Hash Table v/s Trees

Gli hash sono sempre più veloci degli alberi? Sebbene Hashtables abbia una complessità di ricerca O (1) ma supponiamo che a causa di una funzione di hash mal progettata avvenga un sacco di collisioni e se gestiamo le collisioni usando la struttura concatenata (ad esempio un albero bilanciato), il tempo di esecuzione peggiore per la ricerca sarebbe O (log n). Quindi posso concludere per set di dati grandi o piccoli anche nel caso di scenari peggiori. Le tabelle hash saranno sempre più veloci degli alberi? Inoltre, se ho ampia memoria e non desidero ricerche di intervalli, posso sempre andare a un tavolo hash?Hash Table v/s Trees

fonte

2012-04-05 avinash shah

Non sono esperto, ma direi che è situazionale. Molte funzioni di hashing sono costose e per alcuni modelli di accesso un albero è buono. –

"Sempre" è una parola così onnicomprensiva. Qualche possibilità di modificare questa domanda per ridurla a qualcosa di un po 'più specifico, come scenari specifici (solo)? Altrimenti sarà quasi certamente chiuso come non-costruttivo. –

Molte persone qui hanno menzionato che il caso peggiore sarebbe O (N). Come può essere O (n) se le collisioni vengono gestite usando una struttura ad albero bilanciata invece di una lista collegata. Il peggior caso di cercare attraverso un albero bilanciato come AVL sarebbe O (log n) –

Gli hash sono sempre più veloci degli alberi?

No, non sempre. Questo dipende da molte cose, come la dimensione della collezione, la funzione di hash e alcune implementazioni di hash table - anche il numero di operazioni di eliminazione.

hash-tables sono O(1) per op in media - ma questo non è sempre il caso. Potrebbero essere O(n) in casi peggiori.

Alcuni motivi che posso pensare in questo momento a preferire gli alberi:

Ordinare è importante. [hash-tables non mantengono l'ordine, BST è ordinato per definizione]
Latency è un problema - e non si può soffrire il O(n) che potrebbe verificarsi. [Ciò potrebbe essere fondamentale per i sistemi in tempo reale]
I dati potrebbero essere "simili" relativi alla funzione di hash e molti elementi sottoposti a hashing nelle stesse posizioni [collisioni] non sono inattaccabili. [questo può essere a volte risolto utilizzando una diversa funzione di hash]
Per raccolte relativamente piccole - molte volte la costante nascosta tra l'hashtable O(1) è molto più alta di quella dell'albero - e l'utilizzo di un albero potrebbe essere più veloce per le piccole raccolte.

Tuttavia, se i dati sono enormi, la latenza non è un problema e le collisioni non sono probabili - le tabelle hash sono asintoticamente migliori rispetto a un albero.

fonte

2012-04-05 17:56:30 amit

Spesso accade che alberi accuratamente imballati possano eseguire una tabella hash a causa della coerenza della cache (sia dalla memoria principale che dal disco). Non importa quanti dati hai in questo caso - le tabelle hash potrebbero non essere la tua migliore opzione a seconda di come stai usando la struttura del dizionario. – Kaganar

Quali tabelle hash? Aprire le tabelle hash di indirizzamento o le tabelle hash "bucket"? Con o senza ridimensionamento incrementale? Oppure basato su Hashing lineare? Ci * tante * implementazioni di hash tables in giro! La tua risposta è sbagliata per alcuni di loro, quindi per favore, sii preciso. –

@MatthieuM .: Questi sono i tradizionali svantaggi per quasi tutte le tabelle hash, anche se si utilizza l'indirizzamento aperto o il concatenamento con un array semplice come "bucket". L'ordine è un inconveniente perché l'hashing non garantisce che l'ordine rimarrà. La latenza è un problema dovuto al caso peggiore (se non si può soffrire di operazioni 'O (n)' a causa di alcuni vincoli - si tratta di un problema), il valore hash simile non è davvero un richiamo poiché può essere facilmente risolto scegliendo un diversa funzione di hash, e il problema delle dimensioni è solitamente dovuto a overhead di funzioni hash se non ricordo male. Con quale specifico problema hai? – amit

Utilizzare la tabella hash e inizializzarla con la dimensione corretta. Ad esempio se usi solo metà spazio le collisioni sono pochissime.

fonte

2012-04-05 17:55:28 dash1e

Nel peggiore dei casi si avrà O (n) di tempo in tabelle di hast. Ma questo è un miliardo meno probabile del sole che esplode scrivere ora, quindi quando si usa una buona funzione hash si può tranquillamente supporre che funzioni in O (1) a meno che il sole esploda.
D'altra parte, le prestazioni di entrambe le tabelle hash e alberi possono variare a seconda dell'implementazione, della lingua e della fase lunare, quindi l'unica buona risposta a questa domanda è "Prova entrambi, pensa a e scegli meglio".

fonte

2012-04-05 17:55:39 kilotaras

Se a causa progettato male funzione hash sacco di collisioni accadere e se gestiamo le collisioni con struttura a catena (per esempio un albero bilanciato) allora il caso peggiore tempo di esecuzione per la ricerca sarebbe O (n) (non O (log n)). Pertanto non è possibile concludere per serie di dati grandi o piccoli, anche nel caso di scenari peggiori. Le tabelle hash saranno sempre più veloci degli alberi.

fonte

2012-04-05 17:56:38

risposta

Problemi correlati