I fondamenti delle tabelle hash?

https://stackoverflow.com/questions/282712

08-07-2019
|

Domanda

Sono abbastanza confuso sui concetti di base di una tabella Hash. Se dovessi codificare un hash come potrei anche iniziare? Qual è la differenza tra una tabella Hash e solo un array normale?

Fondamentalmente se qualcuno rispondesse a questa domanda penso che tutte le mie domande avrebbero una risposta: Se avessi 100 numeri generati casualmente (come chiavi), come implementerei una tabella hash e perché sarebbe vantaggioso su un array?

Psuedo-code o Java sarebbero apprezzati come strumento di apprendimento ...

Soluzione

Le risposte finora hanno contribuito a definire le tabelle hash e spiegare alcune teorie, ma penso che un esempio possa aiutarti a farti sentire meglio.

Qual è la differenza tra una tabella hash e solo un normale array?

Una tabella hash e una matrice sono entrambe strutture che consentono di archiviare e recuperare dati. Entrambi consentono di specificare un indice e di recuperare un valore ad esso associato. La differenza, come ha osservato Daniel Spiewak, è che gli indici di un array sono sequenziali , mentre quelli di una tabella hash si basano sul valore dei dati ad essi associati.

Perché dovrei usare una tabella hash?

Una tabella hash può fornire un modo molto efficiente di cercare elementi in grandi quantità di dati, in particolare dati che non sarebbero altrimenti facilmente ricercabili. ("Grande" qui significa ginormous , nel senso che richiederebbe molto tempo per eseguire una ricerca sequenziale).

Se dovessi codificare un hash come potrei anche iniziare?

Nessun problema. Il modo più semplice è inventare un'operazione matematica arbitraria che è possibile eseguire sui dati, che restituisce un numero N (di solito un numero intero). Quindi utilizza quel numero come indice in una matrice di "secchi" " e memorizza i tuoi dati nel bucket # N . Il trucco sta nel selezionare un'operazione che tende a posizionare i valori in diversi bucket in modo da renderli più facili da trovare in seguito.

Esempio: un grande centro commerciale conserva un database delle auto e dei parcheggi dei suoi clienti, per aiutare gli acquirenti a ricordare dove hanno parcheggiato. Il database memorizza make , color , targa e parcheggio . All'uscita dal negozio, un acquirente trova la sua auto inserendo la sua marca e il suo colore. Il database restituisce un elenco (relativamente breve) di targhe e parcheggi. Una scansione veloce individua l'auto dell'acquirente.

Potresti implementarlo con una query SQL:

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

Se i dati sono stati memorizzati in un array, che è essenzialmente solo un elenco, puoi immaginare di implementare la query scansionando un array per tutte le voci corrispondenti.

D'altra parte, immagina una regola di hash:

Aggiungi i codici dei caratteri ASCII di tutte le lettere nella marca e nel colore, dividi per 100 e usa il resto come valore hash.

Questa regola converte ciascun elemento in un numero compreso tra 0 e 99, essenzialmente ordinamento i dati in 100 secchi. Ogni volta che un cliente deve individuare un'automobile, è possibile eseguire il hash della marca e del colore per trovare la una benna su 100 che contiene le informazioni. Hai immediatamente ridotto la ricerca di un fattore 100!

Ora ridimensiona l'esempio con enormi quantità di dati, ad esempio un database con milioni di voci che viene cercato in base a decine di criteri. Un "buono" La funzione hash distribuirà i dati in bucket in modo da ridurre al minimo qualsiasi ulteriore ricerca, risparmiando un notevole periodo di tempo.

Altri suggerimenti

Innanzitutto, devi capire cos'è una funzione hash. Una funzione hash è una funzione che accetta una chiave (ad esempio una stringa di lunghezza arbritraria) e restituisce un numero il più unico possibile . La stessa chiave deve sempre restituire lo stesso hash. Una funzione di hashing delle stringhe davvero semplice in Java potrebbe apparire come

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

Puoi studiare una buona funzione hash su http://www.azillionmonkeys.com/qed/ hash.html

Ora, la mappa hash utilizza questo valore hash per posizionare il valore in un array. Metodo java semplicistico:

public void put(String key, Object val) {
    int hash = stringHash(s) % array.length;
    if(array[hash] == null) {
        array[hash] = new LinkedList<Entry<String, Object> >();
    }
    for(Entry e : array[hash]) {
        if(e.key.equals(key)){
            e.value = val;
            return;
        }
    }
    array[hash].add(new Entry<String, Object>(key, val));
}

(Questa mappa applica chiavi univoche. Non tutte le mappe lo fanno.)

È possibile che due diverse chiavi eseguano l'hash sullo stesso valore o due hash diversi per mappare lo stesso indice dell'array. Esistono molte tecniche per affrontarlo. Il più semplice è utilizzare un elenco collegato (o albero binario) per ciascun indice di array. Se la funzione hash è abbastanza buona, non avrai mai bisogno di una ricerca lineare.

Ora per cercare una chiave:

public Object get(String key) {
    int hash = stringHash(key) % array.length;
    if(array[hash] != null) {
        for(Entry e : array[hash]) {
            if(e.key.equals(key))
                return e.value;
        }
    }

    return null;
}

Gli hashtable sono associativi . Questa è un'enorme differenza rispetto agli array, che sono solo strutture di dati lineari. Con un array, potresti fare qualcosa del genere:

int[] arr = ...
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i] + 1);
}

Nota come stai estraendo un elemento dall'array specificando un esatto offset di memoria ( i ). Ciò contrasta con gli hashtabili, che consentono di memorizzare coppie chiave / valore, recuperando in seguito il valore in base alla chiave:

Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);

Con la tabella sopra, possiamo effettuare la seguente chiamata:

int n = table.get("Chris");

... e si assicura che n sarà valutato in 18 .

Penso che questo probabilmente risponderà alla maggior parte delle tue domande. L'implementazione di una tabella hash è un argomento abbastanza interessante, uno che Wikipedia affronta in modo passabile bene .

" Sono più interessato al modo in cui le tabelle hash cercano la chiave e come viene generata la chiave. "

L'hash trasforma un oggetto chiave in un numero. Questo si chiama "hashing" - crea un hash dall'oggetto. Vedi Funzione hash . Sommare i byte di una stringa, ad esempio, è una tecnica hash standard. Si calcola la somma modulo 2 ³² per mantenere l'hash di dimensioni gestibili. Hash dà sempre la stessa risposta. Questo è O(1).
Il numero ti dà uno "spazio" nella tabella hash. Dato un oggetto chiave arbitrario, il valore hash calcola un valore hash. Il valore hash quindi ti dà lo slot nella tabella. Di solito mod (hash, dimensione tabella) . Anche questo è O (1).

Questa è la soluzione generale. Due calcoli numerici e sei passato da un oggetto arbitrario come chiave ad un oggetto arbitrario come valore. Poche cose possono essere così veloci.

La trasformazione da oggetto a valore hash avviene in uno di questi modi comuni.

Se è un " primitivo " oggetto di 4 byte, quindi il valore nativo dell'oggetto è un numero.
L'indirizzo dell'oggetto è di 4 byte, quindi l'indirizzo dell'oggetto può essere usato come valore hash.
Una semplice funzione hash (MD5, SHA1, qualunque cosa) accumula i byte di l'oggetto per creare un numero di 4 byte. Gli hash avanzati non sono semplici somme di byte, una semplice somma non riflette abbastanza tutti i bit di input originali.

Lo slot nella tabella hash è mod (numero, dimensione della tabella).

Se quello slot ha il valore desiderato, il gioco è fatto. Se questo non è il valore desiderato, devi cercare altrove. Esistono diversi algoritmi di sondaggio popolari per cercare un posto libero nella tabella. Linear è una semplice ricerca per il prossimo spot gratuito. Quadratic è un salto non lineare che cerca uno slot libero. Un generatore di numeri casuali (con seed fisso) può essere utilizzato per generare una serie di sonde che diffonderanno i dati in modo uniforme ma arbitrario.

Gli algoritmi di sondaggio non sono O (1). Se il tavolo è abbastanza grande, le probabilità di collisione sono basse e le sonde non contano. Se il tavolo è troppo piccolo, si verificano collisioni e si verificano sondaggi. A quel punto, diventa una questione di "messa a punto e ottimizzazione" per bilanciare sondaggio e dimensioni della tabella per ottimizzare le prestazioni. Di solito allarghiamo il tavolo.

Vedi Tabella hash .

Qualcosa che non ho ancora visto specificatamente notato:

Il punto di usare una tabella hash su un array è la prestazione.

L'iterazione in un array richiede in genere ovunque da O (1) a O (x) dove x è il numero di elementi nell'array. Tuttavia, il tempo per trovare il tuo articolo sarà estremamente variabile , specialmente se stiamo parlando di centinaia di migliaia di articoli nell'array.

Una tabella hash correttamente ponderata ha in genere un tempo di accesso quasi costante di poco superiore a O (1), indipendentemente dal numero di elementi presenti nella tabella hash.

Non vorrai usare una tabella hash per 100 numeri generati casualmente.

Un buon modo di pensare alle tabelle hash è pensare alle coppie di valori. Usiamo gli studenti e diciamo che ognuno ha un numero ID studente. Nel tuo programma memorizzi informazioni sugli studenti (nomi, numeri di telefono, fatture, ecc.). Desideri trovare tutte le informazioni su uno studente utilizzando solo le informazioni di base (nome o ID studente, ad esempio).

Supponiamo che tu abbia 10.000 studenti. Se li memorizzi tutti in un array, devi scorrere l'intero array confrontando l'ID studente di ogni voce con quello che stai cercando.

Se, invece, tu " hash " (vedi sotto) il loro numero ID studente in una posizione nella matrice, quindi devi solo cercare gli studenti i cui numeri hanno lo stesso hash. Molto meno lavoro per trovare quello che volevi.

In questo esempio, supponiamo che gli ID studente siano solo numeri di 6 cifre. La nostra funzione hash potrebbe essere utilizzare solo le 3 cifre inferiori del numero come il tasto "hash". Pertanto, 232145 viene eseguito l'hashing nella posizione dell'array 145. Quindi è necessario solo un array di 999 elementi (ogni elemento è un elenco di studenti).

Questo dovrebbe essere un buon inizio per te. Ovviamente dovresti leggere un libro di testo o Wikipedia per questo tipo di informazioni. Ma presumo tu l'abbia già fatto e sei stanco di leggere.

Ecco, in breve, come funziona una tabella hash.

Immagina di avere una biblioteca, piena di libri. Se dovessi conservare i libri in una matrice, metteresti ogni libro in un punto su uno scaffale, e poi quando qualcuno ti chiedesse di trovare un libro, guarderesti attraverso tutti gli scaffali - piuttosto lentamente. Se qualcuno dicesse "libro # 12345", potresti trovarlo abbastanza facilmente, però.

Diciamo invece che dici, se il titolo del libro inizia con 'A', va nella riga 1. Se la seconda lettera è 'B', va nella riga 1, rack 2. Se la terza lettera è 'C ', va nella riga 1, rack 2, scaffale 3 ... e così via fino a quando non si identifica la posizione del libro. Quindi, in base al titolo del libro, potresti sapere esattamente dove dovrebbe essere.

Ora, ci sono alcuni problemi nel semplicistico "hashing" algoritmo che ho descritto - alcuni scaffali saranno sovraccaricati mentre altri rimangono vuoti, alcuni libri saranno assegnati allo stesso slot .. quindi le vere funzioni di hash sono costruite con cura per cercare di evitare tali problemi.

Ma questa è l'idea di base.

Risponderò a quella parte sulla differenza tra una tabella hash e un array ... ma poiché non ho mai implementato un algoritmo di hash di alcuna importazione prima, lo lascerò a qualcuno più esperto:)

Un array è solo un elenco ordinato di oggetti. L'oggetto stesso non ha molta importanza ... l'importante è che se si desidera elencare gli oggetti in ordine di inserimento, è sempre lo stesso (il che significa che il primo elemento sempre ha un indice di 0).

Per quanto riguarda un hashtable, che è indicizzato da chiavi, non da ordine ... Penso che una ricerca di base sugli algoritmi di hashing ti darà molte più informazioni di quante io possa ... Wikipedia ne ha una molto decente ... che determina "benna" in cui le chiavi vanno per un rapido recupero su oggetti arbitrari usati come chiavi.

Per quanto riguarda i vantaggi: se l'ordine di inserimento è importante, è necessario un array o un tipo di elenco ordinato. Se la ricerca rapida tramite chiave arbitraria (codificata da varie funzioni hash) è importante, allora una tabella hash ha senso.

[Questa è la risposta a un commento fatto da me.yahoo.com/a sopra]

Dipende dalla tua funzione hash. Supponiamo che la tua funzione hash esegua l'hashing di una parola secondo la lunghezza della tua parola, la chiave per chris sarà 5. Allo stesso modo, anche la chiave per yahoo sarà 5. Ora, entrambi i valori (chris e yahoo) saranno inferiori a 5 (cioè in un 'secchio' digitato da 5). In questo modo non è necessario rendere un array uguale alla dimensione dei dati.

La domanda, credo, ha una risposta abbastanza chiara e in molti modi diversi ormai.

Vorrei solo aggiungere un'altra prospettiva (che potrebbe confondere anche un nuovo lettore)

A un livello di minima astrazione, le matrici sono solo blocchi contigui di memoria. Dato l'indirizzo iniziale ( startAddress ), dimensione ( sizeOfElement ) e indice di un singolo elemento, l'indirizzo dell'elemento viene calcolato come:

elementAddress = startAddress + sizeOfElement * index

La cosa interessante da notare qui è che le matrici possono essere astratte / visualizzate come tabelle hash con indice come chiave e la funzione sopra come funzione hash che calcola la posizione di un valore in O (1)

La tabella hash è una struttura di dati creata per una rapida ricerca.

Le tabelle hash non sono efficaci quando il numero di voci è molto piccolo.

riferimento

Alcuni esempi:

    import java.util.Collection;
    import java.util.Enumeration;
    import java.util.Hashtable;
    import java.util.Set;

    public class HashtableDemo {

    public static void main(String args[]) {

// Creating Hashtable for example

     Hashtable companies = new Hashtable();


// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map

     companies.put("Google", "United States");
     companies.put("Nokia", "Finland");
     companies.put("Sony", "Japan");


// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable

     companies.get("Google");


// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable

     System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));


// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value

      System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));


// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values

      Enumeration enumeration = companies.elements();

      while (enumeration.hasMoreElements()) {
      System.out.println("hashtable values: "+enumeration.nextElement());
      }


// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java

       System.out.println("Is companies hashtable empty: "+companies.isEmpty());


// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java

      System.out.println("Size of hashtable in Java: " + companies.size());


// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java

      Set hashtableKeys = companies.keySet();


// you can also get enumeration of all keys by using method keys()

      Enumeration hashtableKeysEnum = companies.keys();


// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection

      Enumeration hashtableValuesEnum = companies.elements();


      Collection hashtableValues = companies.values();


// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.

       companies.clear();
      }
     }

Output:

Does hashtable contains Google as key: true

Does hashtable contains Japan as value: true

hashtable values: Finland

hashtable values: United States

hashtable values: Japan

Is companies hashtable empty: false

Size of hashtable in Java: 3

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow