Hash

Hash는 검색과 저장이 매우 빠른 자료구조이다.
Hash를 정의하자면 키에 대한 해시 값을 사용하여 값을 저장하고 조회하며 키 값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array이다.
C++의 map, C#의 dictionary, Java의 hashtable hashmap이 hash의 구현체이다.

hashtable과 hashmap의 차이는 hashmap은 보조 해시 함수를 사용하여 해시 충돌이 덜 발생하는 장점이 있으며 hashmap은 지속적으로 개선이 되고있다.

Big-O Notation

Hash의 Big-O Notation은 기본적으로 O(1)을 지향한다. 하지만 Big-O Notation은 Hash Collision의 정도에 따라 선형적 혹은 지수적으로 변하게 된다. 그리고 해시 충돌을 어떻게 해결하느냐에 따라 평균 수행 시간이 달라지게 된다.

Hash Collision

Hash의 특성상 서로 다른 key가 같은 hash value를 가지게 되는 경우가 있다. 이런 경우를 Hash Collision이라 하며 Hash Collision이 발생할 경우 다음과 같이 해결한다.

open addressing

open addressing이라 불리는 해쉬 충돌을 해결하는 방법은 해시 충돌이 발생하게 되면 일정 버킷을 뛰어넘어 재시도를 하게 된다. 얼마만큼의 버킷을 이동할것이냐에 따라 선형 탐사 제곱 탐사 이중 해싱이 존재한다. 충돌이 많이 발생하게 될 때 최악의 상황에서 O(n)까지 탐색 시간이 소요된다.

chainning

chainning이라 불리는 방법은 해시 충돌이 발생하면 해당 버킷에 리스트 형식으로 삽입을 수행한다. 리스트형식으로 삽입을 수행하기 때문에 해시 내의 데이터 밀집도가 높을 경우 O(1)이 아니게 된다. 기본적으로 chainning을 통해서 다양한 언어차원에서 해쉬 충돌을 해결하고 있으며 C++, C#, Java 7이하 에서는 hash chain + linked list의 조합으로 해결하고 있고 JAVA 8이상부터 hash chain + red-black-tree의 조합으로 해결하고 있다. linked list를 사용한 hash의 평균 기대 시간은 E(N/M) 이 되고 red-black-tree를 사용한 hash의 평균 기대 시간은 E(logN/M)이 된다.

다음은 체이닝과 선형 주소법의 적재량에 따른 해싱 속도 비교를 나타낸 도표이다.