• 카테고리

    질문 & 답변
  • 세부 분야

    게임 프로그래밍

  • 해결 여부

    해결됨

리스트, 해쉬테이블, 딕셔너리의 차이에 대하여

20.12.01 13:44 작성 조회수 476

2

1. 리스트에서 원하는 값을 찾을려면 메모리에서 처음부터 검색하는 방법으로 딕셔너리 대비해서 성능의 비용은 적고, 느리게 찾는다-이고 딕셔너리는 해쉬테이블 형태로 성능의 비용은 들지만 빠른 시간 내에 찾을 수 있다- 라고 이해 했는데 이게 맞을까요?

2. 해쉬테이블과 딕셔너리의 차이가 제가 다른 지문에서 찾아본 결과 해쉬테이블에 각각의 방의 키값과 내용물은 자료형을 자유롭게 쓸수 있지만 딕셔너리에 비해 느리며 딕셔너리는 키값과 내용물은 일반화(제네릭)가 되어있으며 딕셔너리 사용시 키값과 내용물의 자료형을 미리 선언해서 각각의 방은 선언 된 자료형만 사용해야 된다는 것으로 알고 있습니다. 이것도 이렇게 이해하는 것이 맞는지 궁금합니다.

3. 혹시 그 외에 알아두면 좋은 점이 있는지 말씀해주시면 감사하겠습니다 :)

답변 1

답변을 작성해보세요.

10

1. 아닙니다. 
'빠르게 찾는다 = 성능의 비용이 적다' 와 같은 말입니다.
빠르게 찾는건 다 뒤져볼 필요가 없으니까 빠르게 찾는 것이고,
그렇다면 당연히 성능의 비용도 적게 들겠죠.
리스트에서 검색하면 순차적으로 하나 하나 찾아야 하니,
데이터가 엄청 많다면 (100만개라면) 그 많은 데이터를 다 찾아봐야 할 수도 있습니다. (100만개를 찾아보니 없었다고 한다~)

2.
틀린건 아닌데 해쉬 테이블이라는 단어가
여러가지 의미로 통용되기 때문에 살짝 혼란의 여지가 있습니다.
자료구조/알고리즘에서 말하는 [해쉬 테이블]이라는 것은
키/값 쌍으로 데이터를 해쉬값을 이용해 빠르게 저장하고 찾는 자료구조를 말하며,
Dictionary도 내부적으로는 해쉬 테이블 방식을 이용하고 있습니다.

다만 C#에 Generic 문법이 추가되기 이전에는
Dictionary가 아닌 HashTable이라는 이름의 컬렉션을 사용했는데
HashTable은 모든 아이들을 object로 저장했었습니다.
int나 float나 Monster나 다 object로 저장하니 얼핏보면 편리해보일 수도 있지만,
데이터를 저장하고 꺼낼 때 object<->데이터 변환 (boxing/unboxing)이 일어나기 때문에 성능이 좋지 못합니다.
결과적으로 HashTable의 업그레이드 버전이 Dictionary라고 보시면 됩니다.
자료구조에서 말하는 HashTable과 C# Collection중 HashTable이라는 애가 같은 이름을 사용해서 혼란스럽지만
요약하면 C# Collection의 HashTable은 C# 발전 역사의 유물이며
특별한 상황이 아니라면 그냥 잊고 Dictionary만 사용하면 됩니다.