2011-12-30T16:40:41 topeg

2011-12-30T16:05:16 murphy

• Man kann das Problem auch dadurch umgehen, dass man zum Speichern aller Schlüssel-Wert-Paare mit gleichem Schlüsselhash eben keine einfache sequentielle Datenstruktur verwendet, sondern zum Beispiel einen Binärbaum.

Sicher das reduziert das Problem, schafft es aber nicht aus der Welt. Denn auch das Abarbeiten und Erweitern eines Baumes braucht Zeit. Man kann einen immer tiefer verschachtelten Baum konstruieren, dessen bearbeiten immer länger dauert. Der Extremfall wäre äquivalent zu einer verketteten Liste.

Das ist so nicht korrekt: Auf einem Red-Black Tree lassen sich zum Beispiel alle Operationen eines assoziativen Arrays mit einer Laufzeitordnung von O(log n) für n Einträge durchführen, während die sequentielle Suche in einer Liste oder einem Array immer O(n) braucht.

Man verringert durch die Verwendung eines Baums als Bucketdatenstruktur also deutlich die schlechtestmögliche Laufzeit einer hashtabellenbasierten Implementation assoziativer Arrays ohne die bestmögliche Laufzeit zu beeinflussen.