¿Es un diccionario de Python un ejemplo de una tabla hash?
187
Una de las estructuras básicas de datos en Python es el diccionario, que permite registrar "claves" para buscar "valores" de cualquier tipo. ¿Se implementa esto internamente como una tabla hash? Si no, ¿qué es?
Busqué un diagrama que representa un dict por un tiempo ahora, que descifra la implementación en memoria y CPython. ¡Gracias por hacer referencia al libro!
Chen A.
Respuestas:
241
Sí, es un mapeo hash o una tabla hash. Puede leer una descripción de la implementación dict de python, como está escrita por Tim Peters, aquí .
Es por eso que no puede usar algo 'no hashable' como clave dict, como una lista:
>>> a ={}>>> b =['some','list']>>> hash(b)Traceback(most recent call last):File"<stdin>", line 1,in<module>TypeError: list objects are unhashable>>> a[b]='some'Traceback(most recent call last):File"<stdin>", line 1,in<module>TypeError: list objects are unhashable
El enlace de Tim Peters parece estar roto, ¿hay un enlace limpio por ahí?
Matt Alcock
1
@MattAlcock: He actualizado el enlace. A veces (generalmente debido a que alguien quiere que se elimine su dirección de correo electrónico en algún lugar), los archivos de la lista de Python se reconstruyen y los identificadores de los correos electrónicos cambian, rompiendo así estos enlaces. Los administradores de pydotorg generalmente intentan evitar eso en estos días.
Martijn Pieters
Pero el uso .keys()puede recuperar una lista de claves. Una tabla hash real no almacenaría claves, solo hashes para ahorrar espacio.
@ noɥʇʎԀʎzɐɹƆ: la clave en sí no se almacena, solo una referencia a ella y al hash.
nosklo hace
32
Debe haber más en un diccionario de Python que una búsqueda de tabla en hash (). Por experimentación bruta encontré esta colisión de hash :
>>> hash(1.1)2040142438>>> hash(4504.1)2040142438
Sin embargo, no rompe el diccionario:
>>> d ={1.1:'a',4504.1:'b'}>>> d[1.1]'a'>>> d[4504.1]'b'
Prueba de cordura:
>>>for k,v in d.items():print(hash(k))20401424382040142438
Posiblemente hay otro nivel de búsqueda más allá de hash () que evita colisiones entre las teclas del diccionario. O tal vez dict () usa un hash diferente.
(Por cierto, esto en Python 2.7.10. La misma historia en Python 3.4.3 y 3.5.0 con una colisión en hash(1.1) == hash(214748749.8).)
Entonces las colisiones son inevitables. El conjunto S puede contener una cantidad infinitamente grande de elementos, y usted desea que se mezcle con un número que una computadora puede almacenar. Cada implementación utilizable de una tabla hash resuelve colisiones, siendo dos de los métodos más frecuentes a) direccionamiento abierto y b) encadenamiento. El hecho de que no utilice un hash perfecto no significa que no sea una tabla hash.
TurnipEntropy
1
Las colisiones sucederán en general, porque hay infinitos valores hashables posibles y códigos hash finitos. Incluso una tabla hash tendría que manejar la colisión de alguna manera.
Yanfeng Liu
3
@ YanfengLiu Creo que esos son exactamente los mismos puntos que TurnipEntropy hizo.
Bob Stein
1
En Python 3.7, parece que hay 2E20 menos 1 valores hash posibles, de hecho. De -1E20 menos 1 a (+) 1E20 menos 1. Prueba hash('I wandered lonely as a cloud, that drifts on high o\'er vales and hills, when all at once, I saw a crowd, a host of golden daffodils.')Esto da un decimal de 19 dígitos, -4037225020714749784si eres lo suficientemente geek como para preocuparte. Continúen con sus propias palabras, niños, y el hash sigue siendo un número de 19 dígitos. Supongo que hay un límite en la longitud de la cadena que puede hacer hash en Python, pero es seguro decir muchas más cadenas posibles que valores posibles. Y hash(False)= 0 por cierto.
Will Croxford
22
Si. Internamente se implementa como hashing abierto basado en un polinomio primitivo sobre Z / 2 ( fuente ).
dictimplementación de Python .Respuestas:
Sí, es un mapeo hash o una tabla hash. Puede leer una descripción de la implementación dict de python, como está escrita por Tim Peters, aquí .
Es por eso que no puede usar algo 'no hashable' como clave dict, como una lista:
Puede leer más sobre las tablas hash o verificar cómo se ha implementado en python y por qué se implementa de esa manera .
fuente
.keys()puede recuperar una lista de claves. Una tabla hash real no almacenaría claves, solo hashes para ahorrar espacio.Debe haber más en un diccionario de Python que una búsqueda de tabla en hash (). Por experimentación bruta encontré esta colisión de hash :
Sin embargo, no rompe el diccionario:
Prueba de cordura:
Posiblemente hay otro nivel de búsqueda más allá de hash () que evita colisiones entre las teclas del diccionario. O tal vez dict () usa un hash diferente.
(Por cierto, esto en Python 2.7.10. La misma historia en Python 3.4.3 y 3.5.0 con una colisión en
hash(1.1) == hash(214748749.8).)fuente
hash('I wandered lonely as a cloud, that drifts on high o\'er vales and hills, when all at once, I saw a crowd, a host of golden daffodils.')Esto da un decimal de 19 dígitos,-4037225020714749784si eres lo suficientemente geek como para preocuparte. Continúen con sus propias palabras, niños, y el hash sigue siendo un número de 19 dígitos. Supongo que hay un límite en la longitud de la cadena que puede hacer hash en Python, pero es seguro decir muchas más cadenas posibles que valores posibles. Yhash(False)= 0 por cierto.Si. Internamente se implementa como hashing abierto basado en un polinomio primitivo sobre Z / 2 ( fuente ).
fuente
Para ampliar la explicación de nosklo:
fuente