Newsgroup: it.comp.java
Titolo: Strana hash table

Scusate se scrivo molto codice, ma altrimenti ho paura che non sia 
chiaro il messaggio. Sto leggendo questo codice ed ho trovato difficoltà 
nel capirene una parte. Lo scopo sarebbe quello di scrivere una classe 
che memorizzi, leggendo da file, una serie di parole, tradotte 
dall'italiano all'inglese così:
parolaitaliana parolainglese
parola2 parolatradotta2
ecc...
una per riga. Il tutto viene inserito all'interno di una tabella hash. 
Poi, da quello che ho capito, con le funzioni inItaliano(stringa) ed 
inInglese(stringa), si va a ricercare nella tabella hash se è presente 
la parola passata come parametro, ed in caso a restituire la traduzione. 
Ecco il codice che ho trovato:
public class TR2
{
	class Nodo
	{
		String chiave;
       		String attributo;
       		Nodo prossimo;
       		Nodo (String c, String a, Nodo p)
       		{
			chiave = c;
          		attributo = a;
          		prossimo = p;
		}
       	}
	private int h (String ch)
	{
    		int n = 0;
    		for (int i = 0; i < ch.length(); i++)
    			n = ((31 * n) + ch.charAt(i)) % MAX;
    		return n;
	}
	// parte privata
	private Nodo[] v;
	private static final int MAX = 97;
	public TR2 (String nome) throws IOException
	{
		BufferedReader in = new BufferedReader(new
      			FileReader(nome));
   		v = new Nodo[MAX];
   		String riga;
   		while ((riga = in.readLine()) != null)
   		{
			StringTokenizer t = new
        			StringTokenizer(riga);
     			String italiano = t.nextToken();
     			String inglese = t.nextToken();
     			int chr = h(italiano);
     			v[chr] = new Nodo(italiano, inglese, v[chr]);
     			chr = h(inglese);
     			v[chr] = new Nodo(inglese, italiano,
        			v[chr]);
     		}
   	}
	public String inItaliano(String x)
  	{
     		Nodo p = v[h(x)];
     		while (p != null)
       			if (x.compareTo(p.chiave) == 0)
         			return p.attributo;
       			else
         			p = p.prossimo;
     		return null;
   	}
   	public String inInglese(String x)
   	{
      		return inItaliano(x);
   	}
}
mi pare tutto abbastanza semplice, ad eccezione di una cosa che è però 
fondamentale. Questa tabella di hash, utilizza anche dei bucket giusto?
Cioè, la parte fondamentale è quella dentro al costruttore TR2, dove scrive:
v[chr] = new Nodo(italiano, inglese, v[chr]);
cioè, se non ho capito male, inserisce un nuovo nodo, con i nuovi valori 
  , prima di tutti quelli già presenti, giusto? L'ultimo parametro, cioè 
v[chr], viene usato come riferimento al successivo nodo. Ho capito 
correttamente?
Poi ovviamente, quando va a fare la ricerca con il metodo inItaliano, 
prende subito l'elemento dell'array dove ci dovrebbe essere il nodo che 
serve, e poi va a scandire tutta l'eventuale lista. Giusto?
Spero che sia comprensibile il messaggio, e mi scuso per la lunghezza.
Ciao a tutti.
Luca

   , prima di tutti quelli già presenti, giusto? 
<premessa>Non linciatemi se dico una boiata :)</premessa>
Perchè prima?
Non capisco il senso di questa istruzione; l'ultimo oggetto che passi come 
parametro (tipo Node), è di fatto un riferimento all'oggetto stesso che 
stai creando... e non al 'prossimo' come farebbe intendere l'analisi della 
rispettiva classe.
Di fatto anche modificando l'istruzione in:
 v[chr] = new Nodo(italiano, inglese, v[1]);
il tutto sembra funzionare correttamente.
-- 
daniele

 il tutto sembra funzionare correttamente.
Questo non lo capisco. Come puň funzionare? Non andrebbe piů avanti la 
lista secondo il ragionamento che ho fatto io. Tutti hanno lo stesso 
nodo (v[1]) come successivo, non avrebbe senso.
Che ne dici? Boh.
Grazie.
Luca

 Che ne dici? Boh.
Ok sono stato decisamente precipitoso :), ora penso di aver capito il 
tutto.
La scelta di utilizzare dei nodi fra loro collegati nasce dal fatto che la 
funzione h(s) puo' restituire valori uguali per s differenti. Qualora cio' 
si verifichi il sistema a nodi crea una "coda" con tutte le chiavi che 
hanno identica h(chiave).
La funzione di ricerca inItaliano interpella la posizione dell'array 
h(chiave) e poi intera ai nodi figli verificando che esista una 
corrispondenza tra chiave cercata e chiave-nodo.
La modifica da me proposta (...v[1]...) funziona fin tanto che nella lista 
chiavi/attributo non esistono due chiavi con h(chiave) identico.
ciao :)
-- 
daniele