[자료구조] Hash Table - (1)

앞서 Map을 다룰 때, key가 꼭 integer가 될 필요는 없음을 보았다. 만일 우리가 각 key를 (전체 길이 내의) 특정한 integer 값으로 바꿀 수 있다면, 이 integer 값을 index로 활용해 O(1) 시간에 map에 저장된 element에 접근할 수 있을 것이다. 

 

Hash Table이란 hash function을 이용해 구현된 map이다. hash function이란 바로 윗 문단에서 설명한 'key를 특정한 integer 값으로 바꿔 주는 함수' 이다. 이 때의 값을 'hash value' 라고 한다.

 

즉 어떤 pair (key, value)가 있고, hash function을 h(x)라고 하면, 이 hash table에서 value는 M[h(key)]에 저장된다. 

 

보다 엄밀히 말해, hash function은 다음 두 단계를 거쳐서 hash value를 산출한다.

 

1. key를 integer로 변환.

key를 integer로 변환한다. 이 값을 hash code라고 하는데, 그 값은 굳이 [0, N-1] 범위에 있지 않아도 된다. 이 과정에서 중요한 것은 hash code 간에 충돌을 최대한 회피해야 한다는 것이다. 

ex) Polynomial Hash Code: key가 x_0, x_1, ..., x_n의 n-tuple로 나누어질 때, 다음 연산을 이용해 hash code를 구하는 방법.

x_0*a^(n-1) + x_1*a^(n-2) + ... + x_(n-2)*a+x_(n-1). a는 1이 아닌 정수. 

 

2. hash code를 [0, N-1] 범위 내의 값으로 변환

이 과정을 수행하는 것을 Compression Function 이라고 한다. 여기서도 최대한 충돌을 줄이는 것을 최우선으로 하여야 한다. 

ex)

- Division Method: i mod N.

- MAD(Multiply, Add, and Devide) : [(a*i)+b) mod p] mod N. 여기서 p는 N보다 큰 소수, a는 0보다 크며, a와 b는 [0, p-1] 사이에서 고른 랜덤 정수이다. 

 

이 과정을 거쳤음에도 충돌이 발생할 수 있다. 따라서 다음 포스팅에서는 충돌이 발생했을 때의 Collision Handling 방법을 알아본다.