Ответ 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/