(Java) insiemi o set

  • 0 Risposte
  • 2472 Visite

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline aduri

  • Nuovo Iscritto
  • *
  • 18
(Java) insiemi o set
« il: 05 Novembre 2006, 16:14 »
Salve a tutti.

Da quello che ho capito l'implementazione dell'insieme o set viene realizzato
con una tabella hash ed un array di LinkedList.
La tabella crea n (numeri primi) posizioni che sono gli indici dell'array di liste
e col metodo nextPrime(n) viene restituito il numero primo successivo a quello passato come parametro.
theListOf(Object x) determina la lista che deve contenere l'oggetto x basandosi sul codice hash
di quell'oggetto.
Gentilmente qualcuno mi puo' spiegare come funziona il metodo theListOf(Object x) piu' in particolare
i passaggi:
index = index%table.length;
if(index<0)
index+=table.length;
return table[index];

sembra che divida il valore Hash per la lunghezza della tabella e da questa operazione estragga il resto.
Che senso ha?
Non si creano piu' collisioni?

Allego x completezza i codici

Grazie



Codice: [Seleziona]
public class HashSet implements Set {
List[] table;
int mod;
public HashSet() {
this(97);
}
public HashSet(int n) {
table = new LinkedList[nextPrime(n)];
for (int i=0; i<table.length; i++)
table[i]=new LinkedList();
mod=0;
}

int nextPrime(int n){
if(n>1){
boolean[] p = primes(2*n+1);
for (int i=n; i<p.length; i++)
if (p[i])
return i;
}
return 2;}
boolean[] primes(int n){
boolean[] p = new boolean[n];
for(int i=2; i<n;i++)
p[i]=true;
for(int i=2; i<n;i++){
if (p[i]!=false){
for(int j=i;(long)j*i<n;j++)
p[i*j]=false;}
}
return p;}


List theListOf(Object x){
if (x==null)
throw new IllegalArgumentException();
int index = x.hashCode();
index = index%table.length;
if(index<0)
index+=table.length;
return table[index];
}

public boolean add(Object x) {
List xlist=theListOf(x);
if (xlist.contains(x))
return false;
else{
xlist.add(x);
mod++;
return true;
}
}

public boolean remove(Object x) {
List xlist=theListOf(x);
if (xlist.remove(x)){
mod++;
return true;
}else
return false;
}
public boolean contains(Object x) {
List xlist=theListOf(x);
return xlist.contains(x);
}