Что делает хеш в Python?

Я видел пример кода, в котором hashфункция применяется к кортежу. В результате возвращается отрицательное целое число. Интересно, что делает эта функция? Гугл не помогает. Я нашел страницу, которая объясняет, как вычисляется хэш, но не объясняет, зачем нам нужна эта функция.

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

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

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

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

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

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

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

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))оба являются целыми числами, нам нужно сравнить входные данные __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.

Документы Python дляhash() состояния:

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

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

Кроме того, документы дляdict состояния типа :

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

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

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

Пример:

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
dict['Age'] = 8; # update existing entry
dict['School'] = "DPS School" # Add new entry

print ("dict['Age']: ", dict['Age'])
print ("dict['School']: ", dict['School'])

Для получения дополнительной информации обратитесь к этому руководству по типу данных словаря .