Cosa sono gli hashtable e gli hashap e i loro casi d'uso tipici?

Question

Di recente mi sono imbattuto in questi termini alcune volte, ma sono abbastanza confuso su come funzionano e quando vengono di solito implementati?

Answer 1

Beh, pensaci in questo modo.

Se si utilizza un array, una semplice struttura di dati basata su indice e la si riempie di elementi casuali, la ricerca di una determinata voce diventa un'operazione sempre più costosa quando la si riempie di dati, poiché in pratica è necessario inizia a cercare da un'estremità all'altra, fino a trovare quella che desideri.

Se si desidera ottenere un accesso più rapido ai dati, si ricorre in genere a ordinare l'array e utilizzare una ricerca binaria. Ciò, tuttavia, aumentando la velocità di ricerca di un valore esistente, rallenta l'inserimento di nuovi valori, poiché è necessario spostare gli elementi esistenti quando è necessario inserire un elemento nel mezzo.

Una tabella hash, d'altra parte, ha una funzione associata che accetta una voce e la riduce a un numero, una chiave hash. Questo numero viene quindi utilizzato come indice nell'array ed è qui che si memorizza la voce.

Una tabella hash ruota attorno a un array, che inizialmente inizia vuoto. Vuoto non significa lunghezza zero, l'array inizia con una dimensione, ma tutti gli elementi dell'array non contengono nulla.

Ogni elemento ha due proprietà, dati e una chiave che identifica i dati. Ad esempio, un elenco di codici postali degli Stati Uniti sarebbe un codice postale - > nome tipo di associazione. La funzione riduce la chiave, ma non considera i dati.

Quindi, quando si inserisce qualcosa nella tabella hash, la funzione riduce la chiave a un numero, che viene utilizzato come indice in questo array (vuoto), ed è qui che si memorizzano i dati, sia la chiave che i i dati.

Quindi, in seguito, vuoi trovare una voce particolare per la quale conosci la chiave, quindi esegui la chiave attraverso la stessa funzione, ottieni la sua chiave hash e vai in quel particolare posto nella tabella hash e recupera i dati lì.

La teoria dice che la funzione che riduce la tua chiave in una chiave hash, quel numero, è computazionalmente molto più economica della ricerca lineare.

Una tipica tabella hash non ha un numero infinito di elementi disponibili per l'archiviazione, quindi il numero viene generalmente ridotto ulteriormente fino a un indice che si adatta alla dimensione dell'array. Un modo per farlo è semplicemente prendere il modulo dell'indice rispetto alla dimensione dell'array. Per un array con una dimensione di 10, l'indice 0-9 verrà mappato direttamente su un indice e l'indice 10-19 verrà nuovamente mappato su 0-9, e così via.

Alcune chiavi verranno ridotte allo stesso indice di una voce esistente nella tabella hash. A questo punto le chiavi effettive vengono confrontate direttamente, con tutte le regole associate al confronto dei tipi di dati della chiave (ad es. Confronto di stringhe normali per esempio). Se esiste una corrispondenza completa, si ignorano i nuovi dati (esistono già) o si sovrascrivono (si sostituiscono i vecchi dati per quella chiave) oppure li si aggiunge (hashtable multivalore). Se non esiste alcuna corrispondenza, ciò significa che sebbene le chiavi hash fossero identiche, le chiavi effettive no, in genere si trova una nuova posizione in cui archiviare la chiave + i dati.

La risoluzione delle collisioni ha molte implementazioni e la più semplice è quella di passare all'elemento vuoto successivo nell'array. Questa semplice soluzione presenta altri problemi, quindi trovare l'algoritmo di risoluzione giusto è anche un buon esercizio per gli hashtable.

Gli hashtable possono anche crescere, se si riempiono completamente (o si avvicinano a), e questo di solito viene fatto creando un nuovo array della nuova dimensione e calcolando ancora una volta tutti gli indici e posizionando gli elementi nel nuovo array nelle loro nuove posizioni.

La funzione che riduce la chiave a un numero non produce un valore lineare, ad es. & Quot; AAA " diventa 1, quindi "AAB" diventa 2, quindi la tabella hash non viene ordinata per valore tipico.

C'è anche un buon articolo di Wikipedia disponibile sull'argomento, qui .

Answer 2

La risposta di lassevk è molto buona, ma potrebbe contenere troppi dettagli. Ecco la sintesi. Sto omettendo intenzionalmente alcune informazioni pertinenti che puoi tranquillamente ignorare il 99% delle volte.

Non esiste nessuna differenza importante tra tabelle hash e mappe hash il 99% delle volte.

Le tabelle hash sono magiche

Scherzi a parte. È una struttura di dati magica che quasi garantisce tre cose . (Ci sono eccezioni. Puoi in gran parte ignorarle, anche se impararle un giorno potrebbe essere utile per te.)

1) Tutto nella tabella hash fa parte di una coppia: c'è una chiave e un valore . Inserisci e ottieni i dati specificando la chiave su cui stai operando.

2) Se stai facendo qualcosa con un solo tasto su una tabella hash, è incredibilmente veloce . Ciò implica che put (chiave, valore) , get (chiave) , contiene (chiave) e rimuovi (chiave) sono tutti molto veloci.

3) Le tabelle hash generiche non riescono a fare qualsiasi cosa non elencata in # 2 ! (Per "fallimento", intendiamo che sono tremendamente lenti.)

Quando utilizziamo le tabelle hash?

Usiamo le tabelle hash quando la loro magia si adatta al nostro problema.

Ad esempio, la memorizzazione nella cache finisce spesso con l'utilizzo di una tabella hash - ad esempio, supponiamo di avere 45.000 studenti in un'università e che alcuni processi debbano essere archiviati per tutti. Se fai regolarmente riferimento allo studente per numero ID, quindi un ID = > la cache dello studente ha un senso eccellente. L'operazione che stai ottimizzando per questa cache è ricerca rapida .

Gli hash sono anche straordinariamente utili per archiviare le relazioni tra i dati quando non vuoi andare in giro e modificare gli oggetti stessi. Ad esempio, durante la registrazione del corso, potrebbe essere una buona idea essere in grado di mettere in relazione gli studenti con le lezioni che frequentano. Tuttavia, per qualsiasi motivo potresti non volere che lo stesso oggetto Student lo sappia. Usa un hash studentToClassRegistration e tienilo in giro mentre fai tutto quello che devi fare.

Fanno anche una prima scelta abbastanza buona per una struttura di dati tranne quando è necessario eseguire una delle seguenti operazioni:

Quando non usare le tabelle hash

Scorri gli elementi . Le tabelle hash in genere non eseguono molto bene l'iterazione. (Quelli generici, cioè. Alcune implementazioni particolari a volte contengono elenchi collegati che vengono utilizzati per far sì che l'iterazione su di essi risulti meno efficace. Ad esempio, in Java, LinkedHashMap consente di scorrere rapidamente chiavi o valori.)

Ordinamento. Se non puoi iterare, anche l'ordinamento è un dolore reale.

Passa dal valore alla chiave . Usa due tabelle hash. Fidati di me, ti ho appena risparmiato un sacco di dolore.

Answer 3

se parli in termini di Java, entrambi sono raccolte che consentono l'aggiunta, la cancellazione e l'aggiornamento di oggetti e usano gli algoritmi Hasing internamente.

La differenza significativa, tuttavia, se parliamo in riferimento a Java, è che gli hashtable sono intrinsecamente sincronizzati e quindi sono thread-safe mentre le mappe hash non sono raccolte thread-safe.

A parte la sincronizzazione, il meccanismo interno per archiviare e recuperare oggetti è hash in entrambi i casi.

Se hai bisogno di vedere come funziona l'hashing, consiglierei un po 'di googling su Data Structers e tecniche di hashing.

Answer 4

Hashtables / hashmaps associano un valore (chiamato 'chiave' per scopi di chiarimento delle ambiguità) con un altro valore. Puoi pensarli come un tipo di dizionario (parola: definizione) o record del database (chiave: dati).