Встроенная функция python hash ()

Question

Windows XP, Python 2.5:

hash('http://stackoverflow.com') Result: 1934711907

Google App Engine (http://shell.appspot.com/):

hash('http://stackoverflow.com') Result: -5768830964305142685

Почему это? Как я могу иметь хеш-функцию, которая даст мне одинаковые результаты на разных платформах (Windows, Linux, Mac)?

Answer 1

Как указано в документации, встроенная функция hash () имеет вид , а не и предназначена для хранения результирующих хэшей где-то снаружи. Он используется для предоставления хеш-значения объекта, хранения его в словарях и т. Д. Это также зависит от реализации (GAE использует модифицированную версию Python). Проверить:

>>> class Foo:
...     pass
... 
>>> a = Foo()
>>> b = Foo()
>>> hash(a), hash(b)
(-1210747828, -1210747892)

Как видите, они разные, поскольку hash () использует метод __hash__ объекта вместо «обычных» алгоритмов хеширования, таких как SHA.

Учитывая вышесказанное, рациональным выбором является использование модуля hashlib .

Answer 2

Используйте hashlib , так как hash() предназначен для использования в :

быстрое сравнение словарных ключей при поиске в словаре

и, следовательно, не гарантирует, что оно будет одинаковым во всех реализациях Python.

Answer 3

Ответ абсолютно не удивителен: на самом деле

In [1]: -5768830964305142685L & 0xffffffff
Out[1]: 1934711907L

поэтому, если вы хотите получить надежные ответы на строки ASCII , просто получите младшие 32 бита как uint. Хеш-функция для строк безопасна для 32-бит и почти переносима.

С другой стороны, вы вообще не можете полагаться на получение hash() любого объекта, для которого вы явно не определили метод __hash__ как инвариантный.

Над строками ASCII это работает только потому, что хеш рассчитывается для отдельных символов, образующих строку, как показано ниже:

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

где функция c_mul - это "циклическое" умножение (без переполнения), как в C.

Answer 4

Большинство ответов показывают, что это из-за разных платформ, но это еще не все. С документация object.__hash__(self):

По умолчанию значения __hash__() str, bytes и datetime объекты «засолены» с непредсказуемым случайным значением. Хотя они остаются постоянными в рамках отдельного процесса Python, они не предсказуемы между повторными вызовами Python.

Это предназначено для обеспечения защиты от отказа в обслуживании вызвано тщательно выбранными входами, которые используют наихудший случай производительность вставки dict, сложность O (n²). Увидеть http://www.ocert.org/advisories/ocert-2011-003.html для деталей.

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

Даже работа на одной и той же машине даст разные результаты при каждом вызове:

$ python -c "print(hash('http://stackoverflow.com'))"
-3455286212422042986
$ python -c "print(hash('http://stackoverflow.com'))"
-6940441840934557333

В то время как:

$ python -c "print(hash((1,2,3)))"
2528502973977326415
$ python -c "print(hash((1,2,3)))"
2528502973977326415

---

См. Также переменную среды PYTHONHASHSEED:

Если эта переменная не установлена ​​или не установлена ​​на random, используется случайное значение для сортировки хэшей объектов str, bytes и datetime.

Если для PYTHONHASHSEED установлено целочисленное значение, оно используется как фиксированное семя для генерации hash() типов, охватываемых хешем рандомизации.

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

Целое число должно быть десятичным числом в диапазоне [0, 4294967295]. Указание значения 0 отключит рандомизацию хеша.

Например:

$ export PYTHONHASHSEED=0                            
$ python -c "print(hash('http://stackoverflow.com'))"
-5843046192888932305
$ python -c "print(hash('http://stackoverflow.com'))"
-5843046192888932305

Answer 5

Результаты хеширования варьируются между 32-битными и 64-битными платформами

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

def hash32(value):
    return hash(value) & 0xffffffff

Answer 6

Это хеш-функция, которую Google использует в производственной среде для python 2.5:

def c_mul(a, b):
  return eval(hex((long(a) * b) & (2**64 - 1))[:-1])

def py25hash(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
  if value >= 2**63:
    value -= 2**64
  return value

Answer 7

По-видимому, AppEngine использует 64-битную реализацию Python (-5768830964305142685 не умещается в 32 бита), а ваша реализация Python - 32 бита. Вы не можете полагаться на то, что хеши объектов по значимости сравнимы между различными реализациями.

Answer 8

А как насчет знака?

Например:

Шестнадцатеричное значение 0xADFE74A5 представляет без знака 2919134373 и со знаком -1375832923. Точное значение должно быть подписано (sign bit = 1), но python преобразует его как беззнаковое, и у нас есть неправильное значение хеша после перевода с 64 на 32 бит

Будьте осторожны, используя:

def hash32(value):
    return hash(value) & 0xffffffff

Answer 9

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

mod=1000000009
def hash(s):
    result=0
    for c in s:
        result = (result * 239 + ord(c)) % mod
    return result % mod

Answer 10

Значение PYTHONHASHSEED может использоваться для инициализации значений хеш-функции.

Попытка:

PYTHONHASHSEED python -c 'print(hash('http://stackoverflow.com'))'