dictionary python

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

Question

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

Answer 1

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 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á de hash () que evite 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) .)

Answer 2

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

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

Es por eso que no puede usar algo ''no halagable'' como una 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 leer más acerca de las tablas hash o verificar cómo se ha implementado en python y por qué se implementa de esa manera .

Answer 4

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

Answer 5

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