Perché utilizziamo il rilevamento lineare nelle tabelle hash quando esiste un concatenamento separato collegato con le liste?

Question

Recentemente ho appreso diversi metodi per gestire le collisioni nelle tabelle hash. E ho visto che il concatenamento separato con le liste collegate è sempre più efficiente in termini di tempo e per l'efficienza dello spazio assegniamo una memoria predefinita per il sondaggio lineare che in seguito non potremmo usare, per il concatenamento separato utilizziamo la memoria in modo dinamico, quindi il concatenamento separato con l'elenco collegato non più efficiente del sondaggio lineare? se sì, perché allora usiamo il sondaggio lineare?

Answer 1

Sono sorpreso che tu abbia visto l'hashing incatenato più veloce del sondaggio lineare: in pratica, il sondaggio lineare è in genere significativamente più veloce del concatenamento. Ciò è dovuto principalmente a locality of reference, poiché gli accessi eseguiti nella ricerca lineare tendono ad essere più vicini nella memoria rispetto agli accessi eseguiti nell'hash concatenato.

Ci sono altre vittorie nella ricerca lineare. Ad esempio, gli inserimenti in una tabella di hash lineare non richiedono alcuna nuova allocazione (a meno che non si stia ridefinendo la tabella), quindi in applicazioni come router di rete in cui la memoria è scarsa, è bello sapere che una volta impostata la tabella, gli elementi possono essere inseriti in esso senza il rischio di un errore malloc.

Uno dei punti deboli del sondaggio lineare è che, con una cattiva scelta della funzione di hash, primary clustering può causare un degrado significativo delle prestazioni della tabella. Mentre l'hashing incatenato può ancora soffrire di cattive funzioni hash, è meno sensibile agli elementi con codici hash vicini, che non influiscono negativamente sul runtime. Teoricamente, il controllo lineare fornisce solo le ricerche O (1) previste se le funzioni hash sono 5-independent o se there's sufficient entropy in the keys. Esistono molti modi per risolvere questo problema, poiché utilizzando la tecnica Robin Hood hashing o hopscotch hashing, entrambi hanno casi peggiori significativamente migliori rispetto al sondaggio lineare alla vaniglia.

L'altra debolezza del sondaggio lineare è che le sue prestazioni si riducono in modo significativo con l'avvicinarsi del fattore di carico 1. È possibile risolvere questo problema rielaborando periodicamente o utilizzando la tecnica di hashing Robin Hood sopra descritta.

Spero che questo aiuti!

Answer 2

Il sondaggio lineare è in realtà più efficiente in termini di memoria quando la tabella hash è quasi piena.

Storicamente, uno aveva una memoria molto, molto piccola, quindi ogni byte contava (e ci sono ancora alcuni casi in cui la memoria è molto limitata).

Perché utilizza meno memoria?

considerare che cosa le tabelle assomigliano: (variazioni concatenazioni separate come da Wikipedia - ci sono altre variazioni troppo, ma in genere utilizzano più memoria)

Linear    Separate chaining #1 Separate chaining #2 
probing   List head in table  Pointer in table 
|------|   |------|---|   |---| |------|---| 
|Object|   |Object|Ptr|   |Ptr| -> |Object|Ptr| 
|------|   |------|---|   |---| |------|---| 
|Object|   |Object|Ptr|   |Ptr| -> |Object|Ptr| 
|------|   |------|---|   |---| |------|---| 
| NULL |   | NULL |Ptr|   |Ptr| 
|------|   |------|---|   |---| 
.     .      . 
.     .      . 
.     .      . 

(Ptr sta per "puntatore" - ogni puntatore non puntare a qualcosa può essere considerato NULL)

Il concatenamento separato n. 1 utilizza chiaramente più memoria rispetto al sondaggio lineare (sempre), poiché ogni elemento della tabella è più grande della dimensione del puntatore.

La concatenazione n. 2 separata può avere un vantaggio quando non c'è molto nella tabella, ma quando si riempie, avrà approssimativamente 2 puntatori aggiuntivi in ​​agguato per ogni elemento.

---

templatetypedef è probabilmente ragione su scansione lineare tipicamente essere più veloce (è raramente sbagliato), ma è in genere insegnato che concatenazioni separate è più veloce, e lo si vede nelle principali API (come Java implementations, per esempio), forse perché di questo, per evitare casi in cui la scansione lineare è molto più lenta (con alcuni valori ben selezionati, è possibile ottenere rapidamente prestazioni O(n) con sondaggio lineare mentre il concatenamento separato sarebbe stato ancora O(1)), o forse per qualche altro ragionare.