충돌이 발생했을때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이 바로 ‘선형 조사법’이다.
충돌시 다음 비어있는 자리까지 선형 탐색을 해서 비어있는자리에 데이터를 넣는다.
데이터를 다시 찾아올 떄에도 hash 한자리에 데이터가 없을시 선형조사를 통해 데이터를 가져온다.
그런데 이러한 선형 조사법은 충돌의 횟수가 증가함에 따라서 ‘클러스터 현상’, 이 발생한다는 단점이 있다. 이를 극복하기 위해서 ‘이차조사법’을 사용할 수 있다.
f(k) + 1^2 → f(k) + 2^2 → f(k) + 3^2 → f(k) + 4^2 → …
이렇게 선형 조사법과 이차 조사법을 사용할때는 DELETED 을 포함시켜 DELETED 에 도달했을때 조사를 계속하게 해야한다.
이차 조사법의 문제로 지적되는 사항은 다음과 같다.
“해쉬 값이 같으면, 충돌 발생시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일하다.”
다시 말해서 f(k)가 같다면 k 가 다르더라도 다음의 순서대로 일정하게 빈 슬롯을 찾게된다.
f(k) + 1^2 → f(k) + 2^2 → f(k) + 3^2 → f(k) + 4^2 → …
“이중 조사법은 좀 멀리서 빈 공간을 찾긴 하지만, 그 빈 공간을 선택하는 방식이 규칙적이다”
이러한 생각을 반영한 것이 ‘이중 해쉬’ 방법이다. 이는 두 개의 해쉬 함수를 사용하기 때문에 붙여진 이름이다.
c는 15보다 작은, 그러면서도 소수중 하나로 결정하게 된다.