[Programming] 해쉬 함수 (Hash function)

• 해슁은 검색할 키 값을 비교하지 않고 검색할 수 있는 방법으로써 번지를 이용한 정렬방식과 유사한 방식이다. 해슁은 해쉬 테이블을 사용하여단 한번의 접근으로 원하는 레코드를 검색할 수 있다.

• 해쉬 테이블은 파일의 레코드의 키 값에 대응하는 해쉬주소와 레코드를 저장하는 공간은 버켓으로 구성되어 있다. 포인터를 사용하여 구현하는 경우에는 실제의 레코드 대신에 레코드가 저장되어있는 메모리 포인터를 저장한다. 파일 내의 키 값에 해쉬함수를 적용하여 해쉬주소를 생성한다. 해슁의 절차를 보면 아래와 같다.
  • 파일 내 모든 레코드의 키 값을 해쉬함수를 사용해 해쉬주소Hash Address를 구한다.
  • 해쉬주소로 해쉬 테이블을 구성, 해쉬주소의 버켓에 레코드를 입력한다.
  • 검색대상 레코드의 키 값에 해쉬함수를 적용, 해쉬주소를 구한다.
  • 해쉬 테이블에서 해쉬주소로 레코드를 검색
  • 해쉬 테이블: 해쉬 테이블의 크기는 파일의 크기보다 커야한다. 왜냐하면, 주어진 n개의 레코드에 대해 n개의 해쉬주소를 생성하기 위한 해쉬함수는 찾는 것은 불가능하기 때문이다. 대부분의 경우에는 일정한 범위에 산발적으로 데이터가 분포하기 때문에 이러한 분포를 가진 데이터를 함수를 적용하여 최대한 밀집된 범위의 주소로 매핑하는 것은 한계가 있다.
  • 해쉬 테이블의 크기가 적어지는 경우에는 서로 다른 키 값에 대해 동일 해쉬주소가 생성되는 경우가 발생하는데 이러한 현상을 해쉬충돌Hash Collision이라고 한다.
  • 또한 해쉬 테이블의 주소범위를 너무 크게 잡으면 사용하지 않는 기억공간이 많아지므로 공간낭비가 된다. 따라서 해쉬테이블 크기는 주어진 데이터 크기의 1.2~2배 사이가 보편적인 크기라는 연구가 있다.
    • 버켓Bucket: 각 해쉬주소에 해당하는 위치로
      
      한 버켓에 하나 이상의 레코드가 들어갈 수도 있다. 아래의 그림에서는 버켓의 크기가 2인 경우로서 하나의 버켓에 두 개의 레코드가 저장될 수 있다. 즉, 해쉬 함수에 의해 동일한 주소로 매핑된 두 개의 레코드가 저장될 수 있다. 아래 그림에서 해쉬주소 0번지에 레코드 R0와 R21이 저장되어 있다. 그러나 만일 또다른 레코드가 해쉬함수에 의해 해쉬주소 0번지로 매핑된다면 버켓이 이미 가득 찬 상태이므로 해쉬 충돌이 일어나게 되고 해쉬충돌 해결방법에 의해 다른 공간으로 이동을 해야 한다. 따라서 해쉬충돌을 적게 만드는 것이 좋은 해쉬함수가 된다.

해쉬 함수

효과적인 해쉬함수의 조건은 주어진 데이터의 키 값을 가능한 적은 범위로 매핑하면서 해쉬총돌을 되도록 적게 만들어야 한다. 몇가지의 해쉬함수 생성방법에 대하여 알아보도록 한다.

제곱법Mid Square: 키 값을 제곱하여 원하는 자리 수만큼 선택하여 해쉬주소로 사용하는 방법이다. n자리수의 제곱은 2n-1 ~ 2n자리의 정수가 된다. 이중에서 만일 해쉬주소가 1000개가 사용된다면 세자리 정수를 선택하면 된다. 이때 세자리 정수의 위치는 임의로 정한다. 예를 들어, 주어진 키 값의 자리수가 4자리이면 7~8자리 정수가 되고 아래의 그림에서와 같이 3자리의 임의의 위치에서 선택한다.

만일 주어진 해쉬주소의 범위가 0~200까지라면 간단히 나머지 연산자를 사용하여 변환가능하다. 예를 들어, 선택된 3자리의 정수를 변수 X에 치환하고 해쉬주소가 h라면 아래의 식을 적용한다.

h = X % 200

나눔법Division: 키 값에 나머지 연산자(%)를 적용하여 주어진 해쉬주소 범위로 매핑하는 방식이다. 주어진 키 값이 k, 주어진 주소범위가 m이라면 해쉬주소 h(k)는:

h(k) = k % m

이 연산의 결과는 0 ~ m-1범위의 주소를 생성한다. 그러나 주어진 해쉬주소 m이 2의 제곱일(2, 4, 8, ...)때는 동일주소의 생성가능성이 크므로 소수Prime Number를 선택하는 것이 해쉬충돌을 줄이는 방법이다.

폴딩법Folding: 키 값을 몇 개의 부분으로 분할 후 합산하여 해쉬주소를 생성하는 방법이다. 주어진 키 값을 3자리씩 분할하여 단순히 3자리를 더하는 시프트 폴딩방식 또는 3자리 수를 한번은 정방향, 한번은 역방향으로 읽어 더하는 경계 폴딩방식을 사용한다. 예를 들어, 주어진 키 값이 아래와 같다면:

123456789123 => 123 456 789 123
- 시프트 폴딩: 123 + 456 + 789 + 123
- 경계 폴딩: 123 + 654 + 789 + 321

폴딩 결과가 주어진 주소범위에 맞도록 조정상수를 곱해서 크기를 조정한다.

디지트 분석법Digit Analysis: 키 값의 자리수 가운데 레코드간 중복이 적은 값을 가질 확률이 높은 자리들을 선택하는 방식이다. 예를 들어, 주민등록번호 13자리 가운데 중복될 확률이 가장 적은 3자리를 선택하는 방법이다.

해쉬충돌처리Hash Collision Resolution

아무리 효율적인 해쉬함수를 사용해도 해쉬충돌을 피할 수는 없다. 따라서 해쉬충돌이 발생했을 경우 이를 해결하는 방법을 찾아야 한다. 몇가지의 해결방법을 고려해 본다.

개방주소법Open Addressing: 해쉬충돌이 일어났을 경우에 빈자리를 찾아 이동하는 방식이다.

선형탐색법Linear Probing: 만일 ki의 주소 h(ki)가 이미 포화상태라면 h(ki)+1에 레코드 Ri를 입력하는 방식이다. 만일 또다시 h(ki)+1도 포화상태라면 h(ki)+2, h(ki)+3, ...을 찾아본다. 즉 비어있는 주소를 발견할 때까지 선형이동하는 방식이다. 이러한 방식은 데이터가 뭉치는 현상, 즉 클러스터링Clustering을 유발시킨다.

클러스터링은 한번 데이터가 충돌되어 선형이동이 일어나면 첫번째 해쉬주소 부근에 빈자리에 들어가게 된다. 따라서 이후에 어떤 데이터의 해쉬주소가 클러스터를 이루는 주소범위 내로 변환되면 이 데이터 역시 수평이동하면서 클러스터의 가장 끝에 연결되기 때문에 클러스터의 크기를 증가시킨다. 한번 클러스터가 생성되면 점점 클러스터의 크기가 커져서 검색하는 시간이 길어지는 원인이 된다.

2차 탐색법Quadratic Probing: 선형탐색법의 단점인 클러스터링을 완화하기 위한 방식이 2차탐색법이다. 만일 ki의 주소 h(ki)가 포화상태라면 다음 빈자리를 찾기 위해 아래의 식을 사용하여 다음번 빈자리를 검색하여 레코드 Ri를 삽입한다.

h(ki)+m²(m=1, 2, 3, ...)

임의 탐색법Random Probing: 정해진 임의수열에 의해 다음 주소를 찾아가는 방식으로서 임의라고 해서 충돌이 생성될 때마다 다른 수열이 사용되는 것이 아니라, 정해진 패턴에 따라 이동하는 것이다.

2차 탐색법에서는 R10의 해쉬주소인 5번지가 포화상태일 때 5+1, 5+4, 5+9, ...번지를 찾아가게 된다. 5+9=14번지가 비어있으므로 14번지에 입력된다. 또한 검색연산에서도 3번의 검색으로 R10을 찾을 수 있다.

연쇄 방법Chaining Method

포인터에 의해 각 버켓 레코드들을 연결하는 방법이다.

합병연쇄Coalesced Chanining: 빈 버켓에 충돌을 일으키는 레코드를 삽입하고 그 위치를 포인터로서 기억시키는 방법이다. 해쉬충돌이 일어났을 때 빈 버켓을 해쉬 테이블의 뒤에서부터 찾아서 빈자리에 저장하고 그 위치를 이전 버켓의 포인터 필드에 저장한다.

예를 들어, R8이 입력될 때 해쉬주소는 3번지이고 3번지는 이미 포화상태이다. 따라서 5번지의 포인터 링크를 따라서 15번지로 가고, 15번지도 포화상태이면서 15번지의 다음 포인터 링크가 없으면 뒤에서부터 빈자리를 찾아 13번지에 R8을 입력하고, 이 주소를 15번지의 포인터필드에 저장한다.

분리연쇄Separate Chaining: 각 버켓을 주소로 하는 레코드들을 연결리스트로 연결하고 그 헤드포인터를 해쉬 테이블에 저장. 레코드는 해쉬번지가 다른 버켓에 삽입되지 않는다.

해쉬기법의 검색시간

선형탐색 > 2차탐색 > 합병연쇄 > 분리연쇄

즉, 분리연쇄방식이 가장 검색시간이 적게 걸리는 방식이다.

해슁의 평균비교횟수를 고려해 보기로 하자. 주어진 기억공간 즉, 해쉬 테이블의 공간에 얼마만큼의 비율로 데이터가 차지하는가는 공간밀도로 계산할 수 있다.

공간밀도(d) = 레코드 수 / 전체사용공간

위의 주어진 예에서 공간밀도는 d = 11/16 ≒ 0.7
선형검색의 비교횟수는 아래의 식으로 계산할 수 있다.

분리연쇄 비교횟수는 아래의 식으로 계산할 수 있다.

<출처>
http://blog.bagesoft.com/876