Un dizionario Python è un esempio di una tabella hash?

Question

Una delle strutture di dati di base in Python è il dizionario, che consente di registrare "chiavi" per cercare "valori" di qualsiasi tipo. Questo è implementato internamente come una tabella hash? In caso contrario, che cos'è?

Answer 1

Sì, è una mappatura hash o una tabella hash. Puoi leggere una descrizione dell'implementazione del dict di Python, come scritto da Tim Peters, qui .

Ecco perché non puoi usare qualcosa di "non cancellabile" come chiave dict, come un elenco:

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

Puoi ulteriori informazioni sulle tabelle hash o controlla come è stato implementato in Python e perché è implementato in questo modo .

Answer 2

In un dizionario Python deve esserci più di una ricerca di tabella su hash (). Per esperimento brutale ho trovato questa collisione di hash :

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

Tuttavia non rompe il dizionario:

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

Controllo della sanità:

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

Forse c'è un altro livello di ricerca oltre l'hash () che evita le collisioni tra le chiavi del dizionario. O forse dict () usa un hash diverso.

(A proposito, questo in Python 2.7.10. Stessa storia in Python 3.4.3 e 3.5.0 con una collisione in hash (1.1) == hash (214748749.8) .)

Answer 3

Sì. Internamente è implementato come hash aperto basato su un polinomio primitivo su Z / 2 ( fonte ).

Answer 4

Per espandere la spiegazione di nosklo:

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