Eine weitere Frage zu SO brachte in einigen Sprachen die Möglichkeit zum Hashing von Strings, um ihnen eine schnelle Suche in einer Tabelle zu ermöglichen. Zwei Beispiele hierfür sind das Verzeichnis <> in .NET und die Speicherstruktur {} in Python. Andere Sprachen unterstützen sicherlich einen solchen Mechanismus. C++ hat seine Map, LISP hat ein Äquivalent, wie die meisten modernen Sprachen.Konstante Zeit Hash für Strings?
Es wurde in den Antworten auf die Frage behauptet, dass Hash-Algorithmen auf Strings in konstanter Zeit mit einem SO-Mitglied durchgeführt werden können, das 25 Jahre Erfahrung in der Programmierung hat und behauptet, dass alles in konstanter Zeit hashed werden kann. Meine persönliche Behauptung ist, dass dies nicht wahr ist, es sei denn, Ihre spezielle Anwendung legt eine Grenze für die Länge der Zeichenfolge fest. Dies bedeutet, dass einige konstante K die maximale Länge einer Saite vorgeben würde.
Ich bin vertraut mit dem Rabin-Karp-Algorithmus, der eine Hash-Funktion für seine Operation verwendet, aber dieser Algorithmus diktiert keine bestimmte Hash-Funktion zu verwenden, und die von den Autoren vorgeschlagen ist O (m), wo m ist die Länge der Hash-Zeichenfolge.
Ich sehe einige andere Seiten wie diese (http://www.cse.yorku.ca/~oz/hash.html), die einige Hash-Algorithmen anzeigen, aber es scheint, dass jeder von ihnen über die gesamte Länge der Zeichenfolge iteriert, um seinen Wert zu erreichen.
Aus meiner vergleichsweise begrenzten Lektüre zu diesem Thema, scheint es, dass die meisten assoziativen Arrays für String-Typen tatsächlich mit einer Hash-Funktion erstellt werden, die mit einem Baum von einer Art unter der Haube arbeitet. Dies kann ein AVL-Baum oder ein Rot/Schwarz-Baum sein, der auf die Position des Wertelements im Schlüssel/Wert-Paar zeigt.
Auch wenn wir in dieser Baumstruktur in der Reihenfolge von Theta bleiben (log (n)), wobei n die Anzahl der Elemente im Baum ist, müssen wir einen Hash-Algorithmus mit konstanter Zeit haben. Andernfalls haben wir den additiven Nachteil, dass wir über die Zeichenfolge iterieren. Auch wenn Theta (m) bei Indizes, die viele Strings enthalten, durch Theta (log (n)) überlagert wäre, können wir es nicht ignorieren, wenn wir in einer solchen Domäne sind, in der die gesuchten Texte sehr groß sind.
Ich bin mir bewusst, dass Suffix Bäume/Arrays und Aho-Corasick die Suche nach Theta (M) für einen größeren Aufwand im Speicher bringen kann, aber was ich speziell frage, ob eine Konstante-Zeit-Hash-Methode für Strings von existiert willkürliche Längen, wie von den anderen SO-Mitgliedern behauptet wurde.
Danke.
Erinnert mich an http://xkcd.com/221/ –
Das Problem dabei ist, dass sehr ähnliche Strings ein hätte hohe Wahrscheinlichkeit, identische Hashes zu haben. Im Allgemeinen sollte eine einzige Bitänderung alle Bits im Hash ändern, so dass die Wahrscheinlichkeit, dass zwei Strings kollidieren, unabhängig von ihrer Ähnlichkeit ist. - Das heißt, Ihre Idee würde funktionieren, wenn Sie sich keine Sorgen machen müssten, dass enge Saiten zusammenstoßen. –