[CS] 자료 구조 (4) : 해시 테이블 (Hash Table)

해시 (Hash)

해시는 색인 또는 인덱스이다.

 

해시 함수 (Hash Function)

key로 해시를 만들어내는 함수이다.

 

해시 테이블 (Hash Table)

hash를 주소로 삼아 데이터를 저장하는 효율적 탐색을 위한 자료구조이다.

key와 value 쌍으로 이루어지며, 해시 함수를 통해 입력받은 key를 정수값(index)로 대응시킨다.

 

장점

key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색에서 평균적으로O(1)의 시간복잡도를 가지고 있다.

 

단점

 

1. 해시 충돌(collision)이 있어날 수 있다.
2. 순서/관계가 있는 배열에는 어울리지 않는다.
3. 공간 효율성이 떨어진다. 데이터가 저장되기 전에 저장공간을 미리 만들어놔야한다. 공간을 만들었지만 공간에 채워지지 않는 경우가 발생한다.
4. hash function의 의존도가 높다. 해시함수가 복잡하다면 hash를 만들어 내는데 오래 걸릴 것이다.

 

해시 충돌(collision) 해결방안

해시 테이블에서 중복된 값에 대한 충돌 가능성이 있기 때문에 해결방안을 세워야한다.

 

1. 선형 조사법(linear probing)
2. 이차 조사법
3. 이중 해시법
4. 체이닝

 

1. 선형 조사법(linear probing)

충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다.

ht[k], ht[k+1], ht[k+2] ...

 

삽입 상황

충돌이 ht[k]에서 일어났다면, ht[k+1]이 비어있는지 조사한다. 차있으면 ht[k+2] 조사 ...

테이블 끝까지 도달하면 다시 처음으로 돌아온다. (시작 위치로 돌아온 경우는 테이블이 모두 가득 찬 경우)

 

검색 상황

ht[k]에 있는 키가 다른 값이면, ht[k+1]에 같은 키가 있는지 조사한다.

(비어있는 공간이 나오거나, 검색을 시작한 위치로 돌아오면 찾는 키가 없는 경우)

 

2. 이차 조사법

선형 조사법에서 발생하는 집적화 문제를 완화시켜 준다.

h(k), h(k)+1, h(k)+4, h(k)+9 ...

 

3. 이중 해시법

재해싱(rehasing)이라고도 한다.

충돌로 인해 비어있는 버킷을 찾을 때 추가적인 해시 함수 h'()를 사용하는 방식이다.

h'(k) = C - (k mod C)

h(k), h(k)+h'(k), h(k) + 2h'(k) ...

 

4. 체이닝

각 버킷을 고정된 개수의 슬롯 대신, 유동적 크기를 갖는 연결리스트로 구성하는 방식이다.

충돌 뿐만 아니라 오버플로우 문제도 해결 가능하다. 버킷 내에서 항목을 찾을 때는 연결리스트 순차 탐색 활용한다.