[자료구조] Hash Table

Hash Table

 Hash Table은 해시함수를 사용하여 Key를 해시값으로 매핑하고, 이 해시값을 index로 하여 데이터(value)를 key와 함께 저장하는 자료구조이다.
 Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 특정 값을 검색하는데 데이터 고유의 index로 접근하게 되므로 average case에 대하여 시간 복잡도가 $O(1)$이 된다(collision이 발생하는 경우도 있기 때문에 항상 $O(1)$이 되진 않는다).

Hash Function

 key값을 입력으로 받아 고유한 index로 변환해 준다. 이 메소드에 의해 반환된 고유의 숫자 값을 hashcode라고 한다. Hash Function을 사용하면 다향한 길이의 key값이더라도 고정 길이의 고유한 숫자 값을 얻을 수 있다.

충돌(Collision)

  서로 다른 문자열이 Hash Function을 통해 Hash한 결과가 같은(중복되는) 경우이다. 어설픈 Hash Function을 사용하는 경우 collision이 빈번하게 일어나 해시를 해시답게 사용하지 못하게 한다. collision이 많이 발생할 수록 검색의 시간 복잡도는 $O(n)$에 가까워진다.collision을 해결하는 방법에는 크게 2가지가 있다.

Open Address 방식 (개방주소법)

 해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식이다. 버킷이란 데이터를 저장하기 위한 공간이다.
 공개 주소 방식이라고도 불리는 이 알고리즘은 collision이 발생하면 데이터를 저장할 장소를 찾아 헤멘다. Worst Case의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다. 이 과정에도 여러 방법들이 존재한다.

1. Linear Probing : 순차적으로 탐색하며 비어있는 버킷을 찾으 ㄹ때까지 계속 진행된다.
2. Quadratic probing : 2차 함수를 이용하여 탐색할 위치를 찾는다.
3. Double hashing probing : 하나의 Hash Function에서 충돌이 발생하면 2차 Hash Function을 이용하여 새로운 주소를 할당한다. 연산량이 많아진다.

Open Addresssing 예시

Separate Chaining 방식 (분리연결법)

 일반적으로 OpenAddressing 방식은 Separate Chaining 보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다.
 반면 Separate Chaining 방식의 경우 collision이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case에 가까워 지는 상황을 줄일 수 있다. Separate Chaning를 구현하는 방식에는 2가지가 있다.

 첫번째는 링크드 리스트를 사용하는 것이다. 각각의 버킷들을 링크드리스트로 만들어 collision이 발생하면 해당 버킷의 list에 추가하는 방식이다. 링크드 리스트이기 때문에 삭제와 삽입이 용이하다. 충돌에 대비하여 미리 공간을 확보해두지 않아도 된다는 점과 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다는 장점이 있지만 하나의 버킷에 대한 리스트가 길어질수록 효율이 떨어진다는 단점이 있다.
 두번째는 트리를 사용하는 방식이 있다. 기본적으로 첫번째 방법과 동일하지만 링크드 리스트 대신에 트리를 사용한다는 차이점이 있다.
 두 개의 방법 중 하나를 선택하는 기준은 하나의 버킷에 할당된 key-value의 쌍이다. 데이터의 개수가 적다면 링크드 리스트, 많다면 트리를 사용하는 것이 많다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. 데이터의 개수가 적을 때 Worst Case를 살펴보면 성능이 차이가 거의 없기 때문에 메모리 효율적인 측면을 봤을 때 데이터 개수가 적을 때에는 링크드 리스트를 사용하는 것이 좋다.

Separate chaining 예시

Tree or Linked list?

  트리와 링크드 리스트의 선택의 기준이 되는 데이터의 개수는 6개와 8개 이다. 기준이 6과 7이 아닌 이유는 구조를 바꾸게 되는 기준이 1이라면 구조를 바꾸는 상황이 과도하게 많이 나타날 수 있기 때문이다. 만약 데이터의 개수가 6개에서 삽입과 삭제를 반복한다면 Switching 비용이 과도하게 요구된다. 따라서 2라는 여유를 남겨두고 기준을 잡아준 것이다.

Open Address vs Separate Chaining

 일단 두 방식 모두 Worst Case 에서 $O(M)$이다. 하지만 Open Address 방식은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다(데이터의 지역성이 이유인 듯 하다). 따라서 데이터의 개수가 충분히 작다면 Open Address 방식이 효율이 더 좋다. 또 다른 차이점은 Separate Chaining 방식에 비해 Open Address 방식은 버킷을 계속해서 사용하기 때문에 Separate Chaining 방식이 테이블의 확장을 더 늦출 수 있다는 것이다.

해시 버킷 동적 할당(Resize)

 해시 버킷의 개수가 적다면 메모리를 아낄 수 있는 대신 해시 충돌로 인해 성능이 떨어질 수 있다. 그래서 Separate Chaining을 사용하는 경우 key-value 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다. Open Addresssing의 경우 고정 크기 배열을 사용하기 때문에 배열이 전부 찼을 경우 배열을 두 배의 크기로 확장한다.
 확장하는 임계점은 현재 데이터의 개수 / 버킷의 개수 = 0.75이다. 0.75라는 숫자는 load factor라고 불린다.