python dict dettagli di implementazione

Question

Ho una domanda sull'implementazione del dizionario Python.

Sembra pitone manterrà un ordine di ricerca per tutti i tasti, per esempio se si fa la seguente operazione

a = {} 
a[3] = 1 
a[0] = 2 

a = {0:2, 3:1} 

pitone cambierà automaticamente il mio ordine di inserimento. Siccome Python afferma che il comando è impostato in modo non ordinato, non sono del tutto capire perché Python manterrà tale ordine di ricerca. Python implementa dettato da una tabella hash e memorizza un altro impostato per l'ordinamento dell'indice?

Spero di chiarire la questione.

Grazie

Answer 1

Dict indice di ordinazione è solo una conseguenza di come viene attuato il dict, e non dovrebbe essere invocata.

Per la precisione, Python non modifica l'ordine di inserzione (poiché è appena definito per essere l'ordine in cui si inseriscono gli elementi nel dettato), ma l'ordine di iterazione non ha garanzie.

Quando Python crea un dict, crea abbastanza spazio per 8 coppie chiave, valore (credo). Per un ditt vuoto, nessuno di loro è pieno. Ogni volta che metti un oggetto in un ditt, Python prende un hash della chiave e l'hash della chiave decide su quale sarà l'indice.

Se si desidera che l'ordine di iterazione sia uguale all'ordine di inserzione, controllare uno ordereddict.

Answer 2

L'ordine di un dict è completamente determinato dalla funzione di hashing dell'oggetto (e dall'ordine di inserimento in caso di collisioni di hash). Interi hash a se stessi (almeno fino a sys.maxint):

>>> hash(1) 
1 

L'implementazione (C) pitone prende il valore hash dell'oggetto e prende alcuni bit per determinare l'indice nella tabella. Quanti bit ci vuole dipende dalla lunghezza del dizionario. Per impostazione predefinita, il dict ha 8 slot disponibili, quindi i numeri 0 e 8 si scontreranno. Possiamo vedere questo come segue:

>>> d1 = {} 
>>> d1[0] = 'foo' 
>>> d1[8] = 'bar' 
>>> d1 
{0: 'foo', 8: 'bar'} 
>>> 
>>> d2 = {} 
>>> d2[8] = 'bar' 
>>> d2[0] = 'foo' 
>>> d2 
{8: 'bar', 0: 'foo'} 

Dal 0 e 8 collisione nel nostro dizionario, ordine di inserimento sembra essere stato mantenuto. 0 prende il primo slot disponibile (dopotutto, non importa quanti bit prendi da 0, avrai 0). 8 prova a prendere anche quello slot. Tuttavia, se viene utilizzato lo slot, la risoluzione delle collisioni prende il sopravvento e Python inserisce tale valore in uno spazio successivo.

Naturalmente, se il vostro dizionario succede ad avere più di ~ 5 elementi, verrà ridimensionata (penso a 16, ma non mi citare su questo) e 0 e 8 non sarà più scontrarsi ...

>>> d1 = {x:x for x in range(1, 6)} 
>>> d1[0] = 0 
>>> d1[8] = 8 
>>> d1 
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 8: 8} 
>>> d2 = {x:x for x in range(1, 6)} 
>>> d2[8] = 8 
>>> d2[0] = 0 
>>> d2 
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 8: 8} 

nota, il (ordinate) ordine conservato (non inserimento ordine) il che significa che ogni intero ottenuto è preferibile posto nella tabella hash (collisioni). Penso che il dict venga ridimensionato quando è pieno di circa 2/3.

---

Nota, questo è puramente accademica - la specificazione Python non dire che questo è come funziona e quindi potrebbe cambiare in qualsiasi momento. Per favore non fare affidamento su questo comportamento. La maggior parte di questo può essere ricavata da comments in the source code e che si trova accanto ad essa ...