[자료구조] Hash table collision

collision

이전 포스트에서 알아본 Hash table에서 발생한 collision을 해결하는 방법에는 대표적으로 2가지 방법이 있다.

1. open addressing 방식은 collision이 발생하면 미리 정한 규칙에 따라 hash table이 비어있는 slot을 찾는다. 빈 slot을 찾는 방법에 따라 Linear Probing, Quadreatic Probing, Double Hashing으로 나뉘게 된다.

2. separete chaining방식은 linked list를 이용한다. 만약 collision이 발생하면 linked list에 노드(slot)를 추가하여 데이터를 저장한다.

Open addressing

Open addressing방식은 collision이 발생하면 미리 정한 규칙에 따라 hash table이 비어있는 slot을 찾는다. 추가적인 메모리를 사용하지 않으므로 linked list 또는 tree 자료구조를 통해 추가로 메모리 할당을 하는 separete chaining 방식에 비해 메모리를 적게 사용한다.

Linear Probing(선형 조사법) & Quadratic Probing(이차 조사법)

선형 조사법은 충돌이 발생한 해시값으로 부터 일정한 값만큼 (+1, +2, +3, ...) 건너 뛰어, 비어 있는 slot에 데이터를 저장한다.
이차 조사법은 제곱수 (+1², +2², +3², ...)로 건너 뛰어, 비어 있는 slot을 찾는다.

Double Hasing(이중해시, 중복해시)

이중 해싱은 open addressing 방식을 통해 collision을 해결할 때, probing하는 방식 중에 하나이다. linear probing이나, quadrtic probing을 통해 탐사할 때는 탐사 이동폭이 같이 때문에 클러스터링 문제가 발생할 수 있다. 클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용하는 방식을 이중 해싱이라한다. 하나는 최초의 해시값을 얻을 때 사용하고 또 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용한다.

Separate chaining

Separate chaining 방식은 linked list 또는 tree를 이용하여 collision을 해결한다. 충돌이 발생하면 linked list에 노드를 추가하여 데이터를 저장한다.

• 삽입 : 서로 다른 두 key가 같은 해시값을 갖게 되면 linked list에 node를 추가하여 (key, value) 데이터 쌍을 저장한다. 삽입의 시간 복잡도는 O(1)이다.
• 검색 : 기본적으로 O(1)의 시간복잡도이지만 최악의 경우 O(n)의 시간복잡도를 갖게 된다.
• 삭제 : 삭제를 위해선 검색을 먼저 해야하므로, 검색의 시간복잡도와 동일하다. 기본적으로 O(1)이지만 최악의 경우 O(n)의 시간복잡도를 갖게 된다.

worst case의 경우 n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 linked list가 생성된다. 이 때, 검색 시간복잡도는 O(n)이 된다.

separate chaining은 기본적으로 linked list를 이용하여 데이터를 저장하지만, collision이 많이 발생하여 linked list의 길이가 길어지면 Binary Search Tree(BST) 자료구조를 이용하여 데이터를 저장하기도 한다. BST를 사용함으로써, 검색의 worst case 시간복잡도를 O(n)에서 O(logn)으로 낮출 수 있다.