Wir verwenden eine Hash-Tabelle mit einer Hash-Funktion der Form h(x) = (ax+b) mod N. Falls Hash-Tabellen einen hohen Füllgrad M/N erreichen, wird die Suche nach ihren Elementen wie in der Vorlesung erläutert ineffizient. Eine Möglichkeit wäre es nun, die Hash-Tabelle dynamisch auf N'>N zu vergrößern.
- Skizzieren Sie - für (a) lineares Sondieren und (b) Verkettung mit doppelt verketteten Listen - jeweils ein Verfahren um eine Hash-Tabelle mit existierenden Einträgen zu vergrößern, so dass ihre Konsistenz erhalten bleibt und auch hinterher nach Elementen gesucht werden kann.
- Leiten Sie in beiden Fällen die Worst Case - Komplexität der Reorganisation in Abhängigkeit von M und N her.