Re-Hashing

Id: rehash.tex,v 1.1 2006-10-09 13:24:16 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 2009-01-12