[자료구조] 더블해싱

더블해싱은 Open Address 방식이라고 하며, 체이닝과는 다르게 메모리 공간을 최대한 활용하려는 방향성을 가진다.

Open Address 중 기본적인 방식이 그저 

테이블 크기(Prime number)로 Mod 연산을 수행한 결과 + 충돌 시 1칸씩 이동한 결과라면

더블 해싱은 위에서 이 '1칸씩 이동하는' 부분을 1이 아닌 X만큼 이동하도록 변경한다.

X라는 값은 어떻게 선정해야 할까?

저번 포스팅으로 Key값을 소수로 Mod하는 것에 대한 이점을 알아보았다.

'어떤 수 A로 Mod 연산 시, A의 약수들의 배수로 이루어진 input에 대해 A보다 작은 해당 수들의 배수가 output이 된다.'

마찬가지로 이 X도 그런 이유로 결정하면 된다.

하지만 추가적으로, 이 이동량이 0이 나오는 경우를 배제해야 한다.

1. Prime Number < Hash Table Size

2. hash2(key) = Prime Number - (key % Prime Number)

이렇게 하면 0이 나오지 않으면서 해당 조건을 만족하는 값을 구할 수 있다.