Geschlossenes Hashing

    private Object[] inhalt; // Array von Objekten
    private int[] zustand;   // Array von Zustaenden
                             // LEER, BELEGT, GELOESCHT

Falls y = f (x) schon belegt ist, so suche für x einen Alternativplatz.

y + 1,y + 2,y + 3,y + 4,... lineares Sondieren

y + 1,y + 4,y + 9,y + 16,... quadratisches Sondieren

y + f₂(x) Double Hashing (Schrittweite wird durch 2. Hashfunktion bestimmt)

Beim linearen und quadratischen Sondieren müssen höchstens N - 1 Sondierschritte durchgeführt werden. Beim quadratischen Sondieren werden ggf. nicht alle Buckets besucht, aber mindestens .

Implementation des geschlossenen Hashings

Beispiel:

Die beiden Abbildungen ergeben sich durch sukzessives Einfügen der Worte

Fritz, Mark, Emil, Carsten, Ulf, Heinz, Lutz, Eva, Achim

und anschließendes Löschen von

Ulf, Lutz

für N = 17 .

Perfekte Hashfunktion

Gesucht wird eine Hashfunktion f , die auf den Elementen keine Kollision verursacht, z.B.:

gesucht: f : {braun, rot, blau, violett, türkis}

Länge (w) = 5 3 4 7 6

Länge (w) - 3 = 2 0 1 4 3

f (w) = Länge (w) - 3 [0..4] ist perfekte Hashfunktion.

Source: StringCompare.java     JavaDoc: StringCompare.html     Source: Hashing.java     JavaDoc: Hashing.html    

Source: OfHashing.java     JavaDoc: OfHashing.html    

Source: GeHashing.java     JavaDoc: GeHashing.html    

Source: HashTest.java     JavaDoc: HashTest.html     Applet:

Laufzeit bei geschlossenem Hashing

Sei 1 der Auslastungsfaktor. Dann ergibt sich für die Anzahl der Schritte mit Double-Hashing als Kollisionsstrategie bei

• erfolgloser Suche: = 5.0 , für = 0.8
• erfolgreicher Suche: - = 2.01 , für = 0.8

d.h., in 2 Schritten wird von 800.000 Elementen aus einer 1.000.000 großen Tabelle das richtige gefunden.