hash Table: Delirio

[3nigma666]

Mi sto studiando le Hash Table... ma non c'ho capito un c*zzo..

Si, ovviamente ho compreso il meccanismo principe:

Hai un insieme Universo di Chiavi , la funzione h, fa si che: h: k --> ( 1 .... m )

Dome m sono gli slot di un array.

Allora fin qui è chiaro il meccanismo..se non fosse che:

1. non ho capito che sono ste chiavi, e da dove si ricavano o dove si ottengono

2.Il chaining non ho capito come funziona.

Del chaining so che ogni "slot" dell'array, invece che contenere un singolo elemento contiene una linked list.
si parla del chaining come metodo per diminuire le collisioni.
Si introduce quindi ALFA = n / m , dove alfa è detto FATTORE DI CARICO , e n rappresenta il numero di "slot" dell'array occupati e m il numero totale di slot, giusto ?

soprattutto , considerando che il costo di h(k) è O(1), xke il costo dell'hashing è TETA(1+ ALFA) ?!?!?

help .. please.. qualche anima pia mi spiega...

[franksisca]

Originariamente inviato da 3nigma666

1. non ho capito che sono ste chiavi, e da dove si ricavano o dove si ottengono

le chiavi si ottengono tipicamente dal metodo hashcode, e servono per indicizzare gli oggetti(detto in modo spicciolo).
per favre un paragone vedi le chiavi dei db, ad ogni chiave corrisponde una ed una sola tupla.
ora proprio per "evitare" questo si usa il...

Originariamente inviato da 3nigma666

2.Il chaining non ho capito come funziona.

praticamente tu non avrai una hashtable con tanti elemnenti quanti sono gli oggetti, tipo per 100 elementi avrai 10 oggetti dell'hashtable (da ora in poi HT)
quindi, facendo che inserisci gli oggetti in base alla loro decina di appartenenza, capirai che se inserisci 1 e 3, il 3 sovrasciverà l'1.

con il chaining tu crei una lista, dove metti elementi che creerebbero collisione, una specie di coda, in modo che tu accedi alla posizione che ti dice l'hashcode, se non trovi subito il tuo valore, loo cerchi nella coda.

sò di non essere stato chiarissimo, ma spero che tu riesca a comprende le mie insensate parole

[3nigma666]

Quindi se ho capito bene:

Io ho delle chiavi (ovvero degli oggetti) che devo memorizzare all'interno di una tabella (o array) detta tabella di Hash.

Questo oggetto che devo memorizzare diventa, tramite la funzione di hash, un indice del vettore ove vado a memorizzare la chiave stessa.Tipo:

Chiave: "Antonio". Con la Funzione di Hash al nome antonio viene assegnato il numero 129. Nella tabella, alla funzione 129 viene memorizzato il nome "Antonio".

Nel caso in cui Due chiavi o piu chiavi mi danno come risultato 129, allora creo una lista di oggetti all'interno della tabella alla posizione 129.

Continuo a non capire completamente l'utilità. Nel senso che se l'oggetto che devo salvare nella tabella di hash è la chiave stessa, che senso ha fare questa operazione di trasformazione in indice ?

[franksisca]

Originariamente inviato da 3nigma666

Quindi se ho capito bene:

Io ho delle chiavi (ovvero degli oggetti) che devo memorizzare all'interno di una tabella (o array) detta tabella di Hash.

Questo oggetto che devo memorizzare diventa, tramite la funzione di hash, un indice del vettore ove vado a memorizzare la chiave stessa.Tipo:

Chiave: "Antonio". Con la Funzione di Hash al nome antonio viene assegnato il numero 129. Nella tabella, alla funzione 129 viene memorizzato il nome "Antonio".

Nel caso in cui Due chiavi o piu chiavi mi danno come risultato 129, allora creo una lista di oggetti all'interno della tabella alla posizione 129.

Continuo a non capire completamente l'utilità. Nel senso che se l'oggetto che devo salvare nella tabella di hash è la chiave stessa, che senso ha fare questa operazione di trasformazione in indice ?

in linea di massima sì.

l'utilità???ricerche iperveloci (tramite il codice hash puoi utilizzare la ricerca binaria, ricerca in tempo logaritmico) e ottimizzzazione dello spazio di memoria(se ne spreca molto poco )

[franksisca]

naturalmente sono i primi due che mi sono venuti in mente.....

[3nigma666]

Originariamente inviato da franksisca

naturalmente sono i primi due che mi sono venuti in mente.....

forse mi sono espresso male.
Intendevo dire, in un esempio pratico, metti caso che voglio memorizzare in ram una stringa, tipo questa:" ciao "

Con l'hashing, Ciao viene trasformato in un indirizzo di memoria, tipo 123456 e, in questo stesso indirizzo, viene salvata la stringa ciao.

Se devo andare a controllare se la stringa ciao è salvata nella mia memoria ram sto un attimo, basta fare l'hash e vedere se la casella 123456 è occupata.

Quello che voglio capire io, è se con questo metodo io salvo effettivamente nell'array la chiave stessa ( infatti ho salvato la stringa CIAO nella posizione generata da H sulla stringa ciao ), o se si usa per salvare anche dati diversi dalla stringa stessa

[franksisca]

Originariamente inviato da 3nigma666

forse mi sono espresso male.
Intendevo dire, in un esempio pratico, metti caso che voglio memorizzare in ram una stringa, tipo questa:" ciao "

Con l'hashing, Ciao viene trasformato in un indirizzo di memoria, tipo 123456 e, in questo stesso indirizzo, viene salvata la stringa ciao.

Se devo andare a controllare se la stringa ciao è salvata nella mia memoria ram sto un attimo, basta fare l'hash e vedere se la casella 123456 è occupata.

Quello che voglio capire io, è se con questo metodo io salvo effettivamente nell'array la chiave stessa ( infatti ho salvato la stringa CIAO nella posizione generata da H sulla stringa ciao ), o se si usa per salvare anche dati diversi dalla stringa stessa

allora nell'hashtable tu salvi 2 valori:

Key e Value, quindi salvi sia la chiave che il valore, che può essere una stringa o un oggetto qualsiasi

quindi se ho capito quello che dici....si, salvi anche la chiave!!!

[3nigma666]

Originariamente inviato da franksisca

allora nell'hashtable tu salvi 2 valori:

Key e Value, quindi salvi sia la chiave che il valore, che può essere una stringa o un oggetto qualsiasi

quindi se ho capito quello che dici....si, salvi anche la chiave!!!

perfetto ti ringrazio