Open addressing

Collision을 피하기 위한 다른 방법으로 key를 hash table에 직접 저장

장점

• 포인터를 사용하지 안하도 되므로 구현이 간편
• 포인터를 사용하지 않으므로 추가메모리 공간 사용이 가능

세 가지 오픈 어드레신 기술

• 선형 프로빙
• 이차식 프로빙
• 이중 해싱

선형 프로빙(Linear probing)

$h(k,i)=(k'(k)+i) \mod m$

i 라는 값은 충돌의 횟수를 나타낸다.
현재 키 값이 충돌한 횟수

m = 13
$k = \{5,14,29,25,17,21,18,32,30,9,15,27\}$
$h(k)=k \mod 13$

충돌이 일어나면 다음 빈칸에 값을 집어 넣는다. 값을 검색할 때 h(18)을 사용하면 5가 나오는데 5에 가서 값을 찾으면 해당하는 값과 일치하지 않는다 그러면 다음 칸을 확인하여 찾는 값이 있는지 확인.

장점 및 단점

• 구현은 쉬우나 primary clustering 문제가 있다.
• 값이 들어 있는 slot의 수가 많으면 평균 검색 시간이 증가한다.

primary clustering
key 값을 넣을 빈 slot은 뭉쳐있는 slot들의 끝부분에 존재하기 때문에 값이 들어있는 slot들이 뭉쳐 있는 경우가많다.

해쉬 삭제

• 삭제는 실제로 key값을 삭제하느 것이 맞는가?
  • 실제로 값을 지우는 경우는 "DELETED"라고 표시한다.

왜냐하면 빈 slot이 있는 경우 원래 값이 있었는데 지워서 비어있는지 아니면 원래 값이 없어서 빈 slot인지를 구분할 수 없기 때문

이차식 프로빙 (Quadratic probing)

• 이차식 프로빙은 다음과 값은 형태의 해쉬 함수를 사용
  $h(k,i)=(h'(k)+c_{1}i+c_{2}i^2)\mod m$

주어진 Hash함수 외에 i에 대한 2차함수꼴로 slot을 이동하면서 빈 slot을 찾는다.

단점

• 만약 두 key의 처음 probe 값이 동일하다면 빈 slot을 찾는 과정이 동일하므로 같은 slot을 탐색

• 이런 특성을 secondary clustering이라고 부름.
  처음 충돌한 위치가 같다면 다음 충돌할 위치에서도 반복적으로 계속 충돌이 나게 된다.
  

이중 해싱 (Double hasing)

$h(k,i) = (h_{1}(k)+i*h_{2}(k)) \mod m$

• 처음 탐색하는 위치는 $T[h_{1}(k)]$이다
• 그 다음부터는 $h_{2}(k) \mod m$ 만큼 이동하면서 탐색한다.
  충돌이 발생했을 때, 이동하는 거리가 hash 함수에 의해 계산되어 무작위로 빈 slot을 찾게 한다.
  

주의점

• $h_{2}(k)$ 함수는 해쉬 테이블의 크기 m과 서로 소 관계여야 한다.
• m을 2의 지수승으로 두고 $h_{2}$가 항상 홀수가 되도록 만드는 것이다.
• 다른 방법은 m을 소수로 하고 $h_{2}$을 m 보다 작은 양수로 정하는 것.