Dictionary와 HashTable의 차이

# Dictionary

- Key와 Value를 제네릭형으로 선언하는 구조이다.

- .NET에서 HashTable를 제네릭형으로 구현한 것이 Dictionary다.

- 제네릭형이라서 기본적으로는 박싱/언박싱이 일어나지 않는다는 장점이 있다.

- Key 값으로 Struct나 Enum을 사용하였을 경우에는 박싱/언박싱이 발생할 수 있다.

- 내부적으로 Equals(), GetHashCode()를 구현하거나 IEqualityComparer를 상속받는 클래스를 선언해서 박싱/언박싱을 막을 수 있다.

 

# HashTable

- Key와 Value를 object형으로 선언하는 구조이다.

- object형이라서 박싱/언박싱이 발생한다.

- object형이라서 모든 형식을 선언할 수 있는 장점이 있다.

 

개인적으로는 어진간한건 Dictionary에서 처리가 가능하고

Key가 타입이 다른 여러 형식으로 구현되어야하는 상황 자체를 만들지 않는게 맞지 않나 싶다.

(게임 개발쪽에서 그런 경우가 있나 모르겠다.)

 

두가지 다 HashTable의 구조를 가지는데

HashTable의 구조라는 것은 Key와 Value로 구성된 것을 말한다.

.NET에서 가져다 사용할때는 그냥 object냐 제네릭이냐의 차이만 알고 넘어가기도 하는데

조금 더 정확히 이해를 하려면 Hash_Function을 알아야한다.

 

많은 데이터를 사용할 때 Key를 이용하여 어떻게 데이터를 찾는것일까?

그건 Hash_Function에서 Key와 전체 데이터의 양의 나머지 값으로 index를 만들어내기 때문이다.

즉, hash["키값이야"] = Key % 전체 데이터의 양 = index가 되어 해당 값을 찾게 되는 것이다.

 

하지만 위 같은 방법으로 index가 중복되는 경우들이 발생한다.

이것을 충돌(Collision)이라고 한다.

충돌을 최대한 막기 위해 index가 고루 분포될 수 있도록 계산을 해주어야하는데

똑똑하신 분들이 여러가지 방법으로 최고의 방법들을 많이 구현해놓으셨기 때문에 우리가 크게 신경쓸 필요는 없다.

 

퍼온거지만 몇가지 알아보자면

String key
char[] ch = key.toChar();
int hash = 0;
for(int i=0;i<key.length;i++)
	hash = hash*31 + char[i]

Math.Abs(key.GetHashCode() + 1 + (((key.GetHashCode() >> 5) + 1) % (size))) % size;   

이렇게 두가지 정도가 있겠다.

(더 좋은 방법들도 아마 찾아보면 있을거 같은데..)

다람쥐와 포동포동이

 

 

 

 

RememberCook 9월 28일 정식 출시!