Hi,

In der zweiten Hastabelle ist das Loch aber noch leer: [...]

Nein, du musst ja den die Kollision verursachenden Schluessel mit in
diese neue Hash-Tabelle legen. Du hast den Wert, der bereits in der
Ursprungstabelle war und den neuen Wert, die musst du beide in die
neue Hash-Tabelle legen.

Oh weh, ich sollte das aufmalen, nur wie?

Ho_1->Hn_a
Ho_2->Hn_b
Ho_3->Hn_c

Ho_i sollen die Löcher in der ersten Hashtabelle sein, Hn_i die sekundären Hastabellen.

Hn_i1->LLn_a
Hn_i2->LLn_b
Hn_i3->LLn_c

Hn_ij sollen die Löcher in der sekundären Hashtabelle sein, LLn_i die abschließenden Linked-Lists.

Eine Kollision durch die Funktion h(x)=y wird verarbeitet, indem statt der sonst üblichen LLs eine weiter Hashtabelle drangehangen wird. Bei der ersten Kollision ist die aber noch komplett leer. Egal welche Hashfunktion Du nimmst (vorausgesetzt sie trifft am Ende irgendeines der Löcher) Du triffst auf ein leeres Loch -> keine Kollision. Beim zweitem Mal triffst Du auf ein volles Loch -> Kollision -> LinkedList.
Wenn Du nun eine andere Hashfunktion h(x)=z nimmst, dann hast Du insgesammt weniger Kollisionen, das ist korrekt. Aber diese andere Hashfunktion ist nicht _zwingend_ nötig für die Funktion.
Sie ist aber eine "ordentliche" Optimierung, da sie mit wenig Aufwand (es ist ja wirklich nur _eine_ weitere Hashfunktion nötig, wenn auch eine genauso gute, wie die Erste) guten Effekt erzielt.
Anders sieht das natürlich aus, wenn meine ursprüngliceh Vermutung gestimmt hätte, das statt der abschließenden LinkedLists stets eine weitere Hashtabelle benutzt worden wäre. Dann wäre nicht nur für jede Hashtabelle eine gesonderte Hashfunktion nötig, sondern es hätte überhaupt nicht funktioniert, da hier eine unendliche große (gut: abzählbar unendlich große, hilft hier aber auch nix) Eingangsmenge angenommen wurde.

Oder ich schlepp Dich mit zu madmaxens Ausstellung und wir plündern
einfach dessen Buffet. Käme mir zwar nicht billiger bei den Sprit- und
Bierpreisen, wäre aber logistisch einfacher.

Hehe, wenn du ueber Dortmund faehrst? ;-)

Sind gerade mal - zu faul zum nachschauen, aber gut geschätzt - etwa 30 km Umweg. Der Kasten Oettinger ist hier gerade im Angebot für 4,29 EUR. Da tut sich also nicht viel.

so short

Christoph Zurnieden