Perché Python usa la tabella hash per implementare dict, ma non Red-Black Tree? [chiuso]

Questa è una risposta generale, non specifica per Python.

Confronto di complessità algoritmica

       | Hash Table  |   Red-Black Tree    |
-------+-------------+---------------------+
Space  | O(n) : O(n) | O(n)     : O(n)     |
Insert | O(1) : O(n) | O(log n) : O(log n) |
Fetch  | O(1) : O(n) | O(log n) : O(log n) |
Delete | O(1) : O(n) | O(log n) : O(log n) |
       | avg  :worst | average  : worst    |

Il problema con le tabelle hash è che gli hash possono scontrarsi. Esistono vari meccanismi per risolvere le collisioni, ad es. indirizzo aperto o concatenamento separato. Il caso peggiore assoluto è che tutte le chiavi abbiano lo stesso codice hash, nel qual caso una tabella hash si degraderà in un elenco collegato.

In tutti gli altri casi, una tabella hash è una grande struttura dati che è facile da implementare e offre buone prestazioni. Uno svantaggio è che le implementazioni in grado di far crescere rapidamente la tabella e ridistribuire le loro voci probabilmente cancelleranno quasi tutta la memoria che viene effettivamente utilizzata.

Gli alberi RB sono auto-bilanciati e non cambiano la loro complessità algoritmica nel peggiore dei casi. Tuttavia, sono più difficili da implementare. Le loro complessità medie sono anche peggiori di quelle di una tabella hash.

Restrizioni sui tasti

Tutte le chiavi in una tabella hash devono essere lavabili e confrontabili tra loro per l'uguaglianza. Questo è particolarmente facile per stringhe o interi, ma è anche abbastanza semplice estendere a tipi definiti dall'utente. In alcune lingue come Java queste proprietà sono garantite per definizione.

Le chiavi in un RB-Tree devono avere un ordine totale: ogni chiave deve essere paragonabile a qualsiasi altra chiave, e le due chiavi devono essere comparabili più piccole, più grandi o uguali. Questa uguaglianza degli ordini deve essere equivalente all'uguaglianza semantica. Questo è semplice per interi e altri numeri, anche abbastanza facile per le stringhe (l'ordine deve essere solo coerente e non osservabile esternamente, quindi l'ordine non deve considerare locales ^[1] ), ma difficile per altri tipi che non hanno ordine intrinseco. È assolutamente impossibile avere chiavi di tipi diversi a meno che non sia possibile un confronto tra loro.

^{[1]: In realtà, ho torto qui. Due stringhe potrebbero non essere uguali ai byte ma comunque equivalenti secondo le regole di alcune lingue. Vedi per es. Normalizzazioni Unicode per un esempio in cui due stringhe uguali sono codificate in modo diverso. Se la composizione dei caratteri Unicode è importante per la tua chiave di hash è qualcosa che un'implementazione della tabella hash non può sapere.}

Si potrebbe pensare che una soluzione economica per le chiavi RB-Tree sia quella di testare prima l'uguaglianza, quindi confrontare l'identità (cioè confrontare i puntatori). Tuttavia, questo ordine non sarebbe transitivo: se a == b e id(a) > id(c) , allora deve seguire anche quel id(b) > id(c) , che non è garantito qui. Quindi, potremmo usare il codice hash dei tasti come chiavi di ricerca. Qui, l'ordinamento funziona correttamente, ma potremmo finire con più chiavi distinte con lo stesso codice hash, che sarà assegnato allo stesso nodo nell'albero RB. Per risolvere queste collisioni di hash possiamo usare il concatenamento separato proprio come con le tabelle hash, ma questo eredita anche il comportamento peggiore per le tabelle hash - il peggiore dei due mondi.

Altri aspetti

• Mi aspetto che una tabella hash abbia una localizzazione di memoria migliore di una struttura, perché una tabella hash è essenzialmente solo una matrice.

• Le voci in entrambe le strutture dati hanno un overhead piuttosto elevato:

  • tabella hash: chiave, valore e puntatore alla voce successiva nel caso di concatenazione separata. Anche la memorizzazione del codice hash può velocizzare il ridimensionamento.
  • RB-tree: chiave, valore, colore, puntatore figlio sinistro, puntatore figlio destro. Si noti che anche se il colore è un singolo bit, i problemi di allineamento potrebbero significare che si sprecheranno ancora abbastanza spazio per quasi un intero puntatore, o addirittura quasi quattro puntatori quando è possibile allocare solo blocchi di memoria di potenza di due. In ogni caso, una voce RB-albero consuma più memoria di una voce della tabella hash.

• Inserimenti e cancellazioni in un albero RB implicano rotazioni dell'albero. Questi non sono davvero costosi, ma comportano un sovraccarico. In un hash, l'inserimento e la cancellazione non sono più costosi di un semplice accesso (anche se il ridimensionamento di una tabella hash al momento dell'inserimento è un O(n) endeavour).

• Le tabelle hash sono intrinsecamente mutabili, mentre un albero RB potrebbe anche essere implementato in modo immutabile. Tuttavia, questo è raramente utile.

Ci sono tutta una serie di motivi per cui potrebbe essere vero, ma probabilmente quelli chiave sono:

• Le tabelle di hash sono più facili da implementare rispetto agli alberi. Né è del tutto banale, ma le tabelle di hash sono un po 'più semplici e l'impatto sul dominio delle chiavi legali è meno rigoroso in quanto è necessaria solo una funzione di hashing e una funzione di uguaglianza; gli alberi richiedono una funzione di ordine totale, ed è molto più difficile da scrivere.
• Le tabelle hash (maggio) hanno prestazioni migliori a piccole dimensioni. Ciò conta molto perché una parte significativa del lavoro riguarda solo teoricamente grandi set di dati; in pratica, in realtà funziona molto con solo decine o centinaia di chiavi, non milioni. Le prestazioni su piccola scala sono molto importanti e non è possibile utilizzare l'analisi asintotica per capire cosa è meglio lì; devi effettivamente implementare e misurare.

Più facile scrivere / mantenere e un vincitore di prestazioni in casi d'uso tipici? Iscrivimi, per favore!