SimpleHashtable
public class SimpleHashtable {
protected double[] ar;
protected int nCollisions;
protected static final double EMPTY = Double.POSITIVE_INFINITY;
public SimpleHashtable(int n) {
ar = new double[n];
clear();
}
public void put(double d) {
// legt d in der Hashtable ab
int first = hashCode(d);
int aktuell = first;
// suche freien Platz
int k;
for (k = 0; k < ar.length; k++) {
if (ar[aktuell] == EMPTY) {
break;
}
aktuell = sond(first, k);
}
if (k == ar.length) {
// Hashtable ist voll
throw new IllegalStateException();
}
ar[aktuell] = d;
nCollisions += k;
}
public int anzahlKollisionen() {
return nCollisions;
}
public void clear() {
// leert die Hashtabelle
nCollisions = 0;
for (int i = 0; i < ar.length; i++) {
ar[i] = EMPTY;
}
}
protected int hashCode(double d) {
// Hashfunktion
// liefert Position in der Hashtabelle
// run zu int
int i = (int) Math.round(d);
return i % ar.length;
}
protected int sond(int i0, int k) {
// Sondierungsfunktion
// liefert k-ten Versuch für einen freien Platz, wenn i0 besetzt ist
// gehe einfach k Schritte weiter
return (i0 + k) % ar.length;
}
}