Ho controllato la pagina di Wikipedia this, ma ancora non lo capisco. Qualcuno può aiutare la mia mente ottusa a comprendere i concetti di hashing, hashtable/hashmap e hash? Alcuni esempi potrebbero davvero aiutare.Che cos'è una funzione hash in java?
L'articolo di Wikipedia avrà molte informazioni tecniche, ma una visione semplicistica dell'hash è simile alla seguente.
Immagina che ci sia una funzione magica che può dare un numero a qualsiasi oggetto. Dato lo stesso oggetto, restituisce sempre lo stesso numero.
Immediatamente ora avete un modo rapido per testare se due oggetti sono gli stessi: chiedere questa funzione per i loro numeri e confrontare. Se sono diversi, allora non sono la stessa cosa.
Ma se hanno lo stesso numero? Due oggetti diversi potrebbero avere lo stesso numero?
Sì, questo è possibile nella maggior parte degli scenari. Diciamo che la funzione può solo dare numeri tra 1..10, per esempio, e ci sono 100 oggetti diversi. Quindi ovviamente alcuni oggetti diversi devono avere lo stesso numero. Questo è ciò che viene chiamato "collisione". Una "collisione" rende il nostro test rapido di uguaglianza non altrettanto utile, quindi per quanto possibile vogliamo ridurre al minimo il suo verificarsi. Una buona funzione magica è quella che cercherebbe di minimizzare il numero di "collisioni".
Quindi che altro si può fare con questo numero? Bene, puoi usarlo per indicizzare un array. Dato un oggetto, puoi inserirlo nell'indice dato dal numero di questa funzione magica. Questo array è essenzialmente ciò che è un hashtable; questa funzione magica è una funzione hash.
This book (e supporting video lectures) forniscono una buona spiegazione di algoritmi e strutture dati. Ci sono alcune conferenze sulle funzioni di hash (1, 2). Lo raccomanderei.
Inoltre, appena cronaca, Non proprio vero, come indicato da polygenelubricants nei commenti.hashCode(), chiamata su un'istanza di Object classe restituisce un indirizzo di questo caso particolare in memoria.
FYI, la tua FYI è una mezza verità. Da http://java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode%28%29 - "' convertendo' l'indirizzo interno dell'oggetto in un numero intero/questa tecnica di implementazione è 'non richiesto'" – polygenelubricants
Sono incuriosito. Potresti per favore essere più specifico? :) – folone
Ma questo non è un consiglio per le classi, che sovrascrive questo metodo? Invece sto parlando di istanze della classe 'Object' stessa. – folone
Una tabella hash è fondamentalmente un modo per archiviare qualsiasi cosa in una matrice e recuperarla quasi alla stessa velocità con la ricerca di qualcosa in un array tramite un indice, senza sprecare troppo spazio.
Il lavoro di una funzione di hash è (in questo contesto) per calcolare l'indice di matrice al quale verrà memorizzato un oggetto, in base al contenuto dell'oggetto. Ciò significa che deve sempre restituire lo stesso risultato per lo stesso oggetto e deve restituire risultati diversi per oggetti diversi il più possibile. Quando due oggetti diversi hanno lo stesso hash, si chiama "collisione", e devi trattare questi casi in modo speciale, il che rende l'intera operazione più lenta.
Una funzione di hash è un modo per creare una rappresentazione compatta di una quantità arbitrariamente grande di dati. In java con il metodo hashcode questo significa in qualche modo descrivere lo stato del tuo oggetto (non importa quanto grande) in un int (4 byte). E di solito è scritto per essere abbastanza veloce come spiegato di seguito.
Per semplificare in hashmap/hash, l'hashcode funge da tipo di uguaglianza economica. Prendi due oggetti a e b di tipo Foo ti dice di capire se a.equals (b) richiede 500 ms, dove calcolare un hashcode (efficiente) richiede solo 10ms. Quindi se vogliamo sapere se a.equals (b) invece di farlo direttamente prima guarderemo gli hashcode e ask fa a.hashCode() == b.hashCode(). Nota che nel nostro esempio ci vorranno solo 20ms.
A causa della definizione API di hashcode, sappiamo che se l'hashcode di a non è uguale a b allora a.equals (b) non dovrebbe mai essere vero. Quindi nel nostro test precedente se vediamo che gli hashcode non sono uguali, non abbiamo mai bisogno di eseguire il test .equals() più lungo, questo è il motivo per cui si deve sempre sovrascrivere hashCode ed equivale allo.
Si possono anche vedere riferimenti sulla scrittura di hash "buono" o "ben distribuito". Questo ha a che fare con il fatto che l'inverso delle precedenti affermazioni su hashcode ed equals non è vero. Più precisamente a.hashCode() == b.hashCode() non implica necessariamente a.equals (b) Quindi l'idea di un buon codice hash riduce la probabilità di a.hashCode() == b.hashCode () quando a.equals (b) è falso. Potresti averlo visto come collisione di una funzione di hash.
Torna a hashmaps/tabelle. Questi sono basati su coppie chiave/valore. Quindi quando aggiungi o recuperi un valore, fornirai una chiave. Quindi la prima cosa che la mappa deve fare è cercare la chiave, il che significa trovare qualcosa che equivale() alla chiave che fornisci. Ma come abbiamo discusso sopra .equals() può essere incredibilmente lento, il che significa che i confronti possono essere notevolmente accelerati controllando prima i codici hash. Da quando gli hashcode sono ben distribuiti, dovresti sapere velocemente quando x è sicuramente! = Y.
Ora oltre alle hashmaps/tabelle di confronto effettivamente utilizzare gli hashcode per organizzare la loro memoria interna dei dati, tuttavia penso che sia al di là della portata di ciò che stai cercando di comprendere a questo punto.
La mappatura delle chiavi agli indici di una tabella hash si chiama funzione hash. La funzione hash contiene due parti
Mappa codice hash: Converte le chiavi in numeri interi di qualsiasi intervallo.
Mappa di compressione: Converte (porta) questi numeri interi nell'intervallo di hashtable delle chiavi.
Tratto da http://coder2design.com/hashing/
funzione Hash: Se si passa lo stesso oggetto a questa funzione un numero illimitato di volte, sia esso testo, binario o il numero, si ottiene sempre la stessa uscita. Ai fini della tabella hash viene utilizzata una funzione di hash con ritorno intero.
Sopra la funzionalità è chiamata l'hashing.
Tabella hash: struttura dati miracolosa dell'informatica che restituisce il risultato della ricerca in tempo costante o O (1). Si basa sul concetto di hashing sopra riportato. Quindi, ha un tempo di accesso migliore rispetto a elenco collegato, alberi di ricerca binaria ecc.
Perché quasi O (1): utilizza un array come struttura di base internamente per memorizzare gli oggetti e poiché gli array hanno un tempo di accesso costante, Anche il tavolo hash.
[Interno di base]: Quindi, utilizza internamente una serie di dimensioni fisse e quando si inserisce una coppia (Chiave, Valore), calcola l'hash della chiave e utilizza questo valore di hash come indice per memorizzare (Chiave, Valore) coppia nell'array. Successivamente, quando si cerca l'oggetto utilizzando la stessa chiave, viene nuovamente utilizzato l'hash della chiave come indice per cercare la chiave nell'array. Ora, due oggetti possono avere lo stesso valore di hash e quindi, mentre si inseriscono questi oggetti nella tabella hash ci sarà collisione. Esistono due modi per la risoluzione delle collisioni. È possibile fare riferimento a questo link per una discussione sufficientemente dettagliata su questo argomento.
E l'articolo su wikipedia non capisci? Altrimenti dovremmo ripetere le stesse informazioni. – polygenelubricants
L'articolo mi sembra abbastanza chiaro, quindi troverei difficile trovare una spiegazione alternativa in generale. Potresti essere più specifico su ciò che non capisci in quell'articolo? –
Un esempio di esempio o codice potrebbe aiutare almeno. –