해슁(Hashing)

해슁(hashing)

해슁(hashing)

해슁은 일반적인 검색 트리와는 달리 원소값으로부터 직접 저장된 원소의 위치를 계산할 수 있는 테이블을 이용한다. 이 테이블을 해쉬 테이블(hash table)이라고 하며, 해쉬 테이블을 이용한 원소의 삽입, 검색, 삭제 기법을 해슁이라고 한다.

어떤 원소가 주어져 있을 때, 해쉬 테이블 [eqn: T[0..m-1]] 내의 주소를 결정하기 위하여 해쉬 함수(hash function)를 사용한다. 따라서 모든 원소 [eqn: x]에 대해서 해쉬 함수값 [eqn: h(x)]는 [eqn: 0 le h(x) le m-1] 사이의 값을 가져야 한다.

[eqn: h(x)]

해쉬 테이블의 각 엔트리를 버켓(bucket)이라고 하고, 각 버켓은 하나 이상의 슬롯(slot)으로 구성될 수 있다. 각 원소는 하나의 슬롯에 저장된다.

서로 다른 두 원소가 같은 버켓에 대응되면, 즉 [eqn: h(x) = h(y)]이면 충돌(collision)이 발생하였다고 하고, [eqn: x]와 [eqn: y]를 동의어(synonym)라고 부른다. 꽉 찬 버켓에 원소가 대응되면 그 버켓에 새로운 원소를 저장할 수 없는데, 이러한 상황을 오버플로(overflow)라고 한다. 슬롯이 하나이면 충돌과 오버플로는 동시에 발생한다.

해쉬 함수와 오버플로우 처리

해쉬 함수는 원소를 해쉬 테이블의 주소로 변환한다. 해슁의 효율은 해쉬 함수의 선택과 연관이 크므로, 해쉬 함수는 쉽게 계산할 수 있으며 충돌이 적어야 한다. 이상적인 해쉬 함수는 임의의 원소에 대해서 각 버켓에 대응할 확률이 같은 것이다. 해쉬 함수는 종류는 다음과 같은 것이 있다.

a. bit extraction

적절한 위치의 비트을 추출

b. mid-square

원소를 제곱한 다음 적절한 위치를 추출

c. division

[eqn: h(x) = x \ mod m]

d. multiplication

[eqn: h(x) = m cdot fraction(x cdot alpha), 0 < alpha < 1]

e. folding

원소를 동일한 길이로 나누어 더한다.

해쉬 함수를 아무리 잘 선택하더라도 오버플로우가 발생할 수 있다. 오버플로우 처리가 필요하다.

birthday paradox: 23명의 사람중 생일이 같은

사람이 있을 확률이 1/2를 넘는다.

오버플로우 처리 기법은 다음과 같은 것이 있다.

a. linear open addressing

b. chaining

c. rehashing

참고. 안전한 해쉬 함수