tabelle hash contro alberi binari

Question

Quando si implementa un dizionario ( 'Voglio cercare dati dei clienti con le loro ID cliente'), le tipiche strutture di dati utilizzati sono tabelle hash e alberi binari di ricerca. So per esempio che il C ++ implementa libreria STL dizionari (li chiamano mappe) che utilizzano (bilanciato) binarie alberi di ricerca, e le tabelle usi framework .NET hash sotto il cofano.

Quali sono i vantaggi e gli svantaggi di queste strutture di dati? C'è qualche altra opzione che è ragionevole in determinate situazioni?

Si noti che non sto particolarmente interessato nei casi in cui i tasti hanno una forte struttura sottostante, per esempio, sono tutti numeri interi compresi tra 1 e n o qualcosa del genere.

Answer 1

Un intero trattato potrebbe essere scritto su questo argomento; Sto solo andando a coprire alcuni punti salienti, e io mantenere la discussione di altre strutture di dati al minimo (ci sono molte varianti in effetti). Nel corso di questa risposta, $ n $ è il numero di chiavi nel dizionario.

La risposta breve è che tabelle hash sono più veloci nella maggior parte dei casi , ma può essere molto male al loro peggio. Ricerca alberi hanno molti vantaggi, tra cui addomesticato caso peggiore comportamento , ma sono un po 'più lento in casi tipici.

Balanced BST hanno una complessità abbastanza uniforme: ogni elemento prende un nodo dell'albero (tipicamente 4 parole memoria), e le operazioni di base (ricerca, inserimento, cancellazione) prendere $ O (\ mathrm {} lg (n)) $ tempo (garantito asintotico limite superiore). Più precisamente, l'accesso nella struttura è di circa $ \ mathrm {log} _2 (n) $ confronti.

sono un po 'più variabile. Essi richiedono una serie di circa $ 2n $ puntatori. L'accesso a un elemento dipende dalla qualità della funzione di hash. Lo scopo di una funzione di hash è per disperdere gli elementi. Una tabella di hash “funziona” se tutti gli elementi che si desidera memorizzare in essa hanno diversi hash. Se questo è il caso, allora le operazioni di base (ricerca, inserimento, cancellazione) prendono $ O (1) $ tempo, con un piuttosto piccola costante (calcolo hash uno più uno ricerca puntatore). Questo rende le tabelle hash molto veloce, in molti casi tipici.

Un problema generale con le tabelle hash è che il $ O (1) $ complessità non è garantito.

• Per Inoltre, c'è un punto in cui il tavolo si riempie; quando ciò accade (o, meglio, un po 'prima che ciò accada), le esigenze tavolo da ingrandire, che richiede lo spostamento tutti i suoi elementi, per un O $ (n) $ costo. Questo può introdurre un comportamento “a scatti” quando vengono aggiunti un sacco di elementi.
• E 'possibile per l'ingresso a collidere su un paio di valori di hash. Questo accade raramente, naturalmente, ma può essere un problema di sicurezza se gli ingressi sono scelti da un attaccante: si tratta di un modo per rallentare notevolmente verso il basso alcuni server. Questo problema ha portato alcune implementazioni linguaggio di programmazione (come Perl e Python) per passare da una semplice tabella hash vecchio ad una funzione hash che coinvolge un numero casuale scelto quando la tabella hash è costruito, insieme con una funzione hash che diffonde questo dato casuale ben (che aumenta la costante moltiplicativa in o (1) $ $), oppure ad un albero binario di ricerca. Mentre è possibile evitare le collisioni usando un hash crittografico, questo non viene fatto, in pratica, a causa hash crittografici sono relativamente molto lento da calcolare.

Quando si lancia località dei dati nel mix, tabelle hash fanno male. Lavorano proprio perché memorizzano elementi correlati distanti, il che significa che, se gli sguardi di applicazione fino elementi condivisione di un prefisso in sequenza, non beneficino dei vantaggi della cache. Questo non è rilevante se l'applicazione effettua ricerche essenzialmente casuale.

Un altro fattore a favore di alberi di ricerca è che sono un immutabile struttura dati: se avete bisogno di prendere una copia di un albero e modificare alcuni elementi in esso, è possibile condividere la maggior parte di la struttura di dati. Se si prende una copia di una tabella di hash, è necessario copiare l'intero array di puntatori. Inoltre, se si sta lavorando in un lingue puramente funzionali, tabelle hash spesso non sono un'opzione.

Quando si va al di là di stringhe, tabelle hash e alberi binari di ricerca effettuare esigenze differenti sul tipo di dati della chiave: tabelle hash richiedono una funzione di hash (una funzione dalle chiavi per i numeri interi tali che $ k_1 \ equiv k_2 \ implica h (k_1) = h (k_2) $, mentre binari alberi di ricerca richiedono un ordine totale. Gli hash a volte può essere memorizzati nella cache, se c'è abbastanza spazio nella struttura dati in cui la chiave è il negoziod; cache il risultato di confronti (un'operazione binaria) è spesso impraticabile. D'altra parte, i confronti possono beneficiare di abbreviare: se le chiavi spesso differiscono nei primi byte, un confronto negativo può essere molto veloce

.

In particolare, se si sta andando ad avere bisogno della ordine sui tasti, per esempio se si vuole essere in grado di elencare le chiavi in ??ordine alfabetico, quindi tabelle hash sono di alcun aiuto (si 'll necessità di ordinarli), mentre si può semplicemente attraversare un albero di ricerca in ordine.

È possibile combinare binario alberi di ricerca e tabelle hash in forma di alberi di hash . Un albero hash memorizza chiavi in ??un albero di ricerca in base alla loro hash. Questo è utile, per esempio, in un linguaggio di programmazione puramente funzionale in cui si desidera lavorare su dati che non ha una relazione d'ordine semplice da calcolare.

Quando le chiavi sono stringhe (o interi), un trie può essere un'altra opzione. Un trie è un albero, ma indicizzato in modo diverso da un albero di ricerca: si scrive la chiave in binario, e andate a sinistra per un 0 e buoni per una 1. Il costo di un accesso è quindi proporzionale alla lunghezza della chiave. Trie possono essere compressi per rimuovere nodi intermedi; questo è noto come un trie patricia o albero radicato . alberi Radix possono sovraperformare alberi bilanciati, in particolare quando molti tasti condividono un prefisso comune.