I했습니다 블룸 필터에 대한 해시 함수 선택에 대한 다음과 같은 질문 있어요 :어떤 해시 함수는 블룸에서 사용하는
당신은 블룸에서 사용되는 해시 함수이는 독립적이고 균일하게 분포되어야한다 필터링 할 것을 읽을 수 있습니다.
나는 이것이 (독립적이고 균일하게 배포 된) 의미는 알고 있지만 해시 함수가 이러한 요구 사항을 충족하고 적합하기 때문에 인수 또는 토론을 찾는 데 어려움이 있습니다. 많은 게시물에서 나는 FNV 또는 Murmur 해시 함수의 사용법에 대한 제안을 읽었지만 왜 그런지 (또는 적어도 증거가없는) 적절한 것은 아닙니다.
미리 감사드립니다.
Hash Functions은 왜 FNV가 나쁜 선택 일 수 있으며 왜 Murmur2 또는 Bob Jenkins' Hashes 중 하나가 좋은 선택인지에 대한 그래픽 증거를 제공해야합니다.
자바 블룸 필터 라이브러리를 만들 때 나는 같은 질문을 던졌습니다. 블룸 필터의 해시 함수 분석에 대한 자세한 처리 방법은 the Github readme을 참조하십시오.
나는 두 가지 관점에서 문제를 바라 보았다?
속도는 임의 입력에 대한 벤치 마크로 쉽게 측정 할 수 있습니다. 균일 성은 조금 더 어렵고 일부 통계가 필요합니다. 카이 - 스퀘어 적합성 테스트를 사용하여 해시 값의 분포가 균일 분포에 얼마나 유사한지를 측정했습니다.
결과는 다음과 같습니다에 대한
구현이 Java를 사용하는 경우 Bloom 필터 해시 라이브러리를 사용하는 것이 좋습니다. 그것은 잘 문서화되어 철저히 테스트되었습니다. 다른 해시 함수에 대한 벤치 마크 결과와 카이 제곱 검정에 따른 불완전 성을 포함한 자세한 내용은 Github readme of the repo을 참조하십시오.
합리적인 옵션은 여러 CRC 해시가 될 것이라고 생각합니다.당신이 부울 필드 계수를 갖는 다항식에 대해 여러 개의 n 비트 해시 값을 원한다면, 차수 n + 1의 다중 다항식이 있다고 가정합니다. 그러나 나는이 다항식을 찾는 과정을 모른다.
또 다른 가능성은 여러 개의 모듈로 해시를 사용하는 것입니다. Bloom Filter 비트 배열의 크기는 최대 모듈로 값이어야합니다. 그러나 그것이 잘 작동하기 위해서는 계수 값이 10보다 큰 소수와 서로 상대적으로 소수의 곱 이어야만한다고 생각합니다. 그리고 최소 계수 값에서 최대 계수 값까지의 범위는 가능한 한 작아야합니다. 나는 그러한 가치를 발견 할 수있는 방법을 모른다. 나머지 부분을 빠르게 계산할 수있는 오픈 소스 C++ 코드를 작성했습니다 : https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/modulus_hash.h
[Kirsch-Mitzenmacher-Optimization] (https://www.eecs.harvard.edu/~michaelm/postscripts/tr)을 읽지 않았습니다. hash_i = hash1 + ix hash2 % p, 여기에서 p는 소수이며, hash1과 hash2는 [0, p-1]의 범위 내에 있고, 비트 세트는 k * p 비트로 구성됩니다. . – cyber4ron