È il modo con cui sono realizzati gli HashSet
Si usano quando serve accesso rapido sia in lettura che in scrittura su un insieme non ordinato
Gli array hanno le caratteristiche che servono:
Sono tutte e due operazioni dirette
(non richiedono nessuna ricerca)
Cerco di usare un vettore per rappresentare un insieme
Un insieme di numeri interi che vanno da 0 a 100 si può rappresentare usando un vettore di cento elementi booleani
Se v è il vettore che rappresenta l'insieme, le operazioni si realizzano cosí:
Limiti della rappresentazione dei vettori caratteristici:
Si possono superare tutti e due grazie agli hashCode
È un metodo che ritorna un intero dato un oggetto
Dato un oggetto o, il suo intero corrispondente è o.hashCode()
Per il momento ci basta sapere questo
Al posto del vettore di booleani, usiamo un vettore di Object
Prima versione della tavola hash:
class Tavola {
private Object t[];
public Tavola() {
t=new Object[...];
// inizializzazione automatica a null
}
boolean add(Object o) {
int c=o.hashCode();
if(t[c]!=null)
return false;
t[c]=o;
return true;
}
...
class Tavola {
...
boolean remove(Object o) {
boolean p;
int c=o.hashCode();
p=(t[c]!=null);
t[c]=null;
return p;
}
boolean contains(Object o) {
int c=o.hashCode();
if(o==null)
return false;
if(t[c]==null)
return false;
return t[c].equals(o);
}
}
Del primo problema ci occupiamo dopo
Scelgo una dimensione qualsiasi (per esempio, 100)
Quando l'hashCode vale c, uso c%100 per indicizzare l'array
class Tavola {
private final int size=100;
private Object t[];
public Tavola() {
t=new Object[size];
}
boolean add(Object o) {
int c=o.hashCode()%size;
if(t[c]!=null)
return false;
t[c]=o;
return true;
}
boolean remove(Object o) {
boolean p;
int c=o.hashCode()%size;
p=(t[c]!=null);
t[c]=null;
return p;
}
boolean contains(Object o) {
int c=o.hashCode()%size;
if(o==null)
return false;
if(t[c]==null)
return false;
return t[c].equals(o);
}
}
Stessa classe di prima con c=o.hashCode()%size al posto di c=o.hashCode()
Soluzione banale: quando vado a inserire un oggetto ma la sua posizione è già occupata, lo metto invece in una lista
Casella di un oggetto o: casella nella posizione o.hashCode()%100
Un vettore e una lista, più la dimensione del vettore
import java.util.*;
class Tavola {
private final int size=100;
private Object t[];
private LinkedList l;
public Tavola() {
t=new Object[size];
l=new LinkedList();
}
...
}
La lista si chiama lista di trabocco
Dato un oggetto o, la sua posizione naturale è:
posizione naturale di un oggetto o = casella di indice o.hashCode()%size del vettore
Le assunzioni che faccio e rispetto sono:
Nel nostro caso, "da qualche altra parte" significa nella lista
Facile: se la posizione naturale è libera, ci metto l'oggetto
Altrimenti, lo metto nella lista
Prima devo controllare che non sia presente
boolean add(Object o) {
int c=o.hashCode()%size;
if(t[c]!=null)
if(l.contains(o))
return false;
else
return l.add(o);
t[c]=o;
return true;
}
Devo considerare tutte e due le assunzioni:
boolean contains(Object o) {
int c=o.hashCode()%size;
if(t[c]==null)
return false;
if(t[c].equals(o))
return true;
return l.contains(o);
}
Faccio prima una ricerca
Vedo se l'oggetto sta nella posizione naturale, e se è vuota guardo la lista
Se trovo l'oggetto nella posizione naturale, non basta cancellarlo
Se lo faccio, potrei avere un altro oggetto nella lista che ora non si trova nella sua posizione naturale anche se questa è libera!
Sarebbe un oggetto che non trovo quando faccio contains
Esempio: si supponga che gli oggetti new Integer(50) e new Integer(150) abbiano entrambi posizione naturale 50
Si inserisce prima 50 e poi 150
Ora 50 sta nell'array e 150 nella lista
Si elimina 50 mettendo null nell'array
Se ora eseguo contains(new Integer(150)), mi ritorna false
Infatti, il metodo contains guarda nella posizione naturale, trova null e ritorna false
Due soluzioni:
La prima è inefficiente: quasi tutte le volte si deve andare a guardare nella lista
Usiamo la seconda soluzione
L'assunzione che viene usata da contains è che un elemento sta nella lista solo se la suo posizione naturale è occupata
Questo è lo stesso di: un elemento non può stare nella lista se la sua posizione naturale è libera
Quando si elimina un elemento dalla sua posizione naturale, basta prendere dalla lista uno qualsiasi degli altri elementi con quella posizione naturale (se esiste) e metterlo nella posizione naturale
Questo rende vera l'assunzione: se ci sono elementi nella lista, la loro posizione naturale è occupata
boolean remove(Object o) {
boolean p;
int c=o.hashCode()%size;
if(o==null)
return false;
if(t[c]==null)
return false;
if(!t[c].equals(o))
return l.remove(o);
// trovato oggetto: guarda la lista
Iterator i=l.iterator();
while(i.hasNext()) {
Object b=i.next();
if(b.hashCode()%size==c) {
t[c]=b;
i.remove();
return true;
}
}
t[c]=null;
return true;
}
Serve per trovare la posizione naturale di un oggetto in una tavola hash.
Vincolo: se due oggetti sono equals, devono avere lo stesso hashCode
La versione qui sotto rispetta questa specifica:
public int hashCode() {
return 0;
}
Tutte le operazioni funzionano perchè la specifica è rispettata
Se non vado mai nella lista di trabocco, ogni operazione ha costo uno (accesso al vettore)
Se tutti gli oggetti hanno lo stesso codice hash, allora tutti gli oggetti tranne uno stanno nella lista
L'efficienza delle operazioni è maggiore se riesco a non usare la lista di trabocco
Il metodo hashCode dovrebbe funzionare in modo tale da restituire interi possibilmente diversi per gli oggetti diversi che uso
Questo non può essere garantito; basta che due oggetti diversi che uso abbiano "spesso" codici diversi
Vogliamo avere risultato diverso se i campi sono diversi
class Studente {
String name;
int anno;
public int hashCode() {
int res=0;
res+=name.hashCode();
res+=anno;
return res;
}
}
Prima versione: faccio la somma delle componenti intere e degli hashcode delle componenti oggetto
Supponiamo di avere un insieme di Point
Non è improbabile che il punto (1,2) e (2,1) stiano nello stesso insieme
Hanno però lo stesso hashCode
Altro esempio: le persone con nome e cognome Bruno, Marco e Marco, Bruno hanno lo stesso hashCode se nome e cognome sono due componenti separate
Soluzione: ogni componente viene moltiplicata per un valore diverso
class Studente {
String name;
int anno;
public int hashCode() {
int res=3;
res=5*res+name.hashCode();
res=5*res+anno;
return res;
}
}
L'ultima componente è moltiplicata per 1, la penultima per 5, la terz'ultima per 5*5, ecc.
I concetti comuni delle tavole hash sono:
Ci sono versioni diverse in cui cambia il "qualche altra parte"
Se la posizione naturale di un oggetto è occupata, lo metto nella successiva posizione dell'array
Variante: invece della posizione successiva uso posizione+incremento, dove incremento è un numero primo rispetto alla dimensione dell'array
È complicata
Esempio: (il numero e' la posizione naturale di un oggetto)
prima: {null null 2a 2b 2c 3d 3e null null}
Cancellare 2b: non posso mettere solo null nella posizione 3, altrimenti otterrei:
dopo: {null null 2a null 2c 3d 3e null null}
Se ora cerco 2c oppure 3d, ecc. non li trovo
Occorre spostare tutti gli elementi che seguono fino al primo elemento che è null
dopo: {null null 2a 2c 3d 3e null null null}
In questi spostamenti, gli elementi non possono risalire prima della loro posizione naturale:
prima: {null null 2a 2b 2c 3d 3e 7f 3g}
non va:{null null 2a null 2c 3d 3e 7f null}
dopo: {null null 2a 2c 3d 3e 3g 7f null}
Se non si rispettano queste regole, la cancellazione non è più coerente con la ricerca
Idea: per ogni elemento dell'array, ho una lista di trabocco
Ho quindi un array di oggetti e un array di liste;
i due array hanno la stessa dimensione
L'elemento sta nella posizione naturale oppure nella lista di trabocco della posizione naturale
Realizzo solo l'array di liste
Il principio è che l'accesso al primo elemento di lista è comunque facile come accedere a un elemento di un array
Ognuna delle liste si chiama bucket
import java.util.*;
class Tavola {
private final int size=100;
private LinkedList l[];
public Tavola() {
int i;
l=new LinkedList[size];
for(i=0; i<l.length; i++)
l[i]=new LinkedList();
}
boolean add(Object o) {
int c=o.hashCode()%size;
if(l[c].contains(o))
return false;
return l[c].add(o);
}
boolean contains(Object o) {
int c=o.hashCode()%size;
return l[c].contains(o);
}
boolean remove(Object o) {
int c=o.hashCode()%size;
return l[c].remove(o);
}
}
Si poteva anche lasciare l'array di liste vuoto
La lista l[c] veniva creato solo quando si andava a inserire un elemento che aveva posizione naturale c
Bisogna fare un controllo l[c]==null sia su remove che su contains