Konstantzeit-Hash für Strings?

Question

In einer anderen Frage zu SO wurde die Möglichkeit angesprochen, in einigen Sprachen Zeichenketten zu hashen, um sie schnell in einer Tabelle nachschlagen zu können. Zwei Beispiele hierfür sind dictionary<> in .NET und die {}-Speicherstruktur in Python. Andere Sprachen unterstützen einen solchen Mechanismus natürlich auch. C++ hat seine Map, LISP hat ein Äquivalent, und die meisten anderen modernen Sprachen auch.

In den Antworten auf die Frage wurde behauptet, dass Hash-Algorithmen für Zeichenketten in konstanter Zeit durchgeführt werden können. Ein SO-Mitglied, das 25 Jahre Erfahrung in der Programmierung hat, behauptete, dass alles in konstanter Zeit gehasht werden kann. Ich persönlich behaupte, dass dies nicht stimmt, es sei denn, Ihre spezielle Anwendung setzt eine Grenze für die Stringlänge. Das bedeutet, dass eine bestimmte Konstante K die maximale Länge einer Zeichenkette vorgeben würde.

Ich bin mit dem Rabin-Karp-Algorithmus vertraut, der eine Hash-Funktion für seine Operation verwendet, aber dieser Algorithmus schreibt keine spezifische Hash-Funktion vor, die zu verwenden ist, und die von den Autoren vorgeschlagene ist O(m), wobei m die Länge der gehashten Zeichenfolge ist.

Ich sehe einige andere Seiten, wie zum Beispiel 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 Zeichenkette iteriert, um zu seinem Wert zu gelangen.

Aus meiner vergleichsweise begrenzten Lektüre zu diesem Thema geht hervor, dass die meisten assoziativen Arrays für Stringtypen tatsächlich mit einer Hashing-Funktion erstellt werden, die mit einer Art Baum unter der Haube arbeitet. Dabei kann es sich um einen AVL-Baum oder einen rot/schwarzen Baum handeln, der auf den Ort des Wertelements im Schlüssel/Wert-Paar verweist.

Selbst mit dieser Baumstruktur benötigen wir einen Hash-Algorithmus mit konstanter Zeit, wenn wir in der Größenordnung von theta(log(n)) bleiben wollen, wobei n die Anzahl der Elemente im Baum ist. Andernfalls haben wir den additiven Nachteil, dass wir über die Zeichenkette iterieren müssen. Auch wenn theta(m) bei Indizes, die viele Zeichenketten enthalten, durch theta(log(n)) in den Schatten gestellt wird, können wir dies nicht ignorieren, wenn wir uns in einem Bereich befinden, in dem die Texte, die wir durchsuchen, sehr groß sein werden.

Ich bin mir bewusst, dass Suffix-Bäume/Arrays und Aho-Corasick die Suche auf theta(m) reduzieren können, was einen größeren Aufwand an Speicher bedeutet, aber ich frage speziell, ob es eine Hash-Methode mit konstanter Zeit für Zeichenketten beliebiger Länge gibt, wie vom anderen SO-Mitglied behauptet wurde.

Danke.

Answer 1

Eine Hash-Funktion muss (und kann) nicht für jede Zeichenfolge einen eindeutigen Wert zurückgeben.

Man könnte die ersten 10 Zeichen verwenden, um einen Zufallszahlengenerator zu initialisieren, und diesen dann verwenden, um 100 zufällige Zeichen aus der Zeichenkette herauszuziehen und diese zu hashen. Dies wäre eine konstante Zeit.

Sie könnten auch einfach den konstanten Wert 1 zurückgeben. Streng genommen ist dies immer noch eine Hash-Funktion, wenn auch keine sehr nützliche.

Answer 2

Im Allgemeinen glaube ich, dass jeder vollständige String-Hash jedes Zeichen des Strings verwenden muss und daher als O(n) für n Zeichen wachsen müsste. Ich denke jedoch, dass man für praktische String-Hashes ungefähre Hashes verwenden kann, die leicht O(1) sein können.

Betrachten wir einen String-Hash, der immer Min(n, 20) Zeichen verwendet, um einen Standard-Hash zu berechnen. Offensichtlich wächst dies mit O(1) mit der Größe der Zeichenkette. Wird es zuverlässig funktionieren? Das hängt von Ihrer Domäne ab...

Answer 3

Ein allgemeiner Hash-Algorithmus mit konstanter Zeit für Zeichenketten lässt sich nicht ohne weiteres realisieren, ohne dass es zu schweren Fällen von Hash-Kollisionen kommt.

Um eine konstante Zeit zu erhalten, können Sie nicht auf jedes Zeichen der Zeichenkette zugreifen. Ein einfaches Beispiel: Nehmen wir die ersten 6 Zeichen. Dann kommt jemand und versucht, ein Array von URLs zu hashen. Die has-Funktion wird für jede einzelne Zeichenfolge "http:/" sehen.

Ähnliche Szenarien können auch bei anderen Zeichenauswahlverfahren auftreten. Man könnte die Zeichen pseudozufällig auf der Grundlage des Wertes des vorherigen Zeichens auswählen, aber man läuft immer noch Gefahr, spektakulär zu scheitern, wenn die Zeichenketten aus irgendeinem Grund das "falsche" Muster haben und viele am Ende denselben Hash-Wert haben.

Answer 4

Sie können Hoffnung für asymptotisch weniger als lineare Hashing-Zeit, wenn Sie Seile anstelle von Strings und haben eine gemeinsame Nutzung, die es Ihnen ermöglicht, einige Berechnungen zu überspringen. Aber natürlich kann eine Hash-Funktion keine Eingaben trennen, die sie nicht gelesen hat, daher würde ich die Aussage "alles kann in konstanter Zeit gehasht werden" nicht allzu ernst nehmen.

Bei dem Kompromiss zwischen der Qualität der Hash-Funktion und der Menge der erforderlichen Berechnungen ist alles möglich, und bei einer Hash-Funktion für lange Zeichenfolgen muss es ohnehin zu Kollisionen kommen.

Sie Sie müssen feststellen, ob die Zeichenfolgen, die in Ihrem Algorithmus wahrscheinlich vorkommen, zu oft kollidieren, wenn die Hash-Funktion nur ein Präfix betrachtet.

Answer 5

Obwohl ich mir eine Hash-Funktion mit fester Zeit für Zeichenketten unbegrenzter Länge nicht vorstellen kann, besteht dafür wirklich kein Bedarf.

Die Idee hinter der Verwendung einer Hash-Funktion ist es, eine Verteilung der Hash-Werte zu erzeugen, die es möglich macht unwahrscheinlich, dass viele Strings zusammenstoßen - für den betrachteten Bereich. Dieser Schlüssel würde den direkten Zugriff auf einen Datenspeicher ermöglichen. Beides zusammen ergibt eine konstante Zeit für die Suche - im Durchschnitt .

Kommt es zu einer solchen Kollision, greift der Suchalgorithmus auf eine flexiblere Suchteilstrategie zurück.