Binceline

더블해싱은 Open Address 방식이라고 하며, 체이닝과는 다르게 메모리 공간을 최대한 활용하려는 방향성을 가진다. Open Address 중 기본적인 방식이 그저 테이블 크기(Prime number)로 Mod 연산을 수행한 결과 + 충돌 시 1칸씩 이동한 결과라면 더블 해싱은 위에서 이 '1칸씩 이동하는' 부분을 1이 아닌 X만큼 이동하도록 변경한다. X라는 값은 어떻게 선정해야 할까? 저번 포스팅으로 Key값을 소수로 Mod하는 것에 대한 이점을 알아보았다. '어떤 수 A로 Mod 연산 시, A의 약수들의 배수로 이루어진 input에 대해 A보다 작은 해당 수들의 배수가 output이 된다.' 마찬가지로 이 X도 그런 이유로 결정하면 된다. 하지만 추가적으로, 이 이동량이 0이 나오는 경우를 배제..

테이블 크기를 소수로 하는 이유. 소수가 아닌 수 A라고 가정해 보자. 그렇다면 A의 모든 약수는 자신의 배수가 곧 키값이 된다. 예를 들면, 12로 Mod 연산을 한다고 했을 때, 12의 약수input : 3 6 9 12 15 18 21 24 ...output : 3 6 9 0 3 6 9 0... input : 4 8 12 16 20 24 ...output : 4 8 0 4 8 0 ... input : 6 12 18 24 30 36 ...output : 6 0 6 0 6 0 ... 이런 식이다. 하지만 소수는 약수가 1과 자신 뿐이므로 약수의 배수가 항상 약수로 나오는 문제가 제외된다.