private Comparable[] inhalt; // Array von Comparables private byte[] zustand; // Array von Zustaenden // LEER, BELEGT und GELOESCHTFalls
![]() |
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
Source: OfHashing.java JavaDoc: OfHashing.htmlLänge
ist perfekte Hashfunktion.
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