Hi,

es speichereffizienter ist.

nichts ist umsonst außer dem Tod und selbst der kost' das Leben.

Sonst muesste man in einem Loch Platz fuer
zwei Werte haben, das bedeutet 2x soviel Speicher-Aufwand.

Der zweite Wert ist ein popeliger Pointer auf die Subhashtabelle. Wäre auch sonst ein Pointer auf die LinkedList. Du brauchst also noch nicht einmal mehr Speicher dafür.
Die Information, die Du meinst zu brauchen ist boolscher Natur, der Umstand, das das Loch belegt ist, das eine Kollisison überhaupt stattfindet, ist schon ausreichend als Grund auf die zweite Hastabelle zu wechseln.

Aber inwieweit das Sinn macht ist eine andere Frage.

Es wäre möglich eine Hastabelle, wenn auch nur in engen Grenzen, dynamisch zu erweitern. Ohne ein Rebuild. Komlexität wäre dabei rein theoretisch O(1+m) wobei m die Tiefe der "Subhashtabellenstaffelung" wäre. Grenze des sinnvollen Ausbaus wäre damit sogar genau berechenbar.
Probleme sind auch absehbar: vorher zu bestimmende Größe der Ausbaustufe, es macht keinen Sinn nur um je 1*n Teilstücke zu vergrößern, die angefügten Unterhashtabellen sollten idealerweise immer genau so groß wie die voherige Hashtabelle sein. Speicher kann erst zur Runtime angefordert werden, aber das ist ja nicht unbedingt etwas schlechtes und es käme auch nur selten vor. Eigentliches Problem hierbei ist, das auch der neue Standard maximal Chunks von 64 kib _garantiert_. Das erforderte evt eine komplizierte eigene Speicherverwaltung. Trifft aber auch nur auf die theoretischen Überlegungen zu und hat natürlich auch nix mit dem Algorithmus selber zu tun.
Letztes Problem ist natürlich eindeutig: _riesiger_ Speicherverbrauch. Wenn bei einer Hashtabelle mit 2^16 Löchern jedes Loch einmal kollidiert und nach obigem Vorschlag die Subhashtabellen genauso groß, wie das vorherige Hash, bleiben am Ende 2^32 Löcher und Speicherbedarf dafür.

Alles also mehr eine akademische Übung, wenn auch eine interessante und jetzt muß ich wirklich in die Heia.

so short

Christoph Zurnieden