Hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받는다. Hash function h에 key 값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장한다. 저장, 삭제, 검색의 시간 복잡도는 모두 O(1)으로 매우 강력한 자료 구조이다.
Direct-address table(직접 주소화 방법)
Direct-address Table이란, key 값으로 k를 갖는 원소는 index k에 저장하는 방식이다. 이 방법으로 key-value 쌍의 데이터를 저장하면 크게 아래 두 가지 문제가 발생할 수 있다.
- 불필요한 공간 낭비
- key가 다양한 자료형을 담을 수 없음
Hash Table
Hash table은 (key, value) 데이터 쌍을 저장하기 위한 방법으로, 직접 주소화 방법과는 잘 맞지 않는다. Hash table은 hash function h를 이용하여 (key, value)를 index:h(k)에 저장한다. 이때, "키 k 값을 갖는 원소가 위치 h(k)에 hash된다." 또는 "h(k)는 키 k의 해시값이다."라고 표현한다. key는 무조건 존재해야 하며, 중복되는 key가 있어서는 안된다. 한편, hash table을 구성하고 있는 (key, value) 데이터를 저장 공간을 각각 slot 또는 bucket이라고 부른다.
시간복잡도와 공간 효율
- 시간복잡도는 저장, 삭제, 검색 모두 기본적으로 O(1)이지만, collision에 의해 최악의 경우 O(n)이 될 수 있다.
- 공간효율성은 데이터가 저장되기 전에 미리 저장공간(slot, bucket)을 확보해야 하기 때문에 떨어진다. 따라서 저장공간이 부족하거나 채워지지 않은 부분이 많은 경우가 발생할 수 있다.
좋은 hash function의 조건
각 상황마다 좋은 hash function이 달라질 수 있지만, 대략적인 기준은 연산 속도가 빨라야 하고, 해시값이 최대한 겹치지 않아야 한다는 것이다.
Collision
Collision이란 서로 다른 key의 해시값이 똑같을 때를 말한다. 즉, 중복되는 key는 없지만 해시값은 중복될 수 있는데, 이 때 collision이 발생했다고 한다. 따라서 collision이 최대한 적게 나도록 hash function을 잘 설계해야 하고, 어쩔 수 없이 collision이 발생하는 경우에는 open addressing 또는 separate chaining 등의 방법을 사용하여 해결한다.
Open addressing
open addressing 방식은 collision이 발생하면 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾는 방식이다. 추가적인 메모리를 사용하지 않으므로 linked list 또는 tree 자료 구조를 통해 추가로 메모리를 할당하는 seperate chaining 방식에 비해 메모리를 적게 사용한다.
open addressing은 빈 slot을 찾는 방법에 따라 크게 linear probing, quadratic probing, double hashing으로 나뉜다.
Linear Probing(선형 조사법) & Quadratic Probing(이차 조사법)
선형 조사법은 충돌이 발생한 해시값으로부터 일정한 값만큼(+1, +2, +3, ...) 건너 뛰어, 비어 있는 slot에 데이터를 저장하는 방법이다. 이차 조사법은 제곱수(+1^2, +2^2, +3^2, ...)로 건너 뛰어, 비어 있는 slot을 찾는다.
충돌이 여러번 발생하면, 여러번 건너 뛰어 빈 slot을 찾는다. 선형 조사법과 이차 조사법의 경우, 충돌 횟수가 많아지면 특정 영역에 데이터가 집중적으로 몰리는 클러스터링(clustering) 현상이 발생하는 단점이 있다. 클러스터링 현상이 발생하면, 평균 탐색 시간이 증가하게 된다.
Double Hashing(이중해싱, 중복해싱)
이중 해싱은 클러스터링 문제가 발생하지 않도록, 2개의 해시함수를 사용해 일정하지 않은 탐사이동폭을 사용하는 방식이다. 해시 함수 하나는 최초의 해시값을 얻을 때 사용하고, 나머지 하나는 collision이 발생할 때 탐사 이동폭을 구하기 위해 사용한다.
Separate Chaining
Separate chaining 방식은 linked list 또는 tree를 이용하여 collision을 해결한다. 충돌이 발생하면 linked list에 노드(slot)을 추가하여 데이터를 저장한다.
시간복잡도
- 삽입: 서로 다른 두 key가 같은 해시값을 갖게 되면 linked list에 node를 추가하여 (key, value) 데이터 쌍을 저장한다. 삽입의 시간복잡도는 O(1)이다.
- 검색: 기본적으로 O(1)의 시간복잡도지만, 최악의 경우 O(n)의 시간복잡도를 갖는다.
- 삭제: 삭제를 하기 위해선 검색을 먼저 해야하므로, 검색의 시간복잡도와 동일하다. 기본적으로 O(1)이지만 최악의 경우 O(n)의 시간복잡도를 갖는다.
n개의 모든 key가 동일한 해시값을 갖는 worst case의 경우, 길이 n의 linked list가 생성된다. 이 때, 검색의 시간 복잡도는 O(n)이 된다.
