Große Strings schnell auf Inhalt einer Zeichenkette prüfen?

[alzaimar]

Meine Hashtabelle vergrößert sich doch dynamisch.

Ich hatte ursprünglich auch den CRC16 drin, bis ich meine StringDictionary für mehr als 655536 Elemente brauchte. Also den CRC32.
[edit] Und die Berechnung von CRC32 ist auch nicht langsamer, als CRC16. [/edit] Dann habe ich noch recherchiert und, siehe da, es geht noch schneller: Ich habe den 'ELF'-Hash verwendet, daneben gibt es noch den 'Pjw', der in Compilern Verwendung findet. Ich hatte mal ELF und PJW verglichen, bin dann bei ELF hängengeblieben.

Also nochmal (auf die Gefahr hin, das Dich das nervt):
Ich berechne einen 32bit-Hash zu dem einzufügenden Schlüssel. Damit bin ich, was die maximale Größe der Liste anbelangt, auf der Sicheren Seite. Bevor ich die aber gleich so gross mache, fange ich ganz klein an, nämlich bei 1000 (genauergesagt 997, weil Primzahl) an. Wenn die Liste langsam voll wird, muss ich sie vergrößern. Ich verdopple also die Größe, such mir die nächstbeste Primzahl und dass ist dann die neue Listengröße. Natürlich muss ich einmalig alle bereits in der Liste gespeicherten Elemente nochmals in die neue, größere Liste einfügen, da sich ja die Hashfunktion (ELF mod ListSize) verändert hat. Ich dachte zuerst, dass damit die Performance flöten geht, aber nee. Ausserdem kommt das 'Rehashing' sehr selten vor, bei 2^32 einzufügenden Elementen passiert das ja nur 20 mal, oder so.

Ich verwende Stringlisten derzeit nur noch ihrem Zweck (LISTEN) entsprechend. Wenn ich aber nach Strings suchen muss, geht nix über eine Hash-Tabelle (oder gleich eine DB). Na gut, die Skiplist ist für kleinere (<40.000) Elemente noch etwas besser, aber ich mag die Stringdictionaries nun mal. Vielleicht, weil ich sie mir selbst gebastelt habe.