Это правильное использование встроенной хэш-функции Python?

Question

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

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

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

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

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

Answer 1

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

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

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

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

Как примечание стороны: is не эквивалентно == в Python. Ты имеешь в виду ==,