Я использую SHA-1 для обнаружения дубликатов в программе, обрабатывающей файлы. Это не обязательно должно быть криптостойким и может быть обратимым. Я нашел этот список быстрых хэш-функций https://code.google.com/p/xxhash/
Что выбрать, если мне нужна более быстрая функция и конфликт случайных данных рядом с SHA-1?
Может быть, 128-битного хеша достаточно для дедупликации файлов? (против 160 бит sha-1)
В моей программе хеш рассчитывается для блоков от 0 до 512 КБ.
Может быть, это поможет вам: https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed
редкие коллизии: FNV-1, FNV-1a, DJB2, DJB2a, SDBM и MurmurHash
Я не знаю насчет xxHash, но это тоже выглядит многообещающим.
MurmurHash работает очень быстро, а версия 3 поддерживает длину 128 бит, я бы выбрал эту. (Реализовано на Java и Scala.)
Поскольку единственным важным свойством хэш-алгоритмов в вашем случае является вероятность столкновения, вы должны оценить ее и выбрать самый быстрый алгоритм, который соответствует вашим требованиям.
Если мы предположим, что ваш алгоритм имеет абсолютное единообразие, вероятность коллизии хэшей среди n файлов, использующих хеши с возможными значениями d, будет:
Например, если вам нужна вероятность столкновения ниже одного из миллиона среди миллиона файлов, вам потребуется иметь более 5 * 10 ^ 17 различных значений хэша, что означает, что ваши хэши должны иметь не менее 59 бит. Давайте округлим до 64, чтобы учесть, возможно, плохую однородность.
Поэтому я бы сказал, что вам должно хватить любого приличного 64-битного хеша. Более длинные хэши еще больше снизят вероятность коллизии за счет более тяжелых вычислений и увеличения объема хеш-хранилища. Более короткие кеши, такие как CRC32, потребуют от вас написания некоторого явного кода обработки конфликтов.
Google разработал и использует (я думаю) FarmHash для хеширования, критичного к производительности. На странице проекта:
FarmHash является преемником CityHash и включает многие из тех же приемов и техник, некоторые из которых взяты из MurmurHash Остина Эпплби.
...
На процессорах со всеми необходимыми машинными инструкциями около шести различных хеш-функций могут участвовать в линейке FarmHash. В некоторых случаях мы добились значительного увеличения производительности по сравнению с CityHash за счет использования более новых инструкций, которые теперь общедоступны. Однако мы также выжали немного больше скорости другими способами, поэтому подавляющее большинство программ, использующих CityHash, должны хотя бы немного выиграть при переходе на FarmHash.
(CityHash уже был семейством хэш-функций с оптимизацией производительности от Google.)
Он был выпущен год назад, и на тот момент он почти наверняка был самым современным, по крайней мере, среди опубликованных алгоритмов. (В противном случае Google использовал бы что-нибудь получше.) Есть хороший шанс, что это по-прежнему лучший вариант.
128 бит действительно достаточно для обнаружения различных файлов или фрагментов. Риск столкновения бесконечно мал, по крайней мере, до тех пор, пока не предпринимается попытка преднамеренного столкновения.
64 бита также могут оказаться достаточно хорошими, если количество файлов или фрагментов, которые вы хотите отслеживать, остается «достаточно маленьким» (то есть не более нескольких миллионов).
После определения размера хэша вам понадобится хеш с некоторыми очень хорошими характеристиками распределения, такими как те, которые указаны с Q.Score = 10 в вашей ссылке.
Факты:
Вывод:
В вашем случае я бы попробовал гораздо более быстрый алгоритм, такой как CRC32, который имеет почти все необходимые вам свойства и может обрабатывать более 99,9% случаев и только прибегая к более медленному методу сравнения (например, бинарному сравнению), чтобы исключить ложные срабатывания. Быть намного быстрее в подавляющем большинстве сравнений, вероятно, компенсирует отсутствие "потрясающей" однородности (возможно, сгенерировав еще несколько столкновений).
Это как бы зависит от того, сколько хэшей вы собираетесь вычислить за итерацию. Например, 64-битный хэш достигает вероятности столкновения 1 из 1000000 при вычислении 6 миллионов хешей.
См .: Вероятности коллизии хэша
Ознакомьтесь с MurmurHash2_160. Это модификация MurmurHash2, которая выдает 160-битный вывод.
Он вычисляет 5 уникальных результатов MurmurHash2 параллельно и тщательно их смешивает. Вероятность коллизии эквивалентна SHA-1 на основе размера дайджеста.
Это по-прежнему быстро, но MurmurHash3_128, SpookyHash128 и MetroHash128, вероятно, быстрее, хотя и с более высокой (но все же очень маловероятной) вероятностью столкновения. Также есть CityHash256, который выдает 256-битный вывод, который также должен быть быстрее, чем SHA-1.
