: 효율적으로 탐색을 하기 위한 알고리즘. Key - Value 쌍의 자료구조
- 일반적으로 Chaining을 통해 구현한 해시테이블을 말한다.
- 충돌이 발생한다면 최악의 경우 O(N)(연결리스트를 가정)이 된다.(N은 버킷 내의 키값 개수)
- 일반적으로 충돌이 발생하지 않도록 구현해 O(1)
- 과정: 키의 해시코드를 계산 후
hash(key) % array_length과 같이 배열 인덱스(버킷 주소)를 구한다. 배열의 인덱스에는 일반적으로 연결리스트 혹은 이진 탐색 트리 가 존재한다. 그 인덱스에 해당하는 자료구조를 탐색하면 된다. - Java의 경우 해시테이블은 1~7까지는 연결리스트, 8부터 이진 트리로 변경한다. 또 다시 6으로 줄어드는 순간 연결 리스트로 변경하는데, 2의 차이를 둔 것은 자료구조 변경에 대한 오버헤드를 고려해 최대한 변화를 적게 두기 위함.
- ` 실제 키 / 버킷의 개수` 비가 1을 넘으면 조회의 성능이 안좋아지고(한 버킷으로 맵핑되는 키가 많아진다), 0에 가까울수록 낭비가 심하다.(맵핑을 받지 않는 버킷이 많아진다) 0.7정도가 적당하다고 한다.
Chaining
Open addressing
- 선형 탐사(linear probing)과 제곱 탐사(Quadratic probing)가 존재.
- 선형 탐사의 경우, 충돌 시 정해진 폭(예를들어 1)으로 인덱스를 탐사. 특정 해시값 주변이 모두 채워져있는 경우(primary clusturing)에 취약
- 제곱 탐사의 경우, 충돌 시 해당 수의 제곱 으로 인덱스 탐사(idx 4 -> 16으로 탐사) 서로 다른 키들이 동일한 해시값을 갖는 경우(secondary clusturing) 에 취약
- 이중 해싱: 둘의 경우를 커버하기 위해 사용
- 해시함수를 두개 이용. 하나는 해시값을 얻을 때, 두번째는 충돌 시 이동 폭을 얻을 때 사용
Reference)
https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/
코딩 인터뷰 완전분석