(JAVA) insiemi o set

[aduri]

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

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);
}

[PGI-Bis]

questa parte qui:

int index = x.hashCode();
index = index%table.length;
if(index<0)
index+=table.length;

dal valore x passa ad un valore intero positivo che identifica una certa posizione nella struttura dati. Credo rientri nel panorama delle funzioni di hashing.

"%table.length" fa si che il codice hash dell'oggetto x, che è un intero e dunque va da meno un paio di miliardi a più altrettanto, sia ricondotto nello spazio (-(table.length - 1), +(table.length - 1)).

Poichè il valore minimo restituito dall'operatore % è -(table.length - 1) sommando table.length a index riduce lo spazio a (0, +(table.length - 1)), che è poi quello di un indice valido per accedere ad una delle liste contenute nell'array "table".

Tutto l'ambaradan non ha un problema di collisioni perchè gli elementi di table sono liste concatenate di lunghezza variabile. Ha una complessità variabile.

[aduri]

Ti ringrazio tutto abbastanza chiaro anche se % io sapevo volesse dire modulo o resto di una divisione.
Quello che ancora non mi e' chiaro e' questo passaggio "sommando table.length a index riduce lo spazio a (0, +(table.length - 1))" cortesemente potresti darmi lumi.
Lo 0 +.....? perche' 0?
Quindi se ho capito bene index ha un valore che e' il codice hash dell'oggetto che potrebbe essere inutilmente molto grande ed in questo modo viene ridotto all'interno della dimensione della tabella hash.

Grazie

[PGI-Bis]

In effetti ho detto una cacchiata :muro:

Non "sommando table.length a index riduce lo spazio a (0, +(table.length - 1))" ma "sommando table.length a index riduce lo spazio a (1, +(table.length - 1))". Se è index è zero, l'algoritmo non somma (se lo facesse eccederebbe di uno l'ultimo indice di accesso valido).

Il valore dell'espressione

"x.hashCode() % table.length"

è negativo se x.hashCode è negativo. Cioè:

int index = x.hashCode() % table.length;

può risultare in un index negativo.

Poichè index è l'indice di accesso ad uno dei componenti di un array, è chiaro che index non debba essere negativo.

Per la precisione, affinchè index sia valido deve avere un valore che va da zero a table.length - 1, estremi inclusi.

l'algoritmo dice che se index è negativo, allora somma a index il valore (positivo) table.length.

Risulta un index valido, cioè un index compreso tra 0 e table.length - 1, estremi inclusi?

Per effetto di

index = numeroQualsiasi % table.length

index ha un valore che va da -qualcosa a +qualcosa, con qualcosa pari a table.length - 1.

Se è negativo, al massimo è (table.length - 1) e come minimo è -1. E se sommi ad un numero che va da -(A - 1) a -1, con A intero positivo, ottieni un numero che va da 1 (-A + 1 + A = 1) a A - 1.

Poichè quest'ultima manfrina è condizionata a che index sia strettamente minore di zero (nel caso in cui index sia zero è lasciato così com'è) l'effetto totale è che index va da zero ad table.length - 1.

[PGI-Bis]

Per l'operatore "%" vale quanto stabilito nella documentazione del linguaggio. Produce un valore tale che:

(a/b)*b+(a%b) = a

segni compresi.

Una volta lessi che questa operazione non corrisponde esattamente al resto di una divisione ma sinceramente ignoro quale sia la differenza.

[aduri]

Grazie ora e' tutto chiaro anche per cio' che riguarda l'operatore modulo (%).
;)