Что делает hash в python?

Ответ 1

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

>>> hash("Look at me!")
4343814758193556824
>>> f = "Look at me!"
>>> hash(f)
4343814758193556824

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

>>> hash("Look at me!!")
6941904779894686356

Эти числа очень полезны, поскольку они позволяют быстро искать значения в большом наборе значений. Два примера их использования - Python set и dict. В list, если вы хотите проверить, есть ли значение в списке, и if x in values: Python должен пройти весь список и сравнить x с каждым значением в values списка. Это может занять много времени для длинного list. В set Python отслеживает каждый хеш, и когда вы вводите if x in values: Python получит хеш-значение для x, найдите его во внутренней структуре и затем сравните только x со значениями, которые имеют одинаковые значения. хэш как x.

Та же методология используется для поиска в словаре. Это делает поиск в set и dict очень быстро, в то время как поиск в list медленный. Это также означает, что у вас могут быть объекты, не являющиеся объектами хеширования, в list, но не в set или в качестве ключей в dict. Типичным примером объектов, не являющихся объектами хэширования, является любой объект, который может изменяться, что означает, что вы можете изменить его значение. Если у вас есть изменяемый объект, он не должен быть хешируемым, так как его хэш будет меняться в течение срока службы, что может привести к путанице, поскольку объект может оказаться в неверном хеш-значении в словаре.

Обратите внимание, что хэш значения должен быть одинаковым только для одного запуска Python. В Python 3.3 они будут фактически меняться для каждого нового запуска Python:

$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
1849024199686380661
>>> 
$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
-7416743951976404299

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

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

Ответ 2

TL; DR:

Обратитесь к глоссарию: hash() используется как ярлык для сравнения объектов, объект считается хешируемым, если его можно сравнить к другим объектам. поэтому мы используем hash(). Он также использовался для доступа к элементам dict и set, которые реализованы как изменяемые хэш-таблицы в CPython.

Технические соображения

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

Если вы читаете о о том, как используются словари, они используют хеш-таблицы, что означает, что получение ключа от объекта является краеугольным камнем для извлечения объектов в словарях в O(1). Тем не менее, очень сильно зависит ваша хеш-функция , устойчивая к столкновениям. наихудший случай для получения элемента в словаре на самом деле O(n).

В этой заметке изменяемые объекты обычно не хешируются. Свойство hashable означает, что вы можете использовать объект в качестве ключа. Если хеш-значение используется как ключ и содержимое того же объекта, то что должно вернуть хэш-функцию? Это один и тот же ключ или другой? Он зависит от того, как вы определяете свою хэш-функцию.

Изучение примера:

Представьте, что мы имеем этот класс:

>>> class Person(object):
...     def __init__(self, name, ssn, address):
...         self.name = name
...         self.ssn = ssn
...         self.address = address
...     def __hash__(self):
...         return hash(self.ssn)
...     def __eq__(self, other):
...         return self.ssn == other.ssn
... 

Обратите внимание: все это основано на предположении, что SSN никогда не изменяется для отдельного человека (даже не знаю, где именно проверить этот факт из авторитетного источника).

И у нас есть Боб:

>>> bob = Person('bob', '1111-222-333', None)

Боб идет к судье, чтобы изменить свое имя:

>>> jim = Person('jim bo', '1111-222-333', 'sf bay area')

Это то, что мы знаем:

>>> bob == jim
True

Но это два разных объекта с разнесенной памятью, как две разные записи одного и того же человека:

>>> bob is jim
False

Теперь идет часть, где hash() удобен:

>>> dmv_appointments = {}
>>> dmv_appointments[bob] = 'tomorrow'

Угадайте, что:

>>> dmv_appointments[jim] #?
'tomorrow'

Из двух разных записей вы можете получить доступ к одной и той же информации. Теперь попробуйте следующее:

>>> dmv_appointments[hash(jim)]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 9, in __eq__
AttributeError: 'int' object has no attribute 'ssn'
>>> hash(jim) == hash(hash(jim))
True

Что только что произошло? Это столкновение. Поскольку hash(jim) == hash(hash(jim)), которые являются целыми числами btw, нам нужно сравнить вход __getitem__ со всеми элементами, которые сталкиваются. Встроенный int не имеет атрибута ssn, поэтому он отключается.

>>> del Person.__eq__
>>> dmv_appointments[bob]
'tomorrow'
>>> dmv_appointments[jim]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: <__main__.Person object at 0x7f611bd37110>

В этом последнем примере я показываю, что даже при столкновении выполняется сравнение, объекты уже не равны, что означает, что он успешно повышает значение KeyError.

Ответ 3

Python docs для hash():

Значения хэш являются целыми числами. Они используются для быстрого сравнения словарных ключей во время поиска словаря.

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

Кроме того, docs для состояния dict:

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

Ответ 4

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

Ответ 5

что если у вас есть хешированный объект, но вы хотите увидеть его в прежнем состоянии. Например:

>>> hash('foo')
-450840986

и если возможно:

>>> unhash(-450840986)
'foo'