[자료구조] Hash

지난 글에서는 O(N)인 선형 탐색과 O(logN)인 이분 탐색까지 알아봤다. 그러나 더 빠른 방법이 있다.

무려 O(1)이 가능한 Hash방법이다. 마치 마법처럼 '띡' 하고 바로 찾아내는 것이다.

Hash란?

Hash는 key-value로 데이터를 다루는 방법으로 함수와 테이블로 이루어져 있다.

어떤 데이터가 입력으로 들어오면 미리 정해놓은 Hash 함수를 이용해서 특정한 값을 구해낸다.

그 다음 그 값에 해당하는 위치에 값을 저장한다.

그렇게 하면 나중에 그 값을 찾을 때 똑같이 Hash 함수에 넣어서 그 값이 저장된 곳을 반환하면 즉각적으로 값을 찾을 수 있다.

 

만약 그 값의 위치가 중복된다면???

Hash 알고리즘의 차이는 충돌(collision)이 일어나는 경우에 어떻게 처리하느냐는 것이다.

해시 함수를 이용해서 값을 얻었을 때 우연히 두 값이 같은 해시 값을 얻을 수 있다.

이 경우를 collision이라고 한다.

 

이 collision을 해결하는 방법은 몇가지가 있다.

1. Division Hash Function(나눗셈 기법)

2. Mid-Square Hash Function

3. Multiplication Hash Function

4. Linear Probing

5. Double Hashing

6. Chained Hashing

 

이 중 1~3번은 해시 함수를 잘 조정해서 중복을 피하는 방법이고, 4~6번은 table에 저장하는 방법을 조정하는 전략이다.

 

Hash Function을 조정하는 방법

1. Division Hash Function은 key의 hashCode를 얻고 그 값을 tableSize로 나눈 나머지를 인덱스로 사용하는 방법이다.

tableSize는 소수로 잡는 것이 좋으며 4k+3형태의 소수가 충돌을 더 잘 피한다는 연구 결과(Radke,1970)가 있다.

 

2. Mid-Square Hash Function은 아래와 같은 과정을 따른다.

   1. 키를 정수값으로 변환한다.

   2. 그 값을 제곱한다.

   3. 결과 정수의 가운데 일부 비트 혹은 자리수를 뽑아 인덱스 값으로 사용한다.

이 방법을 사용하면 단순 나눗셈에 비해 키 분포에 따라 출력 값이 고르게 퍼지는 경향이 있어 충돌을 줄일 수 있다.

 

3. Multitplicative Hash Function은 아래와 같은 과정을 따른다.

   1. 키를 정수값으로 변환한다.

   2. 0<A<1인 상수 A를 곱한다.

   3. 곱한 결과의 소수부에 테이블 크기를 곱하고, 그 값을 버림하여 인덱스로 사용한다.

수식 예시 : {}로 감싼 부분은 소수부를 의미한다.

이 방법 사용 시 나눗셈 연산 대신 곱셈만 쓰면서 비교적 균일한 분포를 얻을 수 있다는 장점이 있다.

 

Table 저장 방법을 이용하는 방법

1. Linear Probing

Linear Probing은 이름에서 알 수 있듯 선형적으로 저장하는 방법이다.

이 방법은 기본 인덱스 (hash(key))에 빈 공간이 있다면 거기에 저장을 하고, 만약 충돌이 발생했다면 인덱스를 하나씩 증가시키면서 빈칸을 찾는 방법이다.

 

다만 이 방법을 사용 시, 서로 다른 키들이 유사한 위치로 해시되어 클러스터(군집)이 발생 할 수 있다는 문제가 있다.

테이블의 데이터가 점점 많아질 수록 이 클러스터들이 합쳐져서 더 큰 클러스터를 만들게 되고, 결과적으로 삽입, 탐색 시 연속된 구간을 계속 찾아야 하는 문제가 발생하여 성능이 저하될 우려가 있다.

 

2. Double Hashing

Double Hashing 기법은 linear probing 방식의 클러스터링 문제를 줄이기 위한 방법이다.

과정은 아래와 같다.

   1. 첫 번째 해시 함수 h1(key)로 기본 위치를 구한다.

   2. 충돌이 발생하면 두 번째 해시 함수 h2(key)를 계산한다.

   3. 다음 위치를 (h1(key) + i * h2(key)) mod tableSize와 같이 i = 1, 2, 3, ...으로 바꾸어가며 일정 해시 간격만큼 띄워서 탐색한다.

이 방법을 사용하면 이동 간격이 key마다 다르기 때문에 여러 키가 몰려도 연속된 군집이 생길 확률이 줄어든다.

 

3. Chained hashing 

이 방법은 고정 크기의 배열을 갖지만 각 배열 요소가 한 개 이상의 데이터를 담을 수 있게 하는 방식이다.

서로 다른 키들이 같은 인덱스에 해시된 경우 해당 버킷에 새 요소를 추가하면 충돌이 해결된다.

각 버킷은 연결 리스트 같은 자료구조를 가지기 때문에 여러 요소를 하나의 공간에 저장할 수 있다.

 

Table 저장 방법에 따른 시간복잡도

기본적으로 Hash는 O(1)을 염두해 두지만 최악의 경우에는 O(N)의 시간이 걸릴 수 있다.

Hash는 부하율에 따라 성능이 저하되기에 부하율을 이용해서 평균 검색 시간을 구해보자

부하율 a = (테이블의 요소의 개수) / (버킷의 총 개수)

 

Linear Probing 방법에서 테이블이 다 차지 않았다고 가정할 때,

평균 비교 횟수는 아래와 같다.

 

Double Hashing의 경우

클러스터링 완화 덕분에 Linear probing보다 약간 더 빠른 검색이 가능하다.

평균 비교 횟수는 아래와 같다.

chained Hashing의 경우 슬롯마다 리스트를 사용하여 저장하기 때문에 평균 비교 횟수는

아래와 같다.

어떤 방법을 사용하더라도 부하율이 크면 O(N)에 가까워지므로 부하율을 적게 유지하는 해시 함수와 저장 방법을 선택하는 것이 좋을 것이다.