你好 LanX!,

Darum ging es doch gar nicht. Es ging darum, dass du das Vokabular als
eine feste Zahl gesehen hast. Fakt ist, dass das Vokabular alles andere
als fest ist, wie ich dir gerade bewiesen habe.

Das Gesamtvokabular ist absolut natürlich nicht fest, potentiel aber
schon. Es macht keinen Sinnden gleichen Aufwand für Nischenwörter zu
betreiben die jenseits des Standardvokabulars sind.

Also soll ich demnaechst nur noch nach Standard-Vokabeln suchen koennen?
Na vielen Dank...

Ja. Und um diese Kollisionen aufzuloesen muss dein Hash-Wert genauer
sein als der in der ersten Tabelle, optimalerweise um eine
Zweier-Potenz.

Gehst du davon aus dass ich immer die gleiche Hashfunktion benutze?

Selbst wenn du eine andere benutzt, bekommst du dieselben Probleme. In
dem Fall vielleicht eher spaeter als frueh, aber du bekommst sie. Mal
abgesehen davon, dass irgendwann die Hash-Tabelle einfach voll ist und
du deine Tabelle neu aufbauen musst und den Schluessel vergroessern
musst (sinvollerweise um eine Zweier-Potenz).

Du musst sehen, wie Hash-Tabellen funktionieren. Hash-Tabellen sind
_Tabellen_, wie der Name schon sagt. Eine Tabelle hat eine bestimmte
Groesse, zwangslaeufig. Deshalb muss der Schluessel auch zwangslaeufig
auf eine bestimmte Genauigkeit beschraenkt werden. Ist jetzt die Tabelle
irgendwann voll (heisst, es gibt hinreichend viele Duplikate) gibt es
zwei Moeglichkeiten: Tabelle vergroessern, was eine vollstaendige
Reorganisation nach sich zieht, oder anfangen mit indirekten Tabellen zu
arbeiten, was zumindest teilweise eine Reorganisation benoetigt. Im ersten
Fall hast du nach einer Zeit wieder die gleichen Probleme: die Tabelle
wird zu klein, es gibt hinreichend viele Duplikate, die Performance wird
also scheisse. Im zweiten Fall dauert das vermutlich zwar tendentiell
laenger, aber die Probleme sind dieselben: irgendwann hast du auch in
dieser Stufe hinreichend viele Duplikate. Du kannst jetzt natuerlich
versuchen, eine Dritte Stufe aufzumachen, aber was bringt das? Auch da
stoesst man frueher oder spaeter an die Grenzen...

Nein, Hashes sind einfach nicht gut geeignet fuer eine theoretisch
unbegrenzte Eingabemenge. Das liegt in der Natur der Sache, aber das
solltest du als Mathematiker doch auch sehen? Wenn ich eine Funktion
f : |D -> \W habe, wobei |D = |R und \W = {1,2,...,2^32}, dann ist doch
abzusehen, dass die Funktion nicht injektiv ist und es unendlich viele
Werte in |D gibt, die auf ein einzelnes Element von \W abbilden. Egal,
wie gross du \W machst, wenn du es nicht unendlich gross machst, wirst
du immer unendlich viele Werte in |D haben, die zu einem einzelnen
Element aus \W abbilden.

Aber ich mache dir einen Vorschlag. Du erstellst eine funktionierende
Loesung, die theoretisch (bei unendlich viel Speicher) mit unendlich
vielen Daten klarkommt und dann werde ich dir haltlos zustimmen. Eine
weitere Diskussion duerfte nicht viel bringen. «Du glaubst mir ja eh
nicht!»

Wieso brauche ich für 256 Einträge 32-Bit Schlüssel???

Der hoeheren Genauigkeit wegen. Die Genauigkeit muss doch hoeher sein als
in der ersten Stufe.

再见,
 CK