МурмурХаш - что это?

Я пытался понять, что MurmurHash.

Я прочитал базовое описание, но пока не нашел хорошего объяснения, когда его использовать и почему. Я знаю его очень быстро, но хочу знать немного больше.

Я задал связанный с ним вопрос о том, как я могу поместить UUID в битовый набор Redis, и кто-то предложил использовать MurmurHash. Он работает, но я хотел бы понять риски/выгоды.

Ответ 1

Murmur - это семейство хороших универсальных функций хэширования, подходящих для использования без криптографии. Как заявил Остин Эпплби, MurmurHash предоставляет следующие преимущества:

простой (в виде числа сгенерированных инструкций сборки).
хорошее распределение (передача чи-квадратов тестов практически для всех наборов ключей и размеров ковша.
good avalanche (максимальное смещение 0,5%).
Хорошая устойчивость к столкновению (проходит тест на пытки Bob Jenkin frog.c. Никаких столкновений для 4-байтных ключей, не малых (от 1 до 7 бит) дифференциалов).
отличная производительность на оборудовании Intel/AMD, хорошая компромисс между качеством хэша и потреблением процессора.

Вы можете использовать его для хэш-UUID (как и любые другие продвинутые функции хэширования: CityHash, Jenkins, Paul Hsieh's и т.д.). Теперь битсет Redis ограничен 4 ГБ бит (512 МБ). Поэтому вам необходимо уменьшить 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/

Ответ 2

Я знаю, что я отвечаю поздно, но это может помочь кому-то еще...

Хеширование мурмора - это не криптографическая который используется для ориентированных на хэш-поиск, он использует 3 основные операции в целом Умножить, Повернуть и XOR. Он использует несколько констант, которые находятся там, чтобы сделать хорошую хэш-функцию, передав 2 основных теста.

Вы можете посмотреть это видео, которое я сделал, для подробного объяснения Murmur Hashing.