Re-Hashing

Id: rehash.tex,v 1.1 2005/01/11 16:14:05 waldmann Exp

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



Johannes Waldmann 2006-01-26