Perché l'ordinamento dei dizionari non è deterministico?

Question

Sono passato da Python 2.7 a Python 3.3, e sembra che mentre in Python 2 l'ordinamento delle chiavi del dizionario fosse arbitrario ma coerente, in Python 3 l'ordinamento delle chiavi di un dizionario ottenuto con e.g. vars() appare non deterministico.

se corro:

class Test(object): pass 
parameters = vars(Test) 
print(list(parameters.keys())) 

sia in Python 2.7 e Python 3.3, quindi:

• Python 2.7 mi dà costantemente

  ['__dict__', '__module__', '__weakref__', '__doc__'] 
  

• Con Python 3.3, I può ottenere qualsiasi ordine casuale, ad esempio:

  ['__weakref__', '__module__', '__qualname__', '__doc__', '__dict__'] 
  ['__doc__', '__dict__', '__qualname__', '__module__', '__weakref__'] 
  ['__dict__', '__module__', '__qualname__', '__weakref__', '__doc__'] 
  ['__weakref__', '__doc__', '__qualname__', '__dict__', '__module__'] 
  

Da dove viene questo non determinismo? E perché è qualcosa di simile

list({str(i): i for i in range(10)}.keys()) 

... coerente tra piste, dando sempre

['3', '2', '1', '0', '7', '6', '5', '4', '9', '8'] 

...?

Answer 1

---

Aggiornamento: In Python 3.6, dict ha una new implementation che conserva ordine di inserimento. Tuttavia, questo è un dettaglio di implementazione e non dovrebbe essere invocato.

---

Questo è il risultato di un security fix a partire dal 2012, che è stato enabled by default in Python 3.3 (scorrere fino a "miglioramenti di sicurezza").

Da l'annuncio:

Hash randomizzazione fa sì che l'ordine di iterazione di dicts e imposta di essere imprevedibile e differire tra Python viene eseguito. Python non ha mai garantito l'ordine di ripetizione delle chiavi in un dettato o in un set, e si consiglia alle applicazioni di non fare mai affidamento su . Storicamente, l'ordine di iterazione di dettatura non è cambiato molto spesso nelle versioni ed è sempre rimasto coerente tra le esecuzioni successive di Python. Pertanto, alcune applicazioni esistenti potrebbero fare affidamento su dettare o impostare l'ordine. A causa di questo e del fatto che molte applicazioni Python che non accettano input non attendibili non sono vulnerabili a questo attacco, in tutte le versioni di Python stabili menzionate qui, la RANDOMIZZAZIONE DI HASH È DISATTIVATA PER DEFAULT.

Come indicato sopra, l'ultimo bit in maiuscolo non è più valido in Python 3.3.

Vedere anche:object.__hash__() documentation (barra laterale "Nota").

Se assolutamente necessario, è possibile disabilitare la randomizzazione dell'hash nelle versioni di Python interessate da questo comportamento impostando la variabile di ambiente PYTHONHASHSEED su 0.

---

tuo controesempio:

list({str(i): i for i in range(10)}.keys()) 

... fa non infatti sempre dare lo stesso risultato in Python 3.3, anche se il numero dei diversi ordinamenti è limitato due to il modo in cui le collisioni hash vengono gestiti:

$ for x in {0..999} 
> do 
> python3.3 -c "print(list({str(i): i for i in range(10)}.keys()))" 
> done | sort | uniq -c 
    61 ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] 
    73 ['1', '0', '3', '2', '5', '4', '7', '6', '9', '8'] 
    62 ['2', '3', '0', '1', '6', '7', '4', '5', '8', '9'] 
    59 ['3', '2', '1', '0', '7', '6', '5', '4', '9', '8'] 
    58 ['4', '5', '6', '7', '0', '1', '2', '3', '8', '9'] 
    55 ['5', '4', '7', '6', '1', '0', '3', '2', '9', '8'] 
    62 ['6', '7', '4', '5', '2', '3', '0', '1', '8', '9'] 
    63 ['7', '6', '5', '4', '3', '2', '1', '0', '9', '8'] 
    60 ['8', '9', '0', '1', '2', '3', '4', '5', '6', '7'] 
    66 ['8', '9', '2', '3', '0', '1', '6', '7', '4', '5'] 
    65 ['8', '9', '4', '5', '6', '7', '0', '1', '2', '3'] 
    53 ['8', '9', '6', '7', '4', '5', '2', '3', '0', '1'] 
    62 ['9', '8', '1', '0', '3', '2', '5', '4', '7', '6'] 
    52 ['9', '8', '3', '2', '1', '0', '7', '6', '5', '4'] 
    73 ['9', '8', '5', '4', '7', '6', '1', '0', '3', '2'] 
    76 ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0'] 

Come notato all'inizio di questa risposta, non è più il caso in Python 3.6:

$ for x in {0..999} 
> do 
> python3.6 -c "print(list({str(i): i for i in range(10)}.keys()))" 
> done | sort | uniq -c 
    1000 ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']