Newsgroup: it.comp.java
Titolo: hashtable

Salve,
dovrei utilizzare l'oggetto hashtable, qualcuno sa dirmi come vengono
gestiti eventuali conflitti nelle entrate delle tabelle di hash. L'unica
informazione che ho trovato sui manuali e' che la probabilita' che due campi
chiavi diversi generino codici di hash uguali e' molto bassa pero' non
dicono come viene gestita la situazione quando cio' accade.
Grazie Roberto

:

Se ti interessa sapere se i tuoi dati rimangono, come in tutte le
implementazioni hash c'e' una gestione delle collisioni che degrada le
performance ma garantisce che non vengano perse entry. 
Se vuoi l'algoritmo preciso di gestione delle collisioni, dai un'occhiata
ai sorgenti - sono installabili con ogni JDK. 
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun/

Forse non mi sono spiegato bene. Non mi interessa tanto sapere come Java
gestisce le collisioni, ma come  faccio io a sapere che si sono verificate
delle collisioni e come faccio a recuperare  (con quali metodi) gli elementi
presenti nella lista di collisione associati allo stesso codice di hash.
Grazie Roberto.

:

Momento: 'sta gestione te la fa la tavola hash, che e' li' apposta. Non devi 
fare un bel nulla, sono solo le prestazioni che decadono: per recuperare gli 
elementi i metodi che usi sono sempre gli stessi (Hashtable.get(key)).
Se invece indendi proprio sapere quando e se sono avvenute collisioni - questi, 
e tanto piu' il formato della struttura che gestisce le collisioni, sono 
dettagli di implementazione della classe a cui non puoi accedere. 
Puoi provare, dall'esterno, ad usare containsKey(key). Se l'hash di key e' 
uguale a quello di un'altro oggetto che e' stato gia' usato come chiave, la 
tavola rispondera' true o  false.. ma *in dipendenza dall'implementazione*. 
Implementazioni diverse di Hashtable potrebbero dare risposte diverse.


 presenti nella lista di collisione associati allo stesso codice di hash.
...mi sa che se infili due oggetti con lo stesso codice di hash, l'ultimo
inserito soppianta il primo...
Ciao,
    Stefano


Al contrario di quanto detto da Roberto, inserendo più elementi con lo
stesso hashcode, i nuovi elementi non vanno a sostituire quelli nuovi. Tutti
gli elementi inseriti rimangono.
L'hashcode ha l'unica funzione di consentire una ricerca più veloce
dell'elemento cercato, così il fatto che ci siano altri elementi con il
medesimo hashcode non è così importate. In teoria tutti gli elementi
potrebbero anche avere il medesimo hashcode, certo la cosa non sarebbe molto
furba perché in tal caso anziché fare una ricerca binaria di un elemento,
bisognerebbe fare una ricerca sequenziale con un forte decadimento delle
prestazioni. Se ci sono due o tre elementi con la medesima hashcode così non
è un problema, penso che in generale le prestazioni non decadono così tanto.
Certo è buona norma del programmatore riuscire a trovare un hashcode veloce
da generare e che per diversi oggetti sia abbastanza vario.
Non conosco nessun metodo che dica se in una hashtable esiste un elemento
con un determinato hashcode. L'unico modo per fare questo controllo sarebbe
quindi quello di scandire tutti gli oggetti che fungono da chiavi e
verificare se ve ne è uno con l'hashcode cercato. Ne vale la candela?
Ciao,
Davide

 cercato. Ne vale la candela?
Evidentemente in alcuni casi si, visto che e' proprio il metodo che
utilizza l'implementazione JDK1.1: il metodo come gia' precedentemente
detto si chiama containsKey() e ha una struttura simile alla seguente:
	for (...)
	    if ((el.hash == hash) && el.key.equals(key))
		return true;
Ciao,
      Bruno.
--
Bruno Bossola, a Java Developer
Sent via Deja.com 
http://www.deja.com/
Before you buy.

 return true;
Ma questo non risponde alla seguente domanda.
Ho un oggetto chiave so che il suo hashcode è pippo. Esisteno nella tabella
altri elementi le cui chiavi hanno l'hashcode uguale a pippo?
A questa domanda si può rispondere comunque facendo una scansione delle
chiavi e cercare se una di queste ha il'hashcode pari a pippo.
Questo è quello che intendevo io quando dicevo che non c'è nessun metodo che
mi permette di fare questo.
Spero di non avervi annoiato con questa lunga lettera. Magari fatemi sapere
se con altre implementazioni il mio bel programmino che ho scritto sopra non
funziona nel mio stesso modo.
Grazie a tutti per l'attenzione.
Ciao
Davide

 funziona nel mio stesso modo.
Si, e' proprio cosi'. L'ADT hashtable prevede che in presenza di una
collisione venga usato l'operatore di uguaglianza per verificare esattamente
a che chiave ci si sta riferendo (scandendola presumibilmente da una lista -
ed ecco lo scadimento di prestazioni). Se non solo il codice hash della
chiave e' uguale, ma anche la chiave stessa, l'inserimento e' (com'e'
corretto anche dal punto di vista intuitivo) una sostituzione.
Aggiungo solo che c'e' una tecnica alternativa, che penalizza la
complessita' in spazio invece che in tempo - che' e' quella di eseguire un
rehashing quando c'e' una collisione (o quando la lista di elementi
associati ad una qualunque delle entry supera un certo numero). Il trucco e'
di usare l'hashvalue della chiave *insieme* ad un valore dipendente dalla
tabella stessa per generare l'hash effettivo che identifica l'entry - con
una trasformazione che garantisca l'unicita'. I dettagli non sono elementari
(come sempre si deve scegliere attentamente la funzione di hashing
"secondario", ma con quest'implementazione si riesce a mantenere un limite
superiore costante alla velocita' di retrieval, a prescindere dal numero di
elementi - il tutto ovviamente piuttosto costoso in termini di spazio. :)

 Grazie Roberto
Mi pare che nella documnetazione della classe in questione c'è
scritto che in caso di conflitto l'oggetto "vecchio" esce dalla tabella hash
venendoti restituito da metodo.
Mi pare che fosse una cosa del genere:
vecchiooggetto=H.put(nuovooggetto);
if ( vecchiooggetto == null) {
    // nuovo oggetto non esisteva in H
}
--
------------------------------------------------------------
Fabrizio Sebastiani, 
http://web.tiscalinet.it/fsebasti
fseb...@europe.com
------------------------------------------------------------