È possibile velocizzare una tabella hash usando gli alberi di ricerca binari per il concatenamento separato?

11

Voglio implementare una tabella hash usando gli alberi di ricerca binaria per ridurre la complessità della ricerca nel processo di concatenazione separata da O (n) (usando l'elenco collegato) a O (log n) (usando BST). Questo può essere fatto, e se sì allora come? Sarebbe più facile capire se la soluzione è passo dopo passo, l'implementazione della logica.

Voglio ridurre il tempo di ricerca nella tabella hash (costruisci usando il concatenamento separato), ma allo stesso tempo non voglio che il tempo di inserimento aumenti. Per il mio progetto non posso cambiare la funzione hash per ridurre le collisioni. Ma a causa della scalabilità, stanno accadendo collisioni. Sto cercando di trovare un rimedio, in modo che possa in qualche modo lavorare con il miglior accesso e inserire il tempo nel caso si verifichi una collisione ... cioè per gestire lo stato attuale della cosa piuttosto che per ristrutturare l'intero algoritmo. Se non funziona, dovrà ristrutturare. Quindi qualche idea?

    
posta Aviral 02.05.2015 - 13:42
fonte

2 risposte

11

Ciò che chiedi è possibile, dati i tuoi limiti.

Analisi

Il punto di forza di una tabella hash è la sua rapida ricerca e velocità di inserimento. Per ottenere quella velocità, si deve rinunciare a qualsiasi parvenza di ordine nella tabella: le voci sono tutte mescolate. Una lista è accettabile da usare come voce di una tabella perché mentre l'attraversamento è O (n), gli elenchi tendono ad essere brevi supponendo che la tabella hash sia sufficientemente grande e gli oggetti memorizzati nella tabella siano sottoposti a hashing utilizzando un algoritmo di hashing di buona qualità.

Un albero di ricerca binario (BST) ha un rapido inserimento e ricerca su O (log 2 n). Impone anche una restrizione sugli elementi che memorizza: ci deve essere un modo per ordinare gli elementi. Dati due elementi A e B memorizzati nell'albero, deve essere possibile determinare se A viene prima di B o se hanno un ordine equivalente.

Una tabella hash non impone restrizioni di questo tipo: gli elementi in una tabella hash devono avere due proprietà. In primo luogo, ci deve essere un modo per determinare se sono equivalenti; secondo, ci deve essere un modo per calcolare un codice hash deterministico. L'ordine non è un requisito.

Se gli elementi della tabella hash hanno un ordine, è possibile utilizzare un BST come voce della tabella hash per contenere oggetti con lo stesso codice hash (collisioni). Tuttavia, a causa di un BST che ha O (log 2 n) ricerca e inserimento, ciò significa che il caso peggiore per l'intera struttura (tabella hash più BST) è tecnicamente migliore rispetto all'utilizzo di un elenco come voce di tabella . A seconda dell'implementazione di BST, richiederà più spazio di archiviazione di un elenco, ma probabilmente non molto di più.

Si noti che normalmente il sovraccarico e il comportamento di un BST non portano nulla alla tabella nelle situazioni del mondo reale come bucket hash della tabella, motivo per cui la prestazione teorica di una lista è accettabile. In altre parole, la tabella hash compensa la debolezza dell'elenco inserendo meno elementi in ogni elenco (bucket). Tuttavia : il problema indicava esplicitamente che la tabella hash non può aumentare di dimensioni e che le collisioni sono più frequenti di quelle tipiche di una tabella hash.

Attuazione

Non inserirò il codice qui perché sinceramente non è veramente necessario e comunque non hai dato una lingua.

Quello che farei è semplicemente copiare qualsiasi tabella standard di hash contenuta nella libreria standard della tua lingua in una nuova classe, quindi modificare il tipo di bucket di tabella da un elenco a un albero. A seconda della lingua e della sua libreria standard, questa può essere una cosa molto banale da fare.

Normalmente non vorrei difendere la codifica di copia e incolla come questa. Tuttavia, è un modo semplice per ottenere rapidamente molto una struttura di dati testata in battaglia.

    
risposta data 02.05.2015 - 20:41
fonte
6

L'uso di un albero binario per la gestione delle collisioni in una tabella hash non è solo possibile - è stato fatto.

Walter Bright è meglio conosciuto come l'inventore del D linguaggio di programmazione , ma ha anche scritto una variante ECMAScript chiamata DMDScript . In passato, un'affermazione principale di DMDScript (o forse di un antenato - mi sembra di ricordare il nome DScript) era che i suoi hashtable tendevano a sovraperformare quelli in molte lingue simili. Il motivo: gestione delle collisioni utilizzando alberi binari.

Non ricordo esattamente da dove provenga, ma gli alberi usati erano alberi binari ingenui, senza schema di bilanciamento parziale (non AVL, rosso-nero o altro) che ha un senso assumendo che l'hashtable stessa venga ridimensionata quando diventa troppo pieno e non si ottengono tassi di collisioni hash assurdamente improbabili, gli alberi binari dovrebbero essere sempre piccoli. Fondamentalmente, il caso peggiore è sempre lo stesso dell'utilizzo di un elenco collegato per la gestione delle collisioni (tranne per il pagamento del prezzo di due puntatori per nodo anziché uno), ma il caso medio riduce la quantità di ricerca all'interno di ciascun bucket hash.

    
risposta data 02.05.2015 - 21:30
fonte

Leggi altre domande sui tag