¿Es un diccionario de Python un ejemplo de 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.¿Se implementa esto 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 de dict de Python, escrita por Tim Peters, aquí.

Es por eso que no puedes usar algo 'no hashable' como clave de dictado, 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 sobre tablas hash o comprueba cómo se ha implementado en Python y por qué se implementa de esa manera.

Answer 2

Debe haber más en un diccionario de Python que una búsqueda de tabla en hash().Por experimentación bruta encontré esto. 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 exista otro nivel de búsqueda más allá de hash() que evite colisiones entre claves del diccionario.O tal vez dict() use 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 3

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

Answer 4

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