private Comparable[] inhalt; // Array von Comparables private byte[] zustand; // Array von Zustaenden // LEER, BELEGT und GELOESCHTFalls schon belegt ist, so suche für einen Alternativplatz.
lineares Sondieren | |
quadratisches Sondieren | |
Double Hashing (Schrittweite wird durch 2. Hashfunktion bestimmt) |
Beim linearen und quadratischen Sondieren müssen höchstens 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
Perfekte Hashfunktion
Gesucht wird eine Hashfunktion , die auf den Elementen keine Kollision verursacht, z.B.:
gesucht: : {braun, rot, blau, violett, türkis} Länge = 5 3 4 7 6 Länge = 2 0 1 4 3
Länge ist perfekte Hashfunktion.Source: OfHashing.java JavaDoc: OfHashing.html
Source: GeHashing.java JavaDoc: GeHashing.html Source: HashTest.java JavaDoc: HashTest.html Applet: Laufzeit bei geschlossenem Hashing
Sei der Auslastungsfaktor. Dann ergibt sich für die Anzahl der Schritte mit Double-Hashing als Kollisionsstrategie bei