[자료구조] 12. 해시 테이블(Hash table)

해시 테이블(Hash table)

해시 테이블은 해시 함수를 이용하는 자료구조로 dictionary의 기능을 한다. 기본적인 원리는 적당한 크기의 공간(배열)을 할당해 두고, 특정 키 x로 접근할 시에 해당 키를 해싱하여 나온 값 h(x)를 배열의 인덱스로 이용하여 배열을 즉시 탐색하는 방식이다.

이진 탐색 트리와의 비교

해시 테이블은 맵 자료구조를 만들 때 유용한데, 이전에 소개한 이진 탐색 트리가 O(h)에 접근이 가능한 것과 달리 O(1)에 접근이 가능하다. 그러나 이진 탐색 트리는 범위를 두고 쿼리가 가능한 반면, 해시 테이블은 정확한 키값을 지정해 줘야 탐색이 가능하다.

공간 면에서도 이진 탐색 트리는 당장 필요한 만큼의 공간을 사용하지만, 해시 테이블은 사용할 공간을 에측해서 미리 할당해 두어야 한다.

또한 공간 초과시나 공간 사용이 늘어날 수록 속도가 느려지기에 공간을 확장하고 rehash하는 과정을 거쳐야 한다.

다만 해시테이블이 캐시 적중률등에서는 우위를 가지기도 한다.

	해시 테이블	이진 탐색 트리
시간 복잡도	평균적으로 O(1)	O(h) -> O(log n)
공간 사용	미리 할당해야함	필요한 만큼만 유동적으로
범위 탐색	불가능	가능
캐시 적중률	배열 기반으로 연속적임 -> 높다	노드 기반으로 파편화됨 -> 낮다

위와 같이 가능 기능을 하는 두 자료구조이지만 큰 차이를 가진다.

ADT

search(key)
insert(key, value)
delete(key)

해시함수

해시 테이블에서 해시함수는 임의의 키값을 받고, [0, N-1]의 값을 반환한다. 이때 N은 할당한 배열 공간의 크기이다.

해시 함수는 크게 두 부분, 첫 번째는 임의의 자료형의 키를 정수형으로 변환하는 작업(Hash code), 두 번째는 나온 정수를 해시 테이블의 크기에 맞게 맞춰주는 과정(Compression function)으로 나뉜다.

Hash code

키 값을 정수형으로 변환할 때 다음과 같은 기법들을 사용할 수 있다.

Integer cast

자료형을 단순 비트로 따져서 integer로 가정하고 사용한다. 그렇기에 기본 정수형(int)보다 크기가 작은 자료형에 대하여 유효하다. 예: byte, short, float 등

Component sum

자료형을 일정 단위의 bit로 나누어 더한다. 예를 들어 "abc"라는 문자열을 나누어 'a' + 'b' + 'c' 이런 식으로 나눈 후 합한다. 문제점으로는 순서와 상관없이 일단 더하기 때문에 "abc"와 "cba"가 같은 결과가 나온다는 점이다. 그렇기에 위치를 고려하는 다음의 방법이 있다.

Polynomial accumulation

자료형을 일정 단위의 bit로 나눈 후, z^n을 각 곱해준 것을 더한다. 이때 z값은 임의의 수로 소수를 선택하는 것이 좋고, n은 각 자릿수이다.

Compression function

Division

y mod N

단순히 N으로 나누어 주는 것이다. 이때 N은 해시 테이블의 크기이다. 이때 N은 소수로 정하는 것이 좋은데 왜냐하면 N의 약수에 대해 충돌문제가 생기기 때문이다. 이때 소수가 아닌 수(예:10)를 사용하면 2, 5의 배수에 대하여 모두 문제가 생긴다.

MAD(Multiply, Add and Divide)

(ay + b) mod N

적당한 수 a를 곱하고 b를 더한 후 N으로 나누는 방식이다.

Collision handling

위와 같이 해시함수로 최대한 충돌을 방지하여도, 충돌은 피할 수 없다(비둘기집 문제, 생일 역설 등). 그렇기에 충돌이 발생하였을 때 관리 해 주어야 한다. 아래에 2가지 방법을 소개한다.

Open addressing(closed hashing)

Linear probing

Quadratic probing

Double hashing

Seperating chaining(open hashing)

Rehash

효율