Hash: tabelle, elenchi e mappe, oh mio?

Question

Ho cercato di trovare alcune definizioni di di calcestruzzo (laico, non superaccademico) per i vari tipi di strutture di dati hash, in particolare tabelle hash, elenchi di hash e mappe di hash. Le ricerche online forniscono molti link utili a tutti questi, ma non forniscono mai definizioni chiare di quando è opportuno utilizzarle tutte le altre.

(1) Da un punto di vista pratico, qual è la differenza tra questi 3?

(2) In che modo differiscono i tempi di esecuzione delle loro operazioni? Ci sono casi chiari in cui uno dovrebbe essere usato o evitato rispetto agli altri tipi di hash?

(3) In che modo ciascuno di questi si riferisce all'ADT della mappa? Sono tutti solo implementazioni diverse di esso, o bestie diverse del tutto?

Grazie per qualsiasi informazione qui!

Answer 1

C'è una struttura dati astratta che contiene il mapping tra chiavi e valori. Ha diversi nomi, tra cui Map, Dictionary, Table, Association Table e altro.

Le operazioni di base che dovrebbero essere supportate da questa struttura dati sono l'aggiunta, la rimozione e il recupero di un valore, data la sua chiave associata. Ci sono variazioni e aggiunte attorno a questo concetto di base - ad esempio, alcune strutture supportano l'iterazione su tutte le coppie chiave-valore, alcune strutture supportano più valori per chiave, ecc. C'è anche una differenza nella complessità di tempo e spazio tra le varie implementazioni.

Delle molteplici implementazioni disponibili per questa struttura dati, alcuni dei più popolari utilizzano hash functions per tempi di accesso rapidi. Tali implementazioni sono talvolta denominate con il nome Hash Table o Hash Map, è possibile read more about them in Wikipedia. Le prestazioni variano anche tra le implementazioni delle tabelle hash, con alcune operazioni di inserimento O (1) e complessità di accesso ammortizzate (per il prezzo di un sacco di spazio utilizzato).

A elenco di hash, d'altra parte, è una cosa diversa, ed è più sull'uso di una struttura di dati, che le sue strutture effettive. Una lista di hash è di solito solo una lista regolare di valori hash, niente di speciale. Viene utilizzato per verificare l'integrità di una grande quantità di dati, in questo caso consente di verificare in modo indipendente vari blocchi di dati, consentendo di correggere o recuperare solo i blocchi danneggiati. Questo è in contrasto con l'utilizzo di un singolo valore hash per cancellare l'intero pezzo di dati, nel qual caso un errore significa che tutti i dati devono essere riparati o recuperati di nuovo.