Associate Array
key-value 쌍을 저장하는 자료구조이다. key는 unique하며, 특정 value와 매핑된다. 배열과 같은 순차적인 인덱스가 아닌, 키로 인덱싱된 elements들의 모음이다.
Java에서는 Map, Python에서는 Dictionary로 구현되어있다.
Bucket
bucket은 value를 저장하는 자료구조이다.
probe
probe는 빈 bucket을 찾는 행위이고, probe number은 빈 bucket을 몇 번째 찾고 있는지를 의미한다.
load factor
테이블이 얼마나 차있는지 나타내는 수치이다.
테이블 사이즈가 10이고, 5개의 element가 있을 때, load factor는 0.5가 된다.
Key 충돌 해결 전략
Perfect Hash Function
x.equals(y) 가 false 일 때, x.hashcode() ≠ y.hashcode() 이면 해시 함수는 완전한 해시 함수이다.
완전한 해시 함수를 만드는 것은 어려운 일이므로, 키가 충돌했을 때 다음과 같은 전략들을 사용한다.
open addressing
해시값의 충돌이 일어나면, 테이블의 다음 슬롯에 key-value를 저장한다.
- linear probing
단순하게 해시 값의 충돌이 일어나면, 비어있는 bucket을 찾을 때 까지 한칸씩 움직인다. - Quadratic probing
한칸씩 움직이는 것이 아니라, probe number의 quadatric function, 제곱을 해서 찾는 방식이다.]
장점
- linked-list와 같은 자료구조를 사용하지 않아도 되서 memory overhead가 작다.
- 연속된 메모리에 저장하기 때문에 cache-friendly하다.
- small to medium 사이즈 테이블에 적합하다.
단점
- insert와 delete의 비용이 높다.
- 클러스터링
- worst-case 성능이 매우 낮다.
Chaining
해시 테이블의 bucket을 linked list로 관리하는 형태이다. 해시 값 충돌이 일어나면, linked list에 추가해준다.
Java와 Python 모두 Chaining 방식을 기본으로 사용한다.
장점
- 구현하기 쉽다
- worst-case 성능이 좋다.
- large 사이즈 테이블과 충돌이 높은 테이블에 적합하다.
단점
- linked-list를 사용해 메모리를 많이 쓴다. memory overhead가 있다.
- liked-list를 사용해 cache-unfriendly하다.
- average-case 성능이 낮다.
Double Hashing
해시 함수를 두개를 사용하는 방식이다. 첫 번째 해시 함수로 인덱스를 찾았을 때 충돌이 일어나면, 두 번째 해시 함수를 사용해 step size를 결정하고, step size만큼 늘려서 probing한다.
장점
- access time이 빠르다.
- memory overhead가 작다.
- load factor가 좋다
단점
- 구현이 어렵다.
- Step Size (충돌이 일어났을 때, 두 번째 해시 함수가 계산하여 probe할 때 증가되는 값) 를 고려해서 구현해야 한다. step size가 너무 작으면 충돌 가능성이 높고, step size가 너무 크면 테이블에 빈 위치가 많아진다. 테이블의 모든 위치가 probe될 수 있도록 해야한다.
- 해시 함수나 step size를 변경하면 태이블 전체를 조정해야 하므로 시간이 많이 소요된다.
- worst-case 성능이 안좋다.