Vantaggi di Binary Search Trees oltre Hash Tables

StackOverflow https://stackoverflow.com/questions/4128546

Domanda

Quali sono i vantaggi di alberi binari di ricerca su tabelle hash?

Le tabelle hash può cercare qualsiasi elemento nel Theta (1) tempo ed è altrettanto facile per aggiungere un elemento .... ma non sono sicuro dei vantaggi che vanno viceversa.

È stato utile?

Soluzione

Ricordate che Binary Search Trees (di riferimento-based) sono la memoria-efficiente. Essi non riservano più memoria di cui hanno bisogno per.

Per esempio, se una funzione hash ha una gamma R(h) = 0...100, allora è necessario allocare una matrice di elementi 100 (puntatori-a), anche se sono solo hashing 20 elementi. Se si sceglie di usare un albero binario di ricerca per memorizzare le stesse informazioni, si potrebbe allocare solo tanto spazio quanto il necessario, così come alcuni metadati relativi collegamenti.

Altri suggerimenti

Un vantaggio che nessun altro ha le punte è che albero binario di ricerca consente di effettuare ricerche in modo efficiente gamma.

Al fine di illustrare la mia idea, voglio fare un caso estremo. Dire che si desidera ottenere tutti gli elementi le cui chiavi sono tra 0 e 5000. E in realtà c'è solo un tale elemento e 10000 altri elementi le cui chiavi non sono nel range. BST può fare ricerche gamma molto efficiente in quanto non cerca una sottostruttura che è impossibile avere la risposta.

Mentre, come si può fare ricerche gamma in una tabella hash? Si sia bisogno di iterare ogni spazio della benna, che è O (n), o se si deve guardare per se ciascuno di 1,2,3,4 ... fino a 5000 esiste. (Per quanto riguarda i tasti compresi tra 0 e 5000 sono un insieme infinito? Per esempio i tasti possono essere decimali)

Un "vantaggio" di un albero binario è che può essere attraversato all'elenco fuori tutti gli elementi in ordine. Questo non è impossibile con una tabella di hash, ma non è un disegno funzionamento normale uno in una struttura hash.

In aggiunta a tutti gli altri commenti buoni:

Le tabelle hash, in generale, hanno un migliore comportamento della cache che richiede meno memoria letture rispetto ad un albero binario. Per una tabella di hash che normalmente incorrere in una sola lettura prima di avere accesso a un riferimento di tenuta dei dati. L'albero binario, se è una variante equilibrato, richiede qualcosa nell'ordine di k * lg (n) memoria letture per una costante k.

D'altra parte, se un nemico conosce il vostro hash-function il nemico può far valere la vostra tabella di hash per rendere le collisioni, ostacolando notevolmente le sue prestazioni. La soluzione è quello di scegliere l'hash-function a caso da una famiglia, ma un BST non ha questo svantaggio. Inoltre, quando la pressione tabella hash cresce troppo, spesso si tende a enlargen e riallocare la tabella di hash che può essere un'operazione costosa. La BST ha un comportamento più semplice qui e non tende a allocare improvvisamente un sacco di dati e di fare un'operazione di rimaneggiamento.

Gli alberi tendono ad essere l'ultima struttura di media dei dati. Essi possono agire come liste, può facilmente essere diviso per il funzionamento in parallelo, hanno rapida rimozione, inserimento e ricerca dell'ordine di O (lg n) . Non fanno nulla in particolare bene, ma non hanno alcun comportamento eccessivamente male.

Infine, i BST sono molto più facili da implementare in (puri) linguaggi funzionali rispetto ai hash-tabelle e non richiedono aggiornamenti distruttivi da attuare ( persistenza argomento da Pascal sopra).

I principali vantaggi di un albero binario su una tabella di hash è che l'albero binario ti dà due operazioni aggiuntive non si può fare (facilmente, rapidamente) con una tabella di hash

  • trova l'elemento più vicino al (non necessariamente uguale a) un valore arbitrario chiave (o vicini sopra / sotto)

  • iterazioni all'interno del contenuto della pianta in modo ordinato

I due sono collegati -. L'albero binario mantiene il suo contenuto in un modo ordinato, quindi le cose che richiedono che modo ordinato sono facili da fare

A (equilibrato) albero binario di ricerca ha anche il vantaggio che la sua complessità asintotica è in realtà un limite superiore, mentre i tempi di "costante" per le tabelle hash sono volte ammortizzato: Se si dispone di una funzione di hash non idonei, si potrebbe finire degradanti al tempo lineare, piuttosto che costante.

Una tabella hash si occupano più spazio quando viene creato - avrà slot disponibili per gli elementi che devono ancora essere inseriti (anche se non sono mai inseriti), un albero binario di ricerca sarà solo grande come ha bisogno di essere. Inoltre, quando un hash-table ha bisogno di più spazio, espandendo ad un'altra struttura potrebbero essere che richiede tempo, ma che potrebbe dipendere l'attuazione.

Un albero binario di ricerca può essere implementato con un persistente di interfaccia, in cui un nuovo albero viene restituito, ma il vecchio albero continua ad esistere. Implementato con attenzione, gli alberi vecchi e nuove azioni maggior parte dei loro nodi. Non si può fare questo con una tabella di hash standard.

Un albero binario è più lento di cercare e inserire, ma ha la caratteristica molto piacevole di attraversamento l'infisso che essenzialmente significa che è possibile scorrere i nodi dell'albero in un modo ordinato.

scorrendo le voci di una tabella hash semplicemente non ha molto senso, perché sono tutti sparsi in memoria.

BST forniscono anche il "findPredecessor" e le operazioni "findSuccessor" (per trovare il prossimo più piccolo e successivi elementi più grandi) a O (log n) tempo, che potrebbe anche essere operazioni molto a portata di mano. Hash Table non può fornire in quel tempo l'efficienza.

Cracking l'intervista Coding, 6a edizione

Si può implementare la tabella hash con un albero binario di ricerca bilanciato (BST). Questo ci dà un tempo di ricerca O (log n). Il vantaggio di questo è potenzialmente utilizza meno spazio, poiché allochiamo più un grande array. Possiamo anche scorrere le chiavi in ??ordine, che può essere talvolta utili.

Se si desidera accedere ai dati in maniera ordinata, quindi una lista ordinata deve essere mantenuta in parallelo alla tabella hash. Un buon esempio è dizionario in .NET. (Vedi http://msdn.microsoft.com/en-us/library/3fcwy8h6 aspx ).

Questo ha l'effetto collaterale di non solo rallentare inserti, ma consuma una grande quantità di memoria di un b-albero.

Inoltre, dal momento che un b-albero è ordinato, è semplice da trovare intervalli di risultati, o per eseguire le unioni o le unioni.

Dipende anche l'uso, Hash permette di localizzare corrispondenza esatta. Se si desidera eseguire una query per una gamma allora BST è la scelta. Supponiamo di avere un sacco di e1 dati, E2, E3 ..... it.

Con tabella hash è possibile individuare qualsiasi elemento in tempo costante.

Se si vuole trovare valori di range maggiore di E41 e meno di E8, BST può trovare rapidamente quello.

La cosa fondamentale è la funzione di hash utilizzato per evitare una collisione. Naturalmente, non possiamo assolutamente evitare una collisione, nel qual caso si ricorre al concatenamento o altri metodi. Questo rende il recupero più tempo costante nel peggiore dei casi.

Una volta pieno, tabella hash deve aumentare le sue dimensioni secchio e copiare tutti gli elementi di nuovo. Questo è un costo aggiuntivo non presente nel corso BST.

Un hashmap è un array associativo set. Quindi, la matrice di valori di input viene riunito in secchi. In uno schema di indirizzamento aperto, si dispone di un puntatore a un secchio, e ogni volta che si aggiunge un nuovo valore in un secchio, è scoprire dove nel secchio ci sono spazi liberi. Ci sono alcuni modi per fare questo- si avvia all'inizio del secchio e incrementare il puntatore ogni volta e verificare se la sua occupato. Questo si chiama scansione lineare. Quindi, si può fare una ricerca binaria come add, dove il doppio della differenza tra l'inizio del secchio e dove il doppio verso l'alto o verso il basso ogni volta che siete alla ricerca di uno spazio libero. Questo si chiama quadratica sondaggio. OK. Ora i problemi in entrambi questi metodi è che se il secchio trabocca nella prossima indirizzo secchi, allora avete bisogno di -

  1. Doppia ciascuno secchi Grandezza- malloc (N secchi) / modificare il FUNCTION- hash Tempo di percorrenza: dipende dalla implementazione malloc
  2. Trasferimento / Copia ciascuno dei dati di benne precedenti nei nuovi dati secchi. Questa è un'operazione O (N) dove N rappresenta i dati interi

OK. ma se si utilizza un LinkedList non ci dovrebbe essere un problema giusto? Sì, In legata liste non si dispone di questo problema. Considerando ciascun segmento per iniziare con una lista collegata, e se si dispone di 100 elementi in un secchio si richiede di attraversare quei 100 elementi per raggiungere la fine della LinkedList quindi la List.add (elemento E) avrà tempo per -

  1. Hash l'elemento ad un normale Secchia come in tutte le implementazioni
  2. Prendetevi il tempo per trovare l'ultimo elemento in detta Secchia-O funzionamento (N).

Il vantaggio della implementazione LinkedList è che non è necessario l'operazione di allocazione di memoria e O (N) trasferimento / copia di tutti i secchi, come nel caso della realizzazione di indirizzamento aperto.

Quindi, il modo per ridurre al minimo la O (n) è quello di convertire l'implementazione a quella di un Binary Search albero dove trovano operazioni sono O (log (N)) e si aggiunge l'elemento nella sua posizione sulla base di esso di valore . La caratteristica aggiunta di un BST è che si tratta allineati!

Hash Tables non sono buone per l'indicizzazione. Quando si è alla ricerca di un intervallo, i BST sono migliori. Questo è il motivo per cui la maggior parte degli indici di database utilizzano alberi B +, invece di Hash Tables

alberi binari di ricerca sono buona scelta per implementare dizionario se i tasti hanno un qualche ordine totale (chiavi sono confrontabili) definita su di loro e si desidera conservare le informazioni di ordine.

Come BST conserva informazioni di ordine, vi fornisce quattro ulteriori operazioni di set dinamico che non possono essere eseguite (efficiente) utilizzando le tabelle hash. Queste operazioni sono:

  1. max
  2. Minimo
  3. Successore
  4. predecessore

Tutte queste operazioni, come ogni operazione BST hanno tempo la complessità di O (H). Inoltre, tutte le chiavi memorizzate rimangono ordinati nel BST permettendo così di ottenere la sequenza ordinata delle chiavi solo attraversando l'albero in in-ordine.

In sintesi, se invece si è operazioni di inserimento, cancellare e rimuovere poi tabella di hash è imbattibile (la maggior parte del tempo) in termini di prestazioni. Ma se volete una o tutte le operazioni sopra elencate è necessario utilizzare un BST, preferibilmente un BST di auto-bilanciamento.

alberi binari di ricerca può essere più veloce quando viene utilizzato con chiavi stringa. Soprattutto quando le stringhe sono lunghe.

alberi binari di ricerca utilizzando i confronti per meno / più, che sono veloci per le stringhe (quando non sono uguali). Quindi un BST può rispondere rapidamente quando non viene trovata una stringa. Quando è trovata avrà bisogno di fare solo una comparazione completa.

In una tabella hash. È necessario calcolare l'hash della stringa e questo significa che è necessario passare attraverso tutti i byte almeno una volta per calcolare l'hash. Poi di nuovo, quando viene trovata una voce corrispondente.

vantaggio principale di tabella di hash è che lo fa quasi tutti i ops in ~ = O (1). Ed è molto facile da capire e implementare. Lo fa risolvere molti problemi "intervista" in modo efficiente. Quindi, se volete per rompere un colloquio di codifica, fare la migliore amica di tabella hash; -)

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top