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

Sicherlich ist dies machbar, solange Sie sicherstellen, dass alle Ihre Zeichenfolgen "interniert" sind, bevor Sie sie an etwas übergeben, das Hashing erfordert. Beim Internieren wird die Zeichenkette in eine Zeichenkettentabelle eingefügt, so dass alle internierten Zeichenketten mit demselben Wert tatsächlich dasselbe Objekt sind. Dann können Sie einfach den Zeiger (mit fester Länge) auf die internierte Zeichenkette hashen, anstatt die Zeichenkette selbst zu hashen.

Answer 2

Vielleicht interessiert Sie das folgende mathematische Ergebnis, auf das ich letztes Jahr gekommen bin.

Betrachten wir das Problem des Hashings einer unendlichen Anzahl von Schlüsseln - etwa der Menge aller Zeichenketten beliebiger Länge - mit der Menge der Zahlen in {1,2, ,b}. Beim zufälligen Hashing wird zunächst eine Hash-Funktion h aus einer Familie von H-Funktionen zufällig ausgewählt.

Ich werde zeigen, dass es immer eine unendliche Anzahl von Schlüsseln gibt, die mit Sicherheit über alle H-Funktionen kollidieren, d.h. sie haben immer den gleichen Hash-Wert für alle Hash-Funktionen.

Wählen Sie eine beliebige Hash-Funktion h: Es gibt mindestens einen Hash-Wert y, so dass die Menge A={s:h(s)=y} unendlich ist, d. h., es gibt unendlich viele kollidierende Zeichenfolgen. Es gibt mindestens einen Hashwert y', so dass die Menge A'={s ist in A: h'(s)=y'} unendlich ist, d. h. es gibt unendlich viele Zeichenfolgen, die bei zwei Hashfunktionen kollidieren. Sie können dieses Argument beliebig oft wiederholen. Wiederholen Sie es H-mal. Dann haben Sie eine unendliche Menge von Zeichenketten, bei der alle Zeichenketten mit allen H Hash-Funktionen kollidieren. CQFD.

Weitere Lektüre : Sinnvolles Hashing von Zeichenketten variabler Länge ist unmöglich http://lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/