MurmurHash-무엇입니까?

MurmurHash-무엇입니까?

---

MurmurHash가하는 일에 대해 높은 수준의 이해를 얻으려고 노력해 왔습니다 .

기본 설명을 읽었지만 언제 사용하고 왜 사용하는지에 대한 좋은 설명을 아직 찾지 못했습니다. 나는 그것이 매우 빠르다는 것을 알고 있지만 조금 더 알고 싶습니다.

Redis bitset에 UUID를 맞추는 방법에 대한 관련 질문을 했고 누군가 MurmurHash 사용을 제안했습니다. 작동하지만 위험 / 이점을 이해하고 싶습니다.

---

Murmur는 비 암호화 용도에 적합한 우수한 범용 해싱 함수 제품군입니다. Austin Appleby가 언급했듯이 MurmurHash는 다음과 같은 이점을 제공합니다.

• 단순합니다 (생성 된 어셈블리 지침의 수 측면에서).
• 좋은 분포 (실제로 모든 키 세트 및 버킷 크기에 대한 카이 제곱 테스트 통과)
• 좋은 눈사태 동작 (최대 바이어스 0.5 %).
• 우수한 충돌 저항성 (Bob Jenkin의 frog.c 고문 테스트 통과. 4 바이트 키의 경우 충돌이 불가능하고 작은 (1 ~ 7 비트) 차이 없음).
• Intel / AMD 하드웨어에서 뛰어난 성능, 해시 품질과 CPU 소비 간의 좋은 균형.

확실히 UUID를 해시하는 데 사용할 수 있습니다 (CityHash, Jenkins, Paul Hsieh 등의 다른 고급 해싱 함수와 마찬가지로). 이제 Redis 비트 셋은 4GB 비트 (512MB)로 제한됩니다. 따라서 128 비트 데이터 (UUID)를 32 비트 (해시 값)로 줄여야합니다. 해싱 기능의 품질에 관계없이 충돌이 발생합니다.

Murmur와 같은 엔지니어링 된 해시 함수를 사용하면 분포의 품질을 최대화하고 충돌 수를 최소화 할 수 있지만 다른 보장은 제공하지 않습니다.

다음은 범용 해시 함수의 품질을 비교하는 몇 가지 링크입니다.

http://www.azillionmonkeys.com/qed/hash.html

http://www.strchr.com/hash_functions

http://blog.aggregateknowledge.com/2011/12/05/choosing-a-good-hash-function-part-1/

http://blog.aggregateknowledge.com/2011/12/29/choosing-a-good-hash-function-part-2/

http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/

---

나는 내가 늦게 회신한다는 것을 알고 있지만 다른 사람에게 도움이 될 수 있습니다 ...

Murmur 해싱 은 해시 기반 조회에 사용되는 비 암호화 해시 함수 이며 전체 Multiply , Rotate 및 XOR 로 3 가지 기본 작업을 사용합니다 . 두 가지 기본 테스트를 통과하여 좋은 해시 기능을 만들기 위해 여러 상수를 사용합니다.

1. 눈사태 테스트
2. 카이 제곱 검정

Murmur Hashing에 대한 자세한 설명은 제가 만든 이 비디오 를 시청할 수 있습니다 .

참고 URL : https://stackoverflow.com/questions/11899616/murmurhash-what-is-it