PDA

Visualizza la versione completa : [definizione] hash...


alfdev
15-04-2005, 16:08
Salve a tutti,

volevo chiedere cosa sono le hashtable?
e cosa ovviamente un codice hash?

Grazie 1000

dekdek
15-04-2005, 16:18
Un codice hash e' una rappresentazione sintetica di un dato.
Dato un certo valore, vi si applica una certa funzione che genera l'hashcode.
Questo codice rappresenta un mezzo per effettuare una memorizzazione ed una lettura ultra-rapida di tale dato. Il tutto al costo di possibili sprechi di spazio.

Una hashtable e' un vettore (o una lista o qualsiasi altro tipo aggregato) in cui la memorizzazione e la lettura viene fatta in base al codice hash di un dato.
Se ad esempio inserisci "Luigi" in una hashtable, e mettiamo che hash("Luigi") = 36, allora "Luigi" sara' inserito alla posizione 36. Quando dovrai andare a leggere "Luigi" ti bastera' ricalcolare l'hash e andare a leggere la casella designata.

Il casino e' quando due dati hanno lo stesso hash. Bisogna creare delle catene di puntatori ed allocare spazio extra...
Per questo sono stati studiati metodi che rendono la distribuzione degli hash il piu' possibile uniforme.

Sto un po' semplificando le cose, ovviamente...

alfdev
15-04-2005, 16:22
grazie 1000, sei stato chiarissimo, sto studiando java 2 e con le collection il libro introduce le hashtable...

grazie ancora:)

dekdek
15-04-2005, 16:41
Prego.

Una cosa che non si evince da quello che ho scritto e' che "Luigi" non deve essere necessariamente l'oggetto da memorizzare. E' una chiave, quindi potrebbe essere anche solo una parte dell'oggetto (quella su cui voglio calcolare l'hash, o meglio, quella su cui poi andro' a fare le ricerche) o potrebbe addirittura non appartenere del tutto all'oggetto vero e proprio...
Un esempio (anche se l'hash non c'entra...): nelle memorie associative che spesso si usano come cache, memorizzi i dati piu' recentemente acceduti in memoria, ma la chiave e' l'indirizzo da cui ha letto quei dati, che non fa propriamente parte del dato.

alfdev
15-04-2005, 17:16
beh complimenti per l'esempio...grazie 1000, sembrano davvero potenti queste hashtable...dinuovo grazie!

complimenti per le tue conoscenze ovviamente!

dekdek
15-04-2005, 17:26
:) Eh, quanto meno servono a qualcuno...
Sai com'e', a Ingegneria si divertono a imbottirti... :fagiano:

Loading