해시 테이블 버킷이 소수를받는 이유는 무엇입니까?
해시 기능이 있습니다
H (C) = C % N;
N이 복합 번호를 취하면 가장 간단한 예는 예를 들어 2^N을 복용하는 것입니다.
H (11100 (Binary)) = h (28) = 4
H (10100 (Binary)) = h (20) = 4
이 시점에서 C의 4 번째 바이너리 (오른쪽에서 왼쪽으로)는 "실패"될 것입니다. 이는 C의 4 번째 비트에서 어떤 값을 취하든 H (C)의 동일한 값으로 이어질 것임을 의미합니다. 현재 C의 네 번째 비트는 H (C)의 작동에 전혀 참여하지 않으므로 H (C)는 C의 특성을 완전히 반영하여 충돌 가능성을 높일 수 없습니다.
다른 복합 숫자를 복용 할 때, 일부 C의 비트는 다양한 정도에 "실패"되어 일부 일반적인 응용 프로그램에서 충돌이 발생합니다.
그러나 소수를 취하면 기본적으로 각 C의 비트가 H (C)의 작동에 참여하도록하여 공통 응용 분야에서 충돌 가능성을 줄일 수 있습니다. ．
(개인적인 의견 : 때로는 소수를받지 않는 효율성은 그리 나쁘지 않습니다 ... 그러나 소수를 취하는 것은 의심 할 여지없이 더 안전합니다 ...)
위의 것은 나의 이해입니다
이에 추가하면 공통 응용 프로그램에서 일부 데이터가 종종 유사하다는 것을 의미합니다. 현재 소수를 사용하는 것이 좋습니다. 예를 들어, 저장 될 데이터는 현재 검색 상태를 설명하는 테이블을 저장하는 것과 같은 압축 상태에 있습니다. 현재 소수가없는 해싱 가능성은 비교적 높습니다.
무작위로 분산 된 정수라면 해시 계수는 충분히 크게 늘어나는 한 동일하지만 이것은 분명히 실제 적용을 중단합니다.
당신이 말한 것은 비교적 작은 소수가 선택되면 큰 소수 n을 선택할 때 특정 비트의 n-figit 시스템에서만 실패 할 수 있기 때문에 특별한 상황입니다. 컴퓨터 시스템의 특성과 결합하여 N-figit 표현은 종종 중요하지 않지만 일반적으로 사용되는 2^Nigit 시스템은 더 중요하므로 충돌을 피할 수 있습니다.
실제로, 나는 이진에 압축 된 인접 매트릭스를 저장하기 위해 약간의 많은 숫자를 사용했습니다. 계수가 충분히 크면 복합 수조차도 소수에 매우 가깝게 영향을 줄 수 있지만 일부 (수십 개) 복합 숫자에서는 효율이 심각하게 줄어들어 소수가 비교적 안전합니다.
당신은 당신의 자신의 실험을하고, 임의의 정수를 선택하지 않을 수도 있지만, 일부 일반적인 응용 프로그램을 고려하고, 소수와 복합 숫자를 사용하여 테스트하고, 주로 평균 로딩 계수를 검사하고, 결론은 내 것과 동일 할 수 있습니다. 복합 숫자는 대부분의 시간이 좋지 않으며 거의 모든 숫자는 훌륭합니다.
나는 개인적으로보다 일반적인 의미에서, 당신이 소수를 취하지 않으면 약간의 위험이있을 것이라고 생각합니다. 위험은 비 프라임 번호 M = x*y가 선택된 것으로 가정 할 때 발생하며 해시의 키 가이 제수 x와 관련이있는 경우 비참합니다. 최악의 경우, 모든 것이 x의 배수라고 가정하면 해시의 결과는 1 ~ y가 아닌 1 ~ y라고 상상할 수 있습니다. 그러나 버킷의 크기가 소수로 선택되면 아무런 문제가 없습니다.
읽어 주셔서 감사합니다. 도움이되기를 바랍니다. 이 사이트를 지원 해주셔서 감사합니다!