2009-12-07 23 views
5

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.

Antwort

4

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

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

7

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

Sie könnten die ersten 10 Zeichen verwenden, um einen Zufallszahlengenerator zu initialisieren und dann 100 Zufallszeichen aus der Zeichenfolge 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, obwohl nicht sehr nützlich.

+3

Erinnert mich an http://xkcd.com/221/ –

+1

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. –

1

Sie können Hoffnung für asymptotisch kleiner als lineare Hashing-Zeit, wenn Sie ropes anstelle von Strings verwenden und die gemeinsame Nutzung haben, dass Sie einige Berechnungen überspringen können. Aber offensichtlich kann eine Hash-Funktion Eingaben, die sie nicht gelesen hat, nicht trennen, deshalb würde ich das "alles kann nicht in konstanter Zeit" zu ernst genommen werden.

Alles ist möglich in dem Kompromiss zwischen der Qualität der Hash-Funktion und der Menge an Berechnungen, die es braucht, und eine Hash-Funktion über lange Strings muss sowieso Kollisionen haben.

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

1

Obwohl ich mir keine feste Hash-Funktion für Strings mit unbegrenzter Länge vorstellen kann, ist es wirklich nicht nötig.

Die Idee hinter der Verwendung einer Hash-Funktion besteht darin, eine Verteilung der Hash-Werte zu generieren, die es unwahrscheinlich macht, dass viele Zeichenfolgen kollidieren würden - für die betrachtete Domäne. Dieser Schlüssel würde direkten Zugriff auf einen Datenspeicher ermöglichen. Diese beiden zusammen ergeben eine konstante Zeit-Lookup - im Durchschnitt.

Wenn eine solche Kollision auftritt, greift der Suchalgorithmus auf eine flexiblere Suchunterstrategie zurück.

+0

Ich stimme dir zu, aber im Fall eines Sprachkonstrukts wie einem assoziativen Array, möchtest du nicht so nahe wie möglich an der Gewährleistung der Einzigartigkeit sein? –

3

Sie können nicht einfach einen allgemeinen konstanten Hashing-Algorithmus für Strings erreichen, ohne schwere Fälle von Hash-Kollisionen zu riskieren.

Damit die Zeit konstant bleibt, können Sie nicht auf alle Zeichen in der Zeichenfolge zugreifen. Als einfaches Beispiel nehmen wir an, wir nehmen die ersten 6 Zeichen. Dann kommt jemand und versucht ein Array von URLs zu hacken. Die has-Funktion sieht für jede einzelne Zeichenfolge "http: /".

Ähnliche Szenarien können für andere Zeichenauswahlschemata auftreten. Sie könnten Zeichen pseudozufällig basierend auf dem Wert des vorherigen Zeichens auswählen, aber Sie laufen immer noch Gefahr, spektakulär zu versagen, wenn die Zeichenfolgen aus irgendeinem Grund das "falsche" Muster haben und viele denselben Hashwert haben.

1

Sicherlich ist dies machbar, solange Sie sicherstellen, dass alle Ihre Strings "interniert" sind, bevor Sie sie an etwas übergeben, das Hashing erfordert. Intern ist der Prozess des Einfügens der Zeichenfolge in eine Zeichenfolge-Tabelle, so dass alle internierten Zeichenfolgen mit demselben Wert tatsächlich dasselbe Objekt sind. Dann können Sie einfach den (festen) Zeiger auf die interne Zeichenfolge hashen, anstatt die Zeichenfolge selbst zu hashen.

+0

Eine gute Idee, aber es lohnt sich zu beachten, dass der Prozess des Einfügens in eine String-Tabelle Zeit proportional zur Anzahl der Strings in der Tabelle hinzufügen würde, es sei denn, die Tabelle wäre Hash-basiert. In diesem Fall wird das Problem auf das Original reduziert Zustand. – Peter

+0

Nun, mit einem Trie, ist die Zeit, die eingefügt wird, proportional zum längsten gemeinsamen Präfix, was eine andere Option ist. :) –

+0

@Nick Johnson du mißgibst mich, denke ich. Ich bin auf der Suche nach einem konstanten Zeit Weg, Strings eindeutig zu identifizieren. Das bedeutet, dass Sie, wenn ich Ihnen zwei neue Strings vorlege, diese in konstanter Zeit "hacken" können, so dass, wenn eine Zeichenkette 500 Zeichen und die nächste 5 Zeichen lang ist, die gleiche theoretische Zeit zur Bestimmung der Eindeutigkeit verwendet wird. –

1

Vielleicht interessieren Sie sich für das folgende mathematische Ergebnis, das ich letztes Jahr entwickelt habe.

Betrachten Sie das Problem der Hashing eine unendliche Anzahl von Schlüsseln - wie die Menge aller Zeichenfolgen beliebiger Länge - zu der Menge der Zahlen in {1,2, ..., b}. Random Hashing geht davon aus, dass zunächst zufällig eine Hash-Funktion h in einer Familie von H-Funktionen ausgewählt wird.

Ich werde zeigen, dass es immer eine unendliche Anzahl von Schlüsseln gibt, die sicher ü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 (s) = y} unendlich ist, dh Sie haben unendlich viele Strings kollidieren. Wähle irgendeine andere Hash-Funktion h 'und hase die Schlüssel in der Menge A. Es gibt mindestens einen Hash-Wert y', so dass die Menge A '= {s ist in A: h' (s) = y '} unendlich ist, Das bedeutet, dass unendlich viele Strings auf zwei Hash-Funktionen zusammentreffen.Sie können dieses Argument beliebig oft wiederholen. Wiederholen Sie es H-mal. Dann haben Sie eine unendliche Reihe von Strings, in denen alle Strings über all Ihre H-Hash-Funktionen kollidieren. CQFD.

Weitere Lesen: 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/

Verwandte Themen