¿Qué hace el hash en Python?

Vi un ejemplo de código donde la hashfunción se aplica a una tupla. Como resultado, devuelve un número entero negativo. Me pregunto qué hace esta función. Google no ayuda. Encontré una página que explica cómo se calcula el hash pero no explica por qué necesitamos esta función.

Un hash es un número entero de tamaño fijo que identifica un valor particular . Cada valor debe tener su propio hash, por lo que por el mismo valor obtendrá el mismo hash incluso si no es el mismo objeto.

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

Los valores hash deben crearse de tal manera que los valores resultantes se distribuyan uniformemente para reducir la cantidad de colisiones hash que se obtienen. Las colisiones de hash son cuando dos valores diferentes tienen el mismo hash. Por lo tanto, los cambios relativamente pequeños a menudo dan como resultado valores hash muy diferentes.

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

Estos números son muy útiles, ya que permiten una búsqueda rápida de valores en una gran colección de valores. Dos ejemplos de su uso son Python sety dict. En a list, si desea verificar si un valor está en la lista, con if x in values:, Python necesita revisar toda la lista y comparar xcon cada valor en la lista values. Esto puede llevar mucho tiempo list. En a set, Python realiza un seguimiento de cada hash, y cuando escribe if x in values:, Python obtendrá el valor de hash x, lo buscará en una estructura interna y luego solo comparará xcon los valores que tengan el mismo hash que x.

Se utiliza la misma metodología para la búsqueda de diccionarios. Esto hace que las operaciones de búsqueda en sety dictmuy rápido, mientras que en las operaciones de búsqueda listes lenta. También significa que puede tener objetos no hash en a list, pero no en a seto como claves en a dict. El ejemplo típico de objetos que no se pueden usar con hash es cualquier objeto que sea mutable, lo que significa que puede cambiar su valor. Si tiene un objeto mutable, no debería ser hash, ya que su hash cambiará a lo largo de su vida útil, lo que causaría mucha confusión, ya que un objeto podría terminar con el valor hash incorrecto en un diccionario.

Tenga en cuenta que el hash de un valor solo debe ser el mismo para una ejecución de Python. En Python 3.3, de hecho, cambiarán con cada nueva ejecución de 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

Esto hace que sea más difícil adivinar qué valor hash tendrá una determinada cadena, que es una característica de seguridad importante para las aplicaciones web, etc.

Por lo tanto, los valores hash no deben almacenarse permanentemente. Si necesita utilizar valores hash de forma permanente, puede echar un vistazo a los tipos de hashes más "serios", funciones hash criptográficas , que se pueden utilizar para realizar sumas de comprobación verificables de archivos, etc.

TL; DR:

Consulte el glosario : hash()se utiliza como un atajo para comparar objetos, un objeto se considera hash si se puede comparar con otros objetos. por eso usamos hash(). También se utiliza para el acceso dicty setelementos que se implementan como tablas hash de tamaño variable en CPython .

Consideraciones tecnicas

• Por lo general, comparar objetos (que pueden implicar varios niveles de recursividad) es caro.
• preferiblemente, la hash()función es un orden de magnitud (o varios) menos costosa.
• comparar dos hashes es más fácil que comparar dos objetos, aquí es donde está el atajo.

Si lee sobre cómo se implementan los diccionarios , estos usan tablas hash, lo que significa que derivar una clave de un objeto es una piedra angular para recuperar objetos en diccionarios en formato O(1). Sin embargo, eso depende mucho de su función hash para ser resistente a las colisiones . El peor caso para obtener un elemento en un diccionario es en realidad O(n).

En esa nota, los objetos mutables generalmente no son hash. La propiedad hash significa que puede usar un objeto como clave. Si el valor hash se utiliza como clave y el contenido de ese mismo objeto cambia, ¿qué debería devolver la función hash? ¿Es la misma clave o una diferente? Que depende de cómo se defina su función hash.

Aprendiendo con el ejemplo:

Imagina que tenemos esta clase:

>>> 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
... 

Tenga en cuenta: todo esto se basa en la suposición de que el SSN nunca cambia para un individuo (ni siquiera sé dónde verificar ese hecho de una fuente autorizada).

Y tenemos a Bob:

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

Bob va a ver a un juez para cambiar su nombre:

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

Esto es lo que sabemos:

>>> bob == jim
True

Pero estos son dos objetos diferentes con diferente memoria asignada, al igual que dos registros diferentes de la misma persona:

>>> bob is jim
False

Ahora viene la parte donde hash () es útil:

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

Adivina qué:

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

Desde dos registros diferentes puede acceder a la misma información. Ahora prueba esto:

>>> 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

¿Lo que acaba de suceder? Eso es una colisión. Debido a hash(jim) == hash(hash(jim))que ambos son enteros por cierto, necesitamos comparar la entrada de __getitem__con todos los elementos que colisionan. El incorporado intno tiene ningún ssnatributo, por lo que se dispara.

>>> 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>

En este último ejemplo, muestro que incluso con una colisión, se realiza la comparación, los objetos ya no son iguales, lo que significa que sube con éxito a KeyError.

Los documentos dehash() Python para el estado:

Los valores hash son números enteros. Se utilizan para comparar rápidamente claves de diccionario durante una búsqueda de diccionario.

Los diccionarios de Python se implementan como tablas hash. Por lo tanto, cada vez que usa un diccionario, hash()se llama a las claves que entrega para la asignación o búsqueda.

Además, los documentos para eldict estado de tipo :

Los valores que no son hash , es decir, valores que contienen listas, diccionarios u otros tipos mutables (que se comparan por valor en lugar de por identidad de objeto) no se pueden usar como claves.

Los diccionarios y conjuntos utilizan el hash para buscar rápidamente el objeto. Un buen punto de partida es el artículo de Wikipedia sobre tablas hash .

Puede usar el Dictionarytipo de datos en Python. Es muy similar al hash, y también admite el anidamiento, similar al hash anidado.

Ejemplo:

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'])

Para obtener más información, consulte este tutorial sobre el tipo de datos del diccionario .