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

Una de las estructuras de datos básicas 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?

Sí, es una asignación hash o tabla hash. Puede leer una descripción de la implementación del dictado de python, como está escrito por Tim Peters, aquí .

Es por eso que no puede usar algo ‘no hashable’ como clave de dictado, como una lista:

 >>> a = {} >>> b = ['some', 'list'] >>> hash(b) Traceback (most recent call last): File "", line 1, in  TypeError: list objects are unhashable >>> a[b] = 'some' Traceback (most recent call last): File "", line 1, in  TypeError: list objects are unhashable 

Puede leer más acerca de las tablas hash o consultar cómo se implementó en Python y por qué se implementa de esa manera .

Debe haber más en un diccionario de Python que en una búsqueda de tabla en hash (). Por la 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)) 2040142438 2040142438 

Posiblemente haya otro nivel de búsqueda más allá del hash () que evita las colisiones entre las claves del diccionario. O tal vez dict () utiliza 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) .)

Sí. Internamente, se implementa como hashing abierto basado en un polinomio primitivo sobre Z / 2 ( fuente ).

Para ampliar sobre 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']