Constant-time-Hash für Strings?

Question

Eine weitere Frage auf SO die Einrichtungen in einigen Sprachen gebracht Strings Hash ihnen einen schnellen Nachschlagen in einer Tabelle zu geben. Zwei Beispiele hierfür sind Wörterbuch <> in .NET und der {} Speicherstruktur in Python. Andere Sprachen unterstützen sicherlich einen solchen Mechanismus. C ++ seiner Karte hat, LISP hat eine gleichwertige, wie die meisten anderen modernen Sprachen.

Es wurde in den Antworten auf die Frage geltend, dass Hash-Algorithmen auf Strings können in konstantem timem mit einem SO Mitglied durchgeführt werden, die 25 Jahren Erfahrung in der Programmierung hat behauptet, dass irgendetwas in konstanter Zeit gehasht werden kann. Meine persönliche Behauptung ist, dass dies nicht wahr ist, es sei denn, Ihre Anwendung eine Grenze auf der String-Länge platziert. Dies bedeutet, dass eine Konstante K die maximale Länge eines Strings diktieren würde.

Ich bin mit dem Rabin-Karp-Algorithmus bekannt, die eine Hash-Funktion für den Betrieb verwendet, aber dieser Algorithmus nicht diktieren, eine bestimmte Hash-Funktion zu verwenden, und der Computer der vorgeschlagenen Autoren O (m), wobei m des Länge des Hash-String.

Ich sehe einige andere Seiten wie diese ( http: // www. cse.yorku.ca/~oz/hash.html ), die angezeigt wird, einige Hash-Algorithmen, aber es scheint, dass jeder von ihnen iteriert über die gesamte Länge der Saite zu ihrem Wert zu gelangen.

Aus meiner vergleichsweise begrenzten Lesung zu dem Thema, scheint es, dass die meisten assoziativen Arrays für String-Typen sind tatsächlich erstellt eine Hash-Funktion verwenden, die mit einem Baum von einer Art unter der Haube arbeitet. Dies kann ein AVL-Baum oder rot / schwarz Baum sein, der in dem Schlüssel / Wert-Paar an die Stelle des Wertes Elements verweist.

Auch bei dieser Baumstruktur, wenn wir in der Größenordnung von Theta bleiben sollen (log (n)), wobei n die Anzahl der Elemente in dem Baum zu sein, brauchen wir eine konstante Zeit Hash-Algorithmus haben. Ansonsten haben wir den additiven Nachteil über die Kette von iterieren. Obwohl Theta (m) würde durch Theta (log (n)) für Indizes mit vielen Saiten verfinstert werden, können wir ignorieren es nicht, wenn wir in einer solchen Domäne sind, dass die Texte, die wir gegen die Suche sehr groß sein wird.

Ich bin mir bewusst, dass Suffix Bäume / Arrays und Aho-Corasick die Suche bringen kann bis auf Theta (m) für einen größeren Aufwand in Erinnerung, aber was ich frage speziell, wenn eine konstante Zeit Hash-Verfahren für Strings beliebiger existiert Längen, wie durch das andere Mitglied sO beansprucht wurde.

Danke.

Answer 1

Generell glaube ich, dass jeder vollständige String Hash jedes Zeichen der Zeichenkette verwenden müssen und deshalb brauchen würde als O (n) für n Zeichen wachsen. Aber ich denke, für die praktische String-Hashes können Sie ungefähren Hashes verwenden, die O leicht sein kann (1).

einen String Hash betrachten, die immer verwendet Min (n, 20) einen Standard-Zeichen-Hash zu berechnen. Offensichtlich wächst als O (1) mit Stringgröße. Wird es zuverlässig funktioniert? Es hängt von Ihrer Domain ...

Answer 2

Eine Hash-Funktion muss nicht (und kann) einen eindeutigen Wert für jeden String zurück.

Sie könnten die ersten 10 Zeichen verwenden einen Zufallszahlengenerator zu initialisieren und dann verwenden, um herausziehen 100 zufällige Zeichen aus der Zeichenfolge, und Hash, der. Dies wäre konstante Zeit.

Sie können auch zurückkehren nur den konstanten Wert 1. Streng genommen ist dies immer noch eine Hash-Funktion ist, die aber nicht sehr nützlich.

Answer 3

Sie können nicht einfach eine allgemeine konstante Zeit Hashing-Algorithmus für Strings erreichen, ohne schwere Fälle von Hash-Kollisionen zu riskieren.

Für die konstante Zeit sein, werden Sie nicht in der Lage sein, jedes Zeichen in der Zeichenfolge zuzugreifen. Als ein einfaches Beispiel an, dass wir die ersten 6 Zeichen nehmen. Dann kommt jemand und versucht, eine Reihe von URLs Hash. Die hat Funktion finden Sie unter „http: /“. Für jede einzelne Saite

ähnliche Szenarien können für andere Zeichen Auswahlschemata auftreten. Sie könnten Zeichen pseudo-zufällig basierend auf dem Wert des vorherigen Zeichens wählen, aber immer noch die Gefahr, dass spektakulär, wenn die Strings aus irgendeinem Grunde laufen die „falschen“ Muster und viel am Ende mit dem gleichen Hash-Wert haben.

Answer 4

Sie können Hoffnung für asymptotisch weniger als die Zeit linear Hashing, wenn Sie

Obwohl ich kann keine feste Zeit Hash-Funktion für unbegrenzte Länge Strings vorstellen, gibt es wirklich keine Notwendigkeit dafür.

Die Idee, eine Hash-Funktion hinter der Verwendung ist eine Verteilung der Hash-Werte zu erzeugen, die es macht unwahrscheinlich, dass viele Strings würden kollidieren - für die Domäne betrachteten. Dieser Schlüssel würde einen direkten Zugang zu einem Datenspeicher ermöglichen. Diese beiden kombinierten Ergebnis in einem konstante Zeit Lookup -. Im Durchschnitt

Wenn es jemals eine solche Kollision auftritt, die Lookup-Algorithmus greift auf eine flexiblere Lookup-Teilstrategie.

Das ist sicherlich machbar, so lange, wie Sie sicherstellen, alle Ihre Strings ‚interniert‘, bevor Sie sie auf etwas passieren erfordern Hashing. Interning ist der Prozess, die Zeichenfolge in eine Kettentabelle des Einführens ist, so dass alle internierten Strings mit dem gleichen Wert in der Tat das gleiche Objekt. Dann können Sie einfach hash die (feste Länge) Zeiger auf die internierten String, statt Hashing die Zeichenfolge selbst.

Sie können in der folgenden mathematischen Ergebnis interessiert sein, die ich mit dem letzten Jahr kam.

Betrachten Sie das Problem, eine unendliche Anzahl von Hash-Schlüssel-wie die Menge aller Strings beliebiger Länge zu dem Satz von Zahlen in {1,2, ..., b}. Random Hashing verläuft, indem zunächst zufällig Hashfunktion h in einer Familie von H-Funktionen Kommissionieren.

ich zeigen, dass es immer eine unendliche Anzahl von Tasten, die sich sicher sind, über alle H-Funktionen kollidieren, das heißt, 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 (n) = y} unendlich ist, das heißt, Sie haben unendlich viele Saiten zu kollidieren. Pick andere Hash-Funktion h 'und Raute der Schlüssel in der Menge A. Es gibt mindestens einen Hash-Wert y', so daß die Menge A '= {s ist in A: h' (n) = y '} ist unendlich, das heißt, es gibt unendlich viele Saiten auf zwei Hash-Funktionen kollidieren. Sie können dieses Argument beliebig oft wiederholen. Wiederholen Sie es H mal. Dann sind Sie eine unendliche Menge von Strings, wo alle Saiten über alle Ihre H Hash-Funktionen kollidieren. CQFD.

Weiterführende Literatur : Sensible Hashing von Zeichenfolgen variabler Länge ist unmöglich http: // lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/

Answer 5

Answer 6

Answer 7

Obwohl ich kann keine feste Zeit Hash-Funktion für unbegrenzte Länge Strings vorstellen, gibt es wirklich keine Notwendigkeit dafür.

Die Idee, eine Hash-Funktion hinter der Verwendung ist eine Verteilung der Hash-Werte zu erzeugen, die es macht unwahrscheinlich, dass viele Strings würden kollidieren - für die Domäne betrachteten. Dieser Schlüssel würde einen direkten Zugang zu einem Datenspeicher ermöglichen. Diese beiden kombinierten Ergebnis in einem konstante Zeit Lookup -. Im Durchschnitt

Wenn es jemals eine solche Kollision auftritt, die Lookup-Algorithmus greift auf eine flexiblere Lookup-Teilstrategie.

Answer 8

Das ist sicherlich machbar, so lange, wie Sie sicherstellen, alle Ihre Strings ‚interniert‘, bevor Sie sie auf etwas passieren erfordern Hashing. Interning ist der Prozess, die Zeichenfolge in eine Kettentabelle des Einführens ist, so dass alle internierten Strings mit dem gleichen Wert in der Tat das gleiche Objekt. Dann können Sie einfach hash die (feste Länge) Zeiger auf die internierten String, statt Hashing die Zeichenfolge selbst.

Answer 9

Das ist sicherlich machbar, so lange, wie Sie sicherstellen, alle Ihre Strings ‚interniert‘, bevor Sie sie auf etwas passieren erfordern Hashing. Interning ist der Prozess, die Zeichenfolge in eine Kettentabelle des Einführens ist, so dass alle internierten Strings mit dem gleichen Wert in der Tat das gleiche Objekt. Dann können Sie einfach hash die (feste Länge) Zeiger auf die internierten String, statt Hashing die Zeichenfolge selbst.

Answer 10

Sie können in der folgenden mathematischen Ergebnis interessiert sein, die ich mit dem letzten Jahr kam.

Betrachten Sie das Problem, eine unendliche Anzahl von Hash-Schlüssel-wie die Menge aller Strings beliebiger Länge zu dem Satz von Zahlen in {1,2, ..., b}. Random Hashing verläuft, indem zunächst zufällig Hashfunktion h in einer Familie von H-Funktionen Kommissionieren.

ich zeigen, dass es immer eine unendliche Anzahl von Tasten, die sich sicher sind, über alle H-Funktionen kollidieren, das heißt, 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 (n) = y} unendlich ist, das heißt, Sie haben unendlich viele Saiten zu kollidieren. Pick andere Hash-Funktion h 'und Raute der Schlüssel in der Menge A. Es gibt mindestens einen Hash-Wert y', so daß die Menge A '= {s ist in A: h' (n) = y '} ist unendlich, das heißt, es gibt unendlich viele Saiten auf zwei Hash-Funktionen kollidieren. Sie können dieses Argument beliebig oft wiederholen. Wiederholen Sie es H mal. Dann sind Sie eine unendliche Menge von Strings, wo alle Saiten über alle Ihre H Hash-Funktionen kollidieren. CQFD.

Weiterführende Literatur : Sensible Hashing von Zeichenfolgen variabler Länge ist unmöglich http: // lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/

Answer 11

Answer 12

Sie können in der folgenden mathematischen Ergebnis interessiert sein, die ich mit dem letzten Jahr kam.

Betrachten Sie das Problem, eine unendliche Anzahl von Hash-Schlüssel-wie die Menge aller Strings beliebiger Länge zu dem Satz von Zahlen in {1,2, ..., b}. Random Hashing verläuft, indem zunächst zufällig Hashfunktion h in einer Familie von H-Funktionen Kommissionieren.

ich zeigen, dass es immer eine unendliche Anzahl von Tasten, die sich sicher sind, über alle H-Funktionen kollidieren, das heißt, 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 (n) = y} unendlich ist, das heißt, Sie haben unendlich viele Saiten zu kollidieren. Pick andere Hash-Funktion h 'und Raute der Schlüssel in der Menge A. Es gibt mindestens einen Hash-Wert y', so daß die Menge A '= {s ist in A: h' (n) = y '} ist unendlich, das heißt, es gibt unendlich viele Saiten auf zwei Hash-Funktionen kollidieren. Sie können dieses Argument beliebig oft wiederholen. Wiederholen Sie es H mal. Dann sind Sie eine unendliche Menge von Strings, wo alle Saiten über alle Ihre H Hash-Funktionen kollidieren. CQFD.

Answer 13

Weiterführende Literatur : Sensible Hashing von Zeichenfolgen variabler Länge ist unmöglich