Hashverfahren Vorteile und Nachteile

[Merlin]

also, das quadratische Sondieren VS lineares Sondieren:

Beim quadratischen Sortieren werden primäre Häufungen vermieden, hab ich das richtig verstanden?
Dafür gibt es dann Sekundäre Häufungen.

Dies wird durch uniformes Sondieren bzw. durch an uniformes S. approximierte Sondierungen wie z.B Double Hashing vermieden.

Hab ich das richtig verstanden?

Und zur Verbesserung der Suche (ich meine damit die Laufzeit), falls häufig gesucht wird, dient dann die Verbesserung von Brent.

Wenn man viele Entfernungen vorimmt. ist aber Hashing mit Verkettung der Überläufer vorzuziehen, da die Suchzeit nicht mehr proportional zu Theta(1+alpha) ist bei offenen Hashverfahren.

Bei Verkettung der Überläufer habe ich folgende Vorteile ausserdem:

Belegungsfaktor von mehr als 1 möglich
==> echte Entfernungen von Einträgen sind möglich
Eignet sich für den Einsatz mit Externspeichern (Hashtabelle in Internspeicher)

Nachteile: Speicherplatzbedarf für die Zeiger
Es wird sogar dann Platz für Überläufer benötigt, wenn in der Hashtabelle noch viele freie Plätze sind.

[Georg Kraml]

Nachteile: Speicherplatzbedarf für die Zeiger
Es wird sogar dann Platz für Überläufer benötigt, wenn in der Hashtabelle noch viele freie Plätze sind.

Das ist im Prinzip richtig, aber der Platzbedarf für die Zeiger ist in der Praxis fast immer vernachlässigbar - ein Zeiger hat auf fast allen Architekturen die selbe oder eine ähnliche Größe wie der gebräuchlichste Integraltyp, also zum Beispiel das int von C. Und wenn die eigentlichen Datensätze (ohne Schlüssel) nicht wesentlich größer sind als ein int, greift man in der Regel erst gar nicht zur Hashtabelle.

Ein viel wesentlicherer Nachteil als der Speicherbedarf für die Zeiger ist der erhöhte Zeitaufwand beim Suchen.

.