Является ли это подходящим использованием встроенной хеш-функции python?

Мне нужно сравнить большие куски данных для равенства, и мне нужно сравнивать много в секунду, быстро. Каждому объекту гарантированно будет тот же размер, и это возможно/вероятно, они могут быть немного отличающимися (в неизвестных положениях).

Я видел, что из интерактивного сеанса ниже использование оператора == для байтовых строк может быть медленнее, если различия находятся в конце строки, и это может быть очень быстро, если есть разница вблизи начала.

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

Тем не менее, я понятия не имею о деталях реализации этого хэша, действительно ли это похоже на хэш-стиль, поскольку мне может быть удобно, что когда hash(a) == hash(b), то a == b очень вероятно? Я рад иметь несколько неправильных результатов, если хеш-столкновение достаточно редко (редко в смысле необходимости массив из 200 PS3s за несколько часов, чтобы сделать столкновение)

In [1]: import hashlib

In [2]: with open('/dev/urandom') as f:
   ...:     spam = f.read(2**20 - 1)
   ...:     

In [3]: spamA = spam + 'A'

In [4]: Aspam = 'A' + spam

In [5]: spamB = spam + 'B'

In [6]: timeit spamA == spamB
1000 loops, best of 3: 1.59 ms per loop

In [7]: timeit spamA == Aspam
10000000 loops, best of 3: 66.4 ns per loop

In [8]: timeit hashlib.md5(spamA) == hashlib.md5(spamB)
100 loops, best of 3: 4.42 ms per loop

In [9]: timeit hashlib.md5(spamA) == hashlib.md5(Aspam)
100 loops, best of 3: 4.39 ms per loop

In [10]: timeit hash(spamA) == hash(spamB)
10000000 loops, best of 3: 157 ns per loop

In [11]: timeit hash(spamA) == hash(Aspam)
10000000 loops, best of 3: 160 ns per loop

Ответ 1

Функция хэша Python предназначена для скорости и отображает в 64-битное пространство. Из-за дня рождения парадокса, это означает, что вы, скорее всего, столкнетесь с примерно 5 миллиардами записей (вероятно, раньше, поскольку хеш-функция не криптографический). Кроме того, точное определение hash соответствует реализации Python и может быть архитектурным или даже машинным. Не используйте его, вы хотите получить тот же результат на нескольких машинах.

md5 разработан как криптографическая хэш-функция; даже незначительные возмущения на входе полностью меняют выход. Он также отображает 128-битное пространство, что делает его маловероятным, что вы когда-либо столкнетесь с столкновением вообще, если вы специально не ищете его.

Если вы можете обрабатывать конфликты (т.е. проверять равенство между всеми членами в ведре, возможно, используя криптографический алгоритм, такой как MD5 или SHA2), хеш-функция Python отлично работает.

Еще одна вещь. Чтобы сэкономить место, вы должны хранить данные в двоичной форме, если вы пишете их на диск. (т.е. struct.pack('!q', hash('abc'))/hashlib.md5('abc').digest()).

В качестве примечания стороны: is не эквивалентен == в Python. Вы имеете в виду ==.