MurmurHash-co to jest?

Starałem się uzyskać wysoki poziom zrozumienia tego, co robi MurmurHash .

Przeczytałem podstawowy opis, ale nie znalazłem jeszcze dobrego wyjaśnienia, kiedy go używać i dlaczego. Wiem, że jest bardzo szybki, ale chcę wiedzieć trochę więcej.

Zadałem powiązane pytanie o to, jak mogę dopasować UUID do bitsetu Redis i ktoś zasugerował użycie MurmurHash. To działa, ale chciałbym zrozumieć ryzyko/korzyści.

Author: Community, 2012-08-10
Source

2 answers

Murmur to rodzina dobrych funkcji hashujących ogólnego przeznaczenia, nadających się do zastosowań nie kryptograficznych. Jak stwierdził Austin Appleby, MurmurHash zapewnia następujące korzyści:

  • proste (pod względem liczby wygenerowanych instrukcji montażu).
  • dobra Dystrybucja (przechodzenie testów chi-kwadrat dla praktycznie wszystkich zestawów kluczy i rozmiarów łyżek.
  • dobre avalanche zachowanie (Max bias 0,5%).
    • Dobra odporność na kolizje (wyprzedza żabę Boba Jenkina.c tortury-test. Brak kolizji dla kluczy 4-bajtowych, brak małych (od 1 do 7-bitowych) różnic).
  • świetna wydajność na sprzęcie Intel/AMD, dobra kompromis między jakością hash a zużyciem procesora.

Z pewnością możesz go użyć do haszowania uuid (jak inne zaawansowane funkcje haszujące: CityHash, Jenkins, Paul Hsieh ' s, itp ...). Teraz bitset Redis jest ograniczony do bitów 4 GB (512 MB). Trzeba więc zredukować 128 bitów danych (UUID) do 32 bitów (wartość haszowana). Bez względu na jakość funkcja haszująca, będą kolizje.

Użycie zmodyfikowanej funkcji skrótu, takiej jak Murmur, zmaksymalizuje jakość dystrybucji i zminimalizuje liczbę kolizji, ale nie daje żadnej innej gwarancji.

Oto kilka linków porównujących jakość hashów ogólnego przeznaczenia funkcje:

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/

 114
Author: Didier Spezia,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2021-01-31 11:07:35

MurmurHash może zwracać wartość ujemną, bit oryginalnej wartości i przeciw 0x7fffffff.to jest wartość & 0x7fffffff .Gdy wartość wejściowa jest dodatnia, zwracana jest oryginalna wartość. Gdy liczba wejściowa jest ujemna, zwracana wartość dodatnia jest bitem wartości początkowej, a w stosunku do 0x7fffffff, która nie jest jej wartością bezwzględną. Uwaga: wartość zwracana przez MurmurHash nie może być ustalona długość.

 -2
Author: daemon,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2020-05-21 03:23:25