2 차 프로빙

Question

해시 충돌을 해결하기위한 2 차 프로빙 방법에서 H (k) = h (k) + c1 * i^2 + c2 * i.

해시 테이블의 모든 슬롯을 방문하는 방법을 알려주는 c1 & c2의 값을 결정하는 방법을 알아내는 데 도움이 필요합니다.

Answer 1

해시 테이블 슬롯의 수를 ht_size로합시다. 난 당신이

h(k) + c1*i^2 + c2*i % ht_size 

C1 = 0, C2 = 1이 작동을 의미 가정) 작동도 ht_size 할

C1 = 0, C2 공동 수상. 1은 임의의 수로 동시 소수입니다. ht_size가 우연히 동일한 소수가 아닌 경우에도 소수는 좋은 후보자입니다.

왜 이러한 설정이 모든 슬롯을 방문합니까? c1 = 0이고 c2가 ht_size와 양수이면 ggt (c2, ht_size) == 1입니다. 즉, 그룹 (대수 그룹 이론)에서 c2는 생성자입니다. 이것은 c2**i이 0에서 ht_size - 1까지의 모든 숫자를 생성 함을 의미합니다. **은 전원 연산자, 즉 그룹의 연산자를 i 번 적용하는 것을 의미합니다. 그룹의 연산자는 +이므로 그룹 이론 표기의 c2**i은 정상 표기법의 c2*i에 해당합니다.

나는 이것이 c1과 c2의 조합을 찾기 시작하는 방법을 알려주기를 바란다.