2011-12-30T16:05:16 murphy

• In genau den Spezialfällen wo man alle möglichen Schlüssel im Vorfeld kennt kann man das Problem durchaus dadurch verhindern, dass man eine perfekte Hashfunktion erzeugt.

IP-Adressen sind ein Beispiel für Eindeutige und Begrenzte Anzahl von Werten. Das Problem ist dann, dass man sehr viel Speicher für reservieren muss (rechne mal nach wieviel TByte man bräuchte nur um eine IP -> DomainName Zuweisung zu ermöglichen). Weshalb auch hier eine einfache Form von Hashing genutzt und eine Kollision riskiert wird.

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.