반응형
Hash Table
Hash Table은 key와 value의 구조를 자료구조다. Hash Function을 통해 Hash 값을 구해서 인덱스로 사용하고, 이 인덱스가 key가 되며, key를 통해 value를 얻을 수 있다.
버킷에 있는 해시값을 인덱스로 접근하기 때문에 탐색 시간 복잡도는 O(1)이므로 탐색 시에 효율적인 알고리즘이다. 다만 해시 테이블은 해시 함수를 구하는 과정에서 중복이 발생할 수 있으며, 이를 해시 충돌(Hash Collision)이라 한다.
- 해시 테이블은 다음과 같이 해시 함수, 버킷, 엔트리를 통해서 값을 보관한다.
충돌 해결 방법
해시 충돌 해결 방법으로는 개방 주소법(open-addressing)과 체이닝(chaining) 기법이 있다.
개방 주소법(open-addressing)
개방 주소법에는 Linear probing, Quadratic probing, double hashing 기법이 있다.
- 개방 주소법은 해시 값이 중복되는 경우 보조 해시 함수의 규칙에 의해 빈 공간을 조사하는 probing 과정을 거친다. 이 때 빈 공간이 존재하지 않으면 키를 저장할 수 없으므로 적재량을 확인하여 버킷의 크기를 늘릴 수 있다.
h'(key) -> {0,1, ... , m-1}
// linear probing
h(key, i) = (h'(key) + i) mod m
// quadratic probing
h(key, i) = (h'(key) + (c1 * i) + (c2 * i^2)) mod m
// double hasing
h(key, i) = (h1(key) + (i * h2(key))) mod m- 보조 해시 함수 h'(key)는 키를 0부터 해시 테이블의 크기-1 까지 범위를 갖고 있으며, 충돌난 위치부터 1씩 증가시키며 조사하기 때문에 linear probing이라고 한다.
c1과c2의 임의의 값을 정해서 i를 1씩 증가 시키되 탐색 위치가 달라져서 클러스터링 문제를 줄이는 Quadratic probing기법이 있다.- Quadratic 보다 조금 더 군집 문제를 개선한 기법이 double hasing 기법이다.
- 특정 영역에 키가 몰리는 클러스터 문제로 인해 탐색 저하가 발생할 수 있는 기법이다.
반응형
체이닝 기법
- 체이닝 기법은 해시 충돌 발생 시 링크드 리스트를 만들어서 이어서 연결한다. 즉 최악의 경우로 보면 O(N)번이 발생할 수 있다. 그림과 같이 1에서 충돌이 발생하면 연결리스트로 추가로 연결된다.
- 체이닝 방식의 해시 테이블의 최악의 상황은 해시 함수가 모두 충돌하는 경우이다. 이 때 시간 복잡도는 O(N)이 발생하기 때문에 연결 리스트로 체이닝을 하는 것은 비효율적이다.
- 다음과 같이 체이닝 기법을 리스트가 아닌 Red-Black 트리를 사용하면 최악의 경우에도 O(logN)으로 대응할 수 있다. 자바에서 HashMap은 버킷의 키 적재율이 75프로를 넘어가면 버킷의 크기를 증가시키며, 충돌된 키의 갯수가 8개 이상이 되면 Red-Black 트리로 변경하고, 다시 6개 이하가 되면 연결 리스트로 변경한다.
- 완벽한 자료 구조라는 것은 존재하지 않기 때문에 무조건 장점만 있는 것은 아니다. 일반적으로 연결리스트보다 Red-Black 트리가 트리의 노드가 더 많은 변수가 선언되기 때문에 메모리를 더 소모하게 된다. 또한 트리의 균형을 잡기 위한 재배치 연산으로 삽입 및 삭제의 성능이 떨어질 수 있다.
- 따라서 충돌된 임계치를 정해두고 임계치보다 키의 개수가 적을 경우 연결리스트를 사용하고, 키의 개수가 많아지면 그때 Red-Black 트리를 사용하는 방법을 사용한다.
REFERENCES
반응형
