Re-Hashing

Id: rehash.tex,v 1.1 2006-10-09 13:24:16 waldmann Exp

• Tabelle zu klein $\to$ zu voll $\to$ viele Kollisionen $\to$ langsam.
• Tabelle zu groß: Platz verschenkt.

Lösung: falls Tabelle gewissen Füllstand erreicht, dann zu neuer, größerer Tabelle wechseln (= re-Hashing).

am einfachsten: Tabellengröße ist immer Potenz von 2; dann: vergrößern = verdoppeln.

Beim re-Hashing müssen alle Einträge betrachtet werden, das findet aber nur selten statt, so daß die amortisierte Laufzeit trotzdem konstant ist