¿Es un diccionario de Python un ejemplo de una tabla hash?

Question

Una de las estructuras de datos básicos en Python es el diccionario, que permite grabar "claves" para buscar "valores" de cualquier tipo. ¿Esto se implementa internamente como una tabla hash? Si no, ¿qué es?

Answer 1

Sí, es un mapeo hash o una tabla hash. Puede leer una descripción de la implementación del dict de Python, según lo escrito por Tim Peters, here.

Es por eso que no se 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 

Puede read more about hash tables o check how it has been implemented in python y why it is implemented that way.

Answer 2

Sí. Internamente se implementa como hash abierto basado en un polinomio primitivo sobre Z/2 (source).

Answer 3

Si está interesado en los detalles técnicos, un artículo en Beautiful Code se ocupa de los aspectos internos de la implementación de Python dict.

Answer 4

de ampliar la explicación de nosklo:

a = {} 
b = ['some', 'list'] 
a[b] = 'some' # this won't work 
a[tuple(b)] = 'some' # this will, same as a['some', 'list'] 

Answer 5

Debe haber más de un diccionario de Python que una búsqueda en la tabla de hash de(). Por experimentación bruta encontré este hash de colisión:

>>> hash(1.1) 
2040142438 
>>> hash(4504.1) 
2040142438 

Sin embargo, no se rompe el diccionario:

>>> d = { 1.1: 'a', 4504.1: 'b' } 
>>> d[1.1] 
'a' 
>>> d[4504.1] 
'b' 

cordura cheque:

>>> for k,v in d.items(): print(hash(k)) 
2040142438 
2040142438 

Posiblemente hay otro nivel de búsqueda más allá hash() que evita las 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).)