public class SimpleHash
{
//DICHIARAZIONE DELLE VARIABILI DI ISTANZA
//tabella hash
private int[] table;
//dimensione della tabella (meglio se numero primo)
private int dim;
//METODI
// Costruttore. Inizializza le variabili di istanza
public SimpleHash(int dim) {}
// Inizializza ogni elemento della tabella a -1 (nessun valore inserito)
public void initialize() {}
//Cerca l'elemento v all'interno della tabella restituisce la posizione in cui si trova l’elemento, -1 se questo non e’ presente.
public int search(int v){}
//Inserisce l'elemento v nella tabella se la tabella non e' piena e se l'elemento non e' gia' presente
public void insert(int v){}
//Cancella l'elemento v dalla tabella se presente. Resituisce false se l'elemento non viene cancellato, true altrimenti
public boolean cancel(int v){}
//Stampa la tabella come una stringa
public String toString(){}
}
/**************************************************************************************************************************
*costruttore. Istanzia l'array con un numero di elementi pari a dim (l'array va da 0 a n-1)
*
*
Inizializza la dimensione della tabella (non sarebbe necessario avere una variabile esplicita
*
*
per la dimensione - metodo length)
*
**************************************************************************************************************************/
public SimpleHash(int dim)
{
table = new int[dim];
this.dim = dim;
}
/*******************************************************************************************************************
*Inizializza ogni elemento della tabella a -1 (nessun valore inserito) - potrei voler inserire il valore 0, *
*quindi l'inizializzazione di default (0) non va bene
*
*******************************************************************************************************************/
public void initialize()
{
for (int i = 0; i < dim; i++) table[i] = -1;
}
/*******************************************************************************************************************
* Cerca l'elemento v all'interno della tabella. Restituisce l'indice della posizione in cui e' inserito
*
* l'elemento se presente in tabella, -1 altrimenti
*
******************************************************************************************************************/
public int search(int v)
{ int key = v % dim;
int j = key;
while((table[j] != v) && (table[j] != -1) && ((j+1)%dim != key)) j = (j+1)%dim;
if(table[j] == v) return j;
else return -1;
}
/*******************************************************************************************************************
*Inserisce l'elemento v nella tabella se la tabella non e' piena e se l'elemento non e' gia' presente
*
*******************************************************************************************************************/
public void insert(int v)
{ int key = v % dim;
int j = key;
while((table[j] != v) && (table[j] != -1) && ((j+1) % dim != key)) j = (j+1) % dim;
if(table[j] == -1)
{ table[j] = v;
System.out.println("Elemento "+v+" inserito in posizione "+j);
}
else if(table[j] == v)
System.out.println("Elemeno già inserito");
else System.out.println("Impossibile inserire l'elemento: tabella piena");
}
/**************************************************************************************************************************
*Cancella l'elemento v dalla tabella se presente. Resituisce false se l'elemento non viene cancellato, true
*
*altrimenti
*
***************************************************************************************************************************/
public boolean cancel(int v)
{
int pos = search(v);
if(pos == -1) return false;
table[pos] = -1;
return true;
}
/******************************************************************************************************************
*Stampa la tabella come una stringa
******************************************************************************************************************/
public String toString()
{
String out = new String("[");
int i;
for(i = 0; i < dim-1; i++) out = out + table[i] +", ";
out = out + table[i]+"]";
return out;
}
public class SimpleHashTest
{
public static void main(String[] argv)
{
SimpleHash hash = new SimpleHash(5);
System.out.println(hash.toString());
hash.initialize();
System.out.println(hash.toString());
hash.insert(61);
System.out.println(hash.toString());
hash.insert(15);
System.out.println(hash.toString());
hash.insert(5);
System.out.println(hash.toString());
hash.insert(4);
System.out.println(hash.toString());
hash.insert(24);
System.out.println(hash.toString());
hash.insert(0);
System.out.println("Elemento 1 in posizione: "+hash.search(1));
System.out.println("Elemento 33 cancellato :" +hash.cancel(33));
System.out.println("Elemento 61 cancellato: "+ hash.cancel(61));
System.out.println(hash.toString());
System.out.println("Elemento 24 in posizione" + hash.search(24));
hash.insert(24);
System.out.println(hash.toString());
}
}
SimpleHash hash = new SimpleHash(5)
public SimpleHash(int dim)
{
table = new int[dim];
this.dim = dim;
dim
5
table
0
0
0
0
0
0
1
2
3
4
-1
0
0
0
0
0
1
2
3
4
-1
-1
0
0
0
0
1
2
3
4
-1
-1
-1
0
0
0
1
2
3
4
-1
-1
-1
-1
-1
0
1
2
3
4
}
i
table
i
table
hash.initialize();
public void initialize()
{
for (int i = 0; i < dim; i++) table[i] = -1;
}
i
table
i
table
0
1
2
5
dim
5
0
0
v
5
table
15
61
-1
-1
-1
0
1
2
3
4
0
j
key
j
hash.insert(5)
public void insert(int v)
table[j]
{
int key = v % dim;
int j = key;
1
v
5
table
15
61
-1
-1
-1
0
1
2
3
4
key
while((table[j] != v) && (table[j] != -1) && ((j+1) % dim != key))
j = (j+1) % dim;
if(table[j] == -1)
table[j]
{
table[j] = v;
System.out.println("Elemento "+v+" inserito in posizione "+j);
return;
}
0
2
v
5
table
15
61
-1
-1
-1
0
1
2
3
4
if(table[j] == v)
key
{
j
table[j]
System.out.println("Elemeno già inserito");
return;
v
5
key
0
2
j
}
System.out.println("Impossibile inserire l'elemento: tabella piena");
}
table
15
61
5
-1
-1
0
1
2
3
4
v
table
1
1
1
key
15
61
5
24
4
0
1
2
3
4
j
table[j]
v
hash.search(1)
table
1
2
1
key
15
61
5
24
4
0
1
2
3
4
j
table[j]
public int search(int v)
{
int key = v % dim;
int j = key;
v
table
while((table[j] != v) && (table[j] != -1) && ((j+1)%dim != key))
1
3
1
key
15
61
5
24
4
0
1
2
3
4
j
j = (j+1)%key;
table[j]
if(table[j] == v) return j;
return -1;
}
v
table
1
4
1
key
15
61
5
24
4
0
1
2
3
4
j
table[j]
v
table
table[j]
1
0
1
key
15
61
5
24
4
0
1
2
3
4
j
[
i
15
61
5
24
4
0
1
2
3
4
out
[15,
i
table
15
61
5
24
4
0
1
2
3
4
[15,61,
i
15
61
5
24
4
0
1
2
3
4
out
table
hash.toString()
public String toString()
out
0
1
{
String out = new String("[");
table
int i;
for(i = 0; i < dim-1; i++)
out = out + table[i] +", ";
out [15,61,5,
table
out = out + table[i]+"]";
2
i
15
61
5
24
4
0
1
2
3
4
return out;
}
out [15,61,5,24,
table
out
table
out
3
i
15
61
5
24
4
0
1
2
3
4
[15,61,5,24,
i
4
15
61
5
24
4
0
1
2
3
4
[15,61,5,24,4]
v
table
hash.search(24)
4
4
24
key
15
-1
5
24
4
0
1
2
3
4
j
table[j]
public int search(int v)
{ int key = v % dim;
v
4
0
24
key
15
-1
5
24
4
0
1
2
3
4
24
key
15
-1
5
24
4
0
1
2
3
4
j
int j = key;
while((table[j] != v) && (table[j] != -1) && ((j+1)%dim != key)) j = (j+1)%key;
table
if(table[j] == v) return j;
return -1;
table[j]
}
v
table
table[j]
4
1
j
Esempio di Soluzione
Nuova classe che specifica il tipo degli elementi della tabella hash
public class Elem
{
Ogni elemento è composto da due interi: il valore dell’elemento ed il link – posizione
private int value;
dell’elemento in cui è memorizzato il successivo elemento associato alla stessa chiave.
private int link;
public Elem()
{
value = -1;
Costruttore: inizializza entrambe le variabili d’istanza a -1. All’inizio ogni elemento avrà il
valore -1 e non ci saranno associazioni posizioni - chiavi
link = -1;
}
public int getValue()
Metodo getValue(): Restituisce il valore della variabile value
{
return value;
}
public void setValue(int value)
{
this.value = value;
Metodo setValue(int value): Assegna alla variabile value (di questo Elem) il
valore del parametro formale value
}
public int getLink()
{
Metodo getLink(): Restituisce il valore della variabile link
return link;
}
public void setLink(int link)
{
this.link = link;
}
}
Metodo setLink(int link): Assegna alla variabile link (di questo Elem) il valore
del parametro formale link
public SimpleHash(int dim)
public void insert(int v)
{
{
int j = v%dim;
table = new Elem[dim];
while((table[j].getValue() != v) && (table[j].getLink() != -1))
j = table[j].getLink();
this.dim = dim;
if(table[j].getValue() == v)
{
}
System.out.println("Elemento "+v+" gia' inserito");
public void initialize()
return;
{
}
for (int i = 0; i < dim; i++) table[i] = new Elem();
int firstFree = getFirstFree(v%dim);
}
if(firstFree == -1)
{
public int search(int v)
System.out.println("Impossibile inserire: tabella piena");
{
return;
int j = v % dim;
}
while ((table[j].getValue() != v) && (table[j].getLink() != -1))
if(firstFree != v%dim) table[j].setLink(firstFree);
j = table[j].getLink();
table[firstFree].setValue(v);
if(table[j].getValue() == v) return j;
System.out.println("Elemento "+v+" inserito in
return -1;
posizione"+firstFree);
}
}
public boolean cancel(int v)
{
public String toString()
int j = v % dim;
{
int prev = -1;
while ((table[j].getValue() != v) && (table[j].getLink() != -1))
String out = new String("[");
{
int i;
prev = j;
for(i = 0; i < dim-1; i++)
j = table[j].getLink();
}
out = out + "(" +table[i].getValue()+","+table[i].getLink()+")" +", ";
if(table[j].getValue() == v)
{
if(prev != -1)
out = out + "(" +table[i].getValue()+","+table[i].getLink()+")"+"]";
{
table[prev].setLink(table[j].getLink());
return out;
table[j].setValue(-1);
}
table[j].setLink(-1);
return true;
}
if(table[j].getLink() == -1)
{
table[j].setValue(-1);
public int getFirstFree(int from)
return true;
{
}
int j = from;
int value = table[table[j].getLink()].getValue();
while(((j+1) % dim != from) && (table[j].getValue() != -1))
int link = table[table[j].getLink()].getLink();
table[j].setValue(value);
j = (j+1)%dim;
table[table[j].getLink()].setValue(-1);
if (table[j].getValue() == -1) return j;
table[table[j].getLink()].setLink(-1);
return -1;
table[j].setLink(link);
return true;
}
}
return false;
}
public class SimpleHashTest1
{
public static void main(String[] argv)
{
SimpleHash3 hash = new SimpleHash3(5);
hash.initialize();
System.out.println(hash.toString());
hash.insert(61);
System.out.println(hash.toString());
hash.insert(15);
System.out.println(hash.toString());
hash.insert(5);
System.out.println(hash.toString());
hash.insert(4);
System.out.println(hash.toString());
hash.insert(24);
System.out.println(hash.toString());
hash.insert(0);
System.out.println("Elemento 1 in posizione: "+hash.search(1));
System.out.println("Elemento 4 cancellato :" +hash.cancel(4));
System.out.println("Elemento 61 cancellato: "+ hash.cancel(61));
System.out.println(hash.toString());
System.out.println("Elemento 24 in posizione" + hash.search(24));
hash.insert(24);
System.out.println(hash.toString());
}
}
hash.initialize();
table
-1
-1
-1
0
hash.insert(61);
table
-1
table
-1
15
61
-1
table
15
-1
-1
61
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
3
-1
4
-1
-1
-1
4
3
-1
2
-1
3
-1
5
-1
3
2
-1
1
-1
2
1
2
0
-1
61
-1
2
1
0
hash.insert(5);
-1
1
0
hash.insert(15);
-1
-1
-1
4
hash.insert(4);
table
15
2
61
0
hash.insert(24);
table
15
table
2
15
61
2
table
15
5
-1
-1
-1
5
-1
3
4
3
4
-1
4
-1
-1
-1
24
-1
4
-1
3
3
4
3
-1
2
4
3
-1
5
-1
24
2
-1
1
-1
2
1
2
0
-1
61
-1
2
1
0
hash.cancel(61);
5
1
0
hash.cancel(4);
-1
24
-1
4