해싱 (2)

해시 테이블의 구조

해시테이블 ht는 M개의 버킷으로 이루어지는 테이블로서 ht[0], ht[1], … , ht[M - 1]의 원소를 가진다. 위 그림에서 보이듯이 하나의 버킷은 s개의 슬롯(slot)을 가질 수 있으며, 하나의 슬롯에는 하나의 항목이 저장된다. 하나의 버킷에 여러 개의 슬롯을 두는 이유는 서로 다른 두 개의 키가, 해시함수에 의해 동일한 해시 주소로 변환될 수 있으므로 여러 개의 항목을 동일한 버킷에 저장하기 위함이다. 그러나 대부분의 경우 하나의 버킷은 하나의 슬롯을 가진다.

해시 테이블에 존재하는 버킷의 수가 M이므로 해시함수 h는 모든 키에 대하여 0≤h(x)≤M-1의 범위의 값을 제공해야 한다. 대부분의 경우 해시 테이블의 버킷 수는 모든 키의 경우의 수보다 매우 작으므로 여러 개의 서로 다른 키가 해시함수에 의해 같은 해시 주소로 사상되는 경우가 자주 발생한다. 서로 다른 두 개의 키 k1와 k2에 대하여 h(k1) = h(k2)인 경우를 충돌이라고 하며, 이러한 키 k1과 k2를 동의어라 한다. 만약 충돌이 발생하면 같은 버킷에 있는 다른 슬롯에 항목을 저장하게 된다. 충돌이 자주 발생하면 버킷 내부에서의 순착 탐색 시간이 길어져서 탐색 성능이 저하될 수 있으므로 해시 함수를 수정하거나 해시테이블의 크기를 적절히 조절해 주어야 한다.

이러한 충돌이 버킷에 할당된 수보다 많이 발생하게 되면 버킷에 더 이상 항목을 저장할 수 없게 되는 오버플로우가 발생하게 된다. 만약 버킷 당 슬롯의 수가 하나이면 충돌이 곧 오버플로우를 의미한다. 오버플로우가 발생하면 더 이상 항목을 저장할 수 없게 되므로 오버플로우를 해결하기 위한 방법이 반드시 필요하다.

이상적인 해싱

[학생 정보를 해싱으로 저장, 탐색해보자]

• 5자리 학번 중에 앞 2자리가 학과 번호, 뒤 3자리가 각 학과의 학생 번호
• 같은 학과 학생들만 가정하면 뒤의 3자리만 사용해서 탐색 가능
• 학번이 01023이라면, h(01023) = 23이므로 이 학생의 인적사항은 해시테이블 ht[23]에 저장

• 만약 해시테입르이 1000개의 공간을 가지고 있다면, 이 때 탐색 시간이 O(1)이 되므로 이상적임

  → 즉, 함수 계산 시간만 필요하고, 저장이나 탐색에는 동일한 시간이 걸린다.

실제의 해싱

• 실제로는 해시 테이블의 크기가 제한되므로, 존재 가능한 모든 키에 대해 저장 공간을 할당할 수 없음.
• h(k) = k mod M의 예에서 보듯이 필연적으로 충돌과 오버플로우가 발생함

• 알파벳 문자열 키의 해시 함수가 키의 첫 번째 문자의 순서라고 하자.
  • h(”array”) = 0
  • h(”binary”) = 1
• 입력 데이터 : array, binary, bubble, file, digit, direct, zero, bucket
• 실제 해싱에서는 충돌과 오버플로우가 빈번하게 발생하므로 시간 복잡도는 이상적인 경우의 O(1)보다는 떨어지게 됨

좋은 해시 함수의 조건

• 충돌이 적어야 한다
• 해시 함수 값이 해시 테이블의 주소 영역내에서 고르게 분포되어야 한다.
• 계산이 빨라야 한다.