Хэш-значения Python2 плохо распределены

Question

При использовании встроенного Python hash() Функция на струнах, я просто играл с ней, когда заметил что-то странное. Обычно нормальная хеш-функция должна быть некоррелированной в том смысле, что из hash(A), hash(B) должно быть полностью неузнаваемым (для достаточных определений некоррелированных / неузнаваемых).

Тем не менее, этот быстрый маленький сценарий показывает иначе

In [1]: for i in range(15):
...:     print hash('test{0}'.format(i))
...:
-5092793511388848639
-5092793511388848640
-5092793511388848637
-5092793511388848638
-5092793511388848635
-5092793511388848636
-5092793511388848633
-5092793511388848634
-5092793511388848631
-5092793511388848632
5207588497627702649
5207588497627702648
5207588497627702651
5207588497627702650
5207588497627702653

Я понимаю питона hash() Функция не должна быть криптографически безопасной на любом участке, и для этого вы должны использовать hashlib библиотека, но почему значения testX так регулярно распространяется? Это кажется мне плохим поведением при столкновении.

Answer 1

Хеш рассчитывается один символ за другим. Вот почему хеши так похожи.

Во время вычислений "test0" а также "test1" иметь точно такой же хэш до "test", В последнем символе есть только одно отличие. В безопасных хэшах изменение одного бита в любом месте должно полностью изменить весь хэш (например, благодаря нескольким проходам).

Вы можете проверить это поведение, вычислив хэш "0test" и "1test":

>>> for i in range(15):
...     print hash('{0}test'.format(i))
... 
-2218321119694330423
-198347807511608008
-8430555520134600289
1589425791872121742
-6642709920510870371
-4622800608552147860
8038463826323963107
2058173137418684322
-8620450647505857711
-6600477335291135136
8795071937164440413
4111679291630235372
-765820399655801141
2550858955145994266
6363120682850473265

Это тот тип широкого распространения, который вы ожидали, верно? Кстати, у Python 3, похоже, другое вычисление хеша для строк.

Для получения дополнительной информации о хэше Python2, взгляните на "Python Hash Algorithms":

class string:
    def __hash__(self):
        if not self:
            return 0 # empty
        value = ord(self[0]) << 7
        for char in self:
            value = c_mul(1000003, value) ^ ord(char)
        value = value ^ len(self)
        if value == -1:
            value = -2
        return value

Кстати, эта проблема не связана с Python. В Java "Aa" а также "BB" поделитесь тем же хешем.

Answer 2

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

узнать больше о __hash__ и хеш в документации.

как указано там:

dict. __hash__() должен вернуть целое число. Единственным обязательным свойством является то, что объекты, которые сравниваются равными, имеют одинаковое значение хеш

и - как отметил в комментарии Jean-François Fabre - хэши питона должны быть быстрыми (т.е. создавать словари). криптографические хеши медленные и поэтому непригодны для этого.

Кстати, в Python 3 распределение выглядит более случайным.

Answer 3

Объяснение можно найти в комментариях к исходному коду Python2.7 Objects/dictobject.c:

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

>>> map(hash, (0, 1, 2, 3)) 
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]

Это не обязательно плохо! Наоборот, в таблице размером 2**i, бита младшего разряда i в качестве начального индекса таблицы чрезвычайно быстра, и нет никаких коллизий для кодов, индексируемых непрерывным диапазоном целых чисел. То же самое примерно верно, когда ключи являются "последовательными" строками. Так что это дает поведение лучше случайного в обычных случаях, и это очень желательно.