해싱 (Hashing) (2)

Hasing

Open Addressing을 통한 충돌 해결

- 모든 키를 해쉬 테이블 자체에 저장한다.

- 테이블의 각 칸(slot)에는 1개의 키만 저장한다.

- 충돌 해결 기법의 종류

Linear probing

Quadratic probing

Double hashing

Open Addressing의 방법 - Linear Probing

- h(k), h(k) + 1, h(k) + 2, ...의 순서로 검사를 진행한다. 만일 원래 저장할 슬롯에 데이터가 존재한다면 계속 뒤로 진행하며 가장 처음에 나오는 빈 슬롯에 데이터를 저장한다.

- 테이블의 끝에 도달하면 다시 처음으로 돌아가며 circular하게 저장 공간을 찾게 된다.

- Linear Probing의 단점

primary cluster : 키에 의해서 채워진 연속된 슬롯들

cluster가 생성되면 점점 cluster는 커지는 문제점이 생기게 된다. cluster가 커지게 되면 해싱 결과가 클러스터의 위에 형성될 가능성이 높아지고 해당 cluster의 뒤에 저장하게 되며 점점 검색에 소요되는 시간이 cluster의 길이에 비례해 늘어나는 문제가 생기게 된다.

Open Addressing의 방법 - Quadratic Probing

- 충돌이 발생하면 h(k), h(k) + $1^2$, h(k) + $2^2$ + h(k) + $3^2$, ...의 순서로 저장을 시도하는 방식이다.

Open Addressing의 방법 - Double Hashing

- 서로 다른 두 해쉬 함수 $h_1$, $h_2$를 이용한다.

- h(k, i) = ($h_1$(k) + i * $h_2$(k)) mod m

- 키의 크기에 따라서 띄어지는 간격이 계속 바뀐다.

Open Addressing - 키의 삭제

- 단순히 키를 삭제만 할 경우에는 문제가 발생하게 된다.

$A_2$, $B_2$, $C_2$가 순서대로 모두 같은 해쉬 함수값을 가져서 linear probing으로 충돌을 해결한다고 한다.

$B_2$를 삭제한 후 $C_2$를 검색할 때는 cluster가 끊어진 상태이기 때문에 문제가 발생하게 된다.

- 문제를 해결하기 위해서 사용할 수 있는 방법들에는 해당 위치의 키가 지워졌다는 것을 표시하거나, 가장 적합한 값을 지워진 자리에 옮겨오는 등이 있을 수 있다.