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 die Anzahl der in der Hashtabelle zur Zeit gespeicherten Objekte,
sei
die Anzahl der möglichen Speicherpositionen.
Sei
der Auslastungsfaktor.
Dann ergibt sich für die Anzahl der Schritte mit Double-Hashing als Kollisionsstrategie bei