Быстрая хеш-функция с возможностью столкновения вблизи SHA-1

Ответ 1

Возможно, это поможет вам: 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.)

Ответ 2

Поскольку единственным подходящим свойством хэш-алгоритмов в вашем случае является вероятность столкновения, вы должны оценить его и выбрать самый быстрый алгоритм, который соответствует вашим требованиям.

Если мы предположим, что ваш алгоритм имеет абсолютную однородность, вероятность хэш-столкновения между n файлами с использованием хэшей с d возможными значениями будет:

Например, если вам нужна вероятность столкновения менее одного миллиона в миллионе от одного миллиона файлов, вам нужно будет иметь более 5 * 10 ^ 17 различных значений хэша, что означает, что ваши хэши должны иметь не менее 59 бит. Пусть круглые до 64, чтобы объяснить, возможно, плохую однородность.

Поэтому я бы сказал, что для вас будет достаточно приличного 64-битного хэша. Более длинные хэши будут дополнительно уменьшать вероятность столкновений по цене более тяжелых вычислений и увеличению объема хеш-памяти. Более короткие кеши, такие как CRC32, потребуют от вас ввода некоторого явного кода обработки конфликтов.

Ответ 3

Google разработал и использует (я думаю) FarmHash для высокопроизводительного хеширования. На странице проекта:

FarmHash является преемником CityHash и включает в себя многие из тех же трюков и приемов, некоторые из которых взяты из Austin Applebys MurmurHash.

...

На процессорах со всеми необходимыми машинными инструкциями в линейку FarmHash может входить около шести различных хеш-функций. В некоторых случаях мы добились значительного повышения производительности по сравнению с CityHash, используя новые инструкции, которые в настоящее время доступны. Тем не менее, мы также вытеснили еще одну скорость другими способами, поэтому подавляющее большинство программ, использующих CityHash, должны получить хотя бы немного при переключении на FarmHash.

(CityHash уже был оптимизированным по производительности семейством хеш-функций от Google.)

Он был выпущен год назад, и в этот момент это было почти наверняка состояние дел, по крайней мере, среди опубликованных алгоритмов. (Или Google использовал бы что-то лучше.) Хорошая возможность - это лучший вариант.

Ответ 4

Факты:

1. Хорошие хеш-функции, особенно криптографические (например, SHA-1), требуют значительного времени процессора, потому что они должны соблюдать ряд свойств, которые в этом случае не будут очень полезны;
2. Любая хеш-функция даст вам только одну определенность: если хэш-значения двух файлов разные, файлы, безусловно, разные. Если, однако, их значения хэша равны, есть вероятность, что файлы также равны, но единственный способ точно сказать, является ли это "равенство" не просто хеш-столкновением, это возврат к двоичному сравнению двух файлы.

Вывод:
В вашем случае я бы попробовал гораздо более быстрый алгоритм, такой как CRC32, который имеет почти все необходимые вам свойства и способен обрабатывать более 99,9% случаев и прибегать к более медленному методу сравнения (например, к двоичному сравнению) с исключить ложные срабатывания. Быть намного быстрее при подавляющем большинстве сравнений, вероятно, компенсирует отсутствие "удивительной" однородности (возможно, создание еще нескольких столкновений).

Ответ 5

128 бит действительно достаточно хороши для обнаружения разных файлов или фрагментов. Риск столкновения бесконечно мал, по крайней мере, до тех пор, пока не предпринимается попытка преднамеренного столкновения.

64 бит также могут оказаться достаточно хорошими, если количество файлов или фрагментов, которые вы хотите отслеживать, остается "достаточно маленьким" (т.е. не более нескольких миллионов).

После определения размера хэша вам понадобится хеш с некоторыми очень хорошими свойствами распространения, такими как те, которые перечислены с Q.Score = 10 в вашей ссылке.

Ответ 6

Это зависит от того, сколько хэшей вы собираетесь вычислять на итерации. Например, 64-битный хэш достигает вероятности столкновения 1 в 1000000 с вычислением 6 миллионов хешей.

См. " Вероятности столкновения хешей"

Ответ 7

Проверьте MurmurHash2_160. Это модификация MurmurHash2, которая производит 160-битный вывод.

Он вычисляет 5 уникальных результатов MurmurHash2 параллельно и тщательно их смешивает. Вероятность столкновения эквивалентна SHA-1 на основе размера дайджеста.

Это все еще быстро, но MurmurHash3_128, SpookyHash128 и MetroHash128, вероятно, быстрее, хотя и с более высокой (но все же очень маловероятной) вероятностью столкновения. Там также CityHash256, который производит 256-битный вывод, который должен быть быстрее, чем SHA-1.