Ich möchte eine Hash-Map (oder eine andere Struktur, falls Sie Vorschläge haben) erstellen, um Schlüsselwertpaare zu speichern. Die Schlüssel werden alle zur selben Zeit eingefügt, wie die Karte erstellt wird, aber ich weiß nicht, was die Schlüssel sein werden (Strings mit beliebiger Länge) bis zur Laufzeit, wenn ich die Karte erstellen muss.
Ich analysiere eine Abfrage-Zeichenfolge wie diese "x=100&name=bob&color=red&y=150" (aber die Zeichenfolge kann eine unbegrenzte Anzahl von Variablen haben und die Variablen können einen beliebigen Längennamen haben).
Ich möchte es einmal analysieren und eine Hash-Map erstellen, vorzugsweise minimal und mit einer perfekten Hash-Funktion, um lineare Speicheranforderungen zu erfüllen. Sobald die Karte erstellt wurde, werden die Werte nicht geändert oder gelöscht, es werden auch keine weiteren Schlüsselwertpaare zur Karte hinzugefügt, sodass die gesamte Karte praktisch eine Konstante ist. Ich gehe davon aus, dass eine Variable nicht zweimal in der Zeichenfolge auftritt (IE.% Co_de% ist nicht gültig).
Ich codiere in "x=1&x=2" und habe momentan eine Funktion, die ich wie C benutzen kann, die die Zeichenkette get("x") zurückgibt, aber sie analysiert jedes Mal die Abfragezeichenfolge, die "100" time benötigt. Ich möchte es beim ersten Laden einmal analysieren, da es sich um einen sehr großen Abfrage-String handelt und jeder Wert mehrmals gelesen wird. Obwohl ich O(n) verwende, brauche ich keinen Code in C als Antwort. Pseudocode oder irgendwelche Vorschläge wären großartig!
Versuchen Sie GPL gperf , oder Bob Jenkins Public-Domain-Implementierung in C
Vorgehensweise:
empfängt die Abfragezeichenfolge und identifiziert die Domäne der perfekten Hashfunktion durch Aufzählung der Schlüsselliste
stellt diese Schlüssel und die Listengröße (der Bereich wird 1..size sein) für die perfekte Hash-Generierungsfunktion bereit, die von den obigen Referenzimplementierungen abgeleitet wird
Verwenden Sie die perfekte Hash-Funktion, die zum Erstellen der HashMap generiert wurde
Verwenden Sie dieselbe perfekte Hash-Funktion, um die get -Anforderungen in der HashMap
Bearbeiten Necrolis hat im Kommentar unten notiert, dass die Referenzimplementierungen perfekte Hash-Funktionen im C-Quellcode ausgeben. Daher müssen Sie sie modifizieren, um stattdessen etwas wie einen Bytecode für eine VM zu generieren. Sie könnten auch eine interpretierende Sprache wie Embedded Scheme oder Lua verwenden.
Es wäre interessant zu wissen, ob sich die Mühe über eine einfache (nicht perfekte) HashMap lohnt, wenn sich der Aufwand für die Erstellung der perfekten Hash-Funktion über die Nachschlagewerke amortisiert.
Eine andere Option ist Kuckuckshashing , die auch O (1) Lookups hat
Es gibt einige sehr gute Hash-Routinen; Um jedoch zu beweisen, dass einer von ihnen nahezu perfekt ist, ist viel Wissen über die Eingaben erforderlich. Es scheint, dass Ihre Eingaben nicht eingeschränkt genug sind, um einen solchen Beweis nahezu unmöglich zu machen.
Im Allgemeinen ist eine perfekte (oder nahezu perfekte) Routine für jedes Bit / Byte der Eingabe empfindlich. Für die Geschwindigkeit ist die Kombinationsoperation typischerweise XOR. Die Art und Weise, wie solche Routinen verhindern, dass sich zwei identische Bytes gegenseitig auslöschen, besteht darin, die Bits zu verschieben oder zu drehen. Eine solche Verschiebung sollte jedoch durch eine Zahl erfolgen, die eine relative Primzahl zu der maximal darstellbaren Zahl ist; Andernfalls könnten Muster in der Eingabe teilweise durch vorherige Eingabe abgebrochen werden. Dies verringert die Entropie in der Lösung und erhöht die Wahrscheinlichkeit einer Kollision.
Die typische Lösung ist
%Vor%Die Probleme mit einer solchen Routine sind bekannt. Im Grunde gibt es einen Mangel an Variation in der Eingabe, und dies macht das Dispergieren der Eingabe nicht ideal. Das heißt, diese Technik ergibt eine gute Streuung von Eingabebits über die gesamte Domäne von Ausgaben, vorausgesetzt, es gibt eine ausreichende Eingabe, um von der anfänglichen Hauptstartnummer wegzulaufen. Leider ist das Auswählen einer zufälligen Startnummer keine Lösung, da es dann unmöglich wird, den Hash genau zu berechnen.
In jedem Fall darf die in der Multiplikation zu verwendende Primzahl die Multiplikation nicht überlaufen lassen. Ebenso muss das Erfassen höherwertiger Bits in der niedrigen Reihenfolge ersetzt werden, wenn Sie vermeiden möchten, dass Dispersionseffekte der ursprünglichen Eingabe verloren gehen (und das Ergebnis nur um die letzteren Bits / Bytes gruppiert wird). Die Auswahl der Primzahlen beeinflusst die Streuung, und manchmal ist eine Abstimmung für einen guten Effekt erforderlich.
Inzwischen sollten Sie leicht erkennen können, dass ein nahezu perfekter Hash mehr Rechenzeit benötigt als ein anständiger weniger als fast perfekter Hashwert. Hash-Algorithmen wurden entwickelt, um Kollisionen zu berücksichtigen, und die meisten Java-Hash-Strukturen passen sich an Belegungsschwellen an (normalerweise im Bereich von 70%, aber es ist einstellbar). Da die Größenanpassung eingebaut ist, werden Sie, solange Sie keinen schrecklichen Hashwert schreiben, die Java-Datenstrukturen weiterhin so abstimmen, dass Sie weniger Kollisionserscheinungen haben.
Optimierungen, die einen Hash beschleunigen können, umfassen das Berechnen von Bitgruppen, das Löschen von gelegentlich Byte-, Vorberechnungs-Nachschlagtabellen mit häufig verwendeten multiplizierten Zahlen (indiziert durch Eingabe) usw. Gehen Sie nicht davon aus, dass eine Optimierung schneller ist, abhängig In Bezug auf Architektur, Maschinendetails und "Alter" der Optimierung bleiben manchmal die Annahmen der Optimierung nicht mehr erhalten und die Anwendung der Optimierung erhöht tatsächlich die Zeit zur Berechnung des Hash.
In dem, was Sie beschreiben, gibt es kein perfektes Hash. Ein perfekter Hash wäre die ursprüngliche Eingabe. Wenn Sie sicher sind, dass Ihre Daten nur bestimmte Dinge sind (wie zum Beispiel lateinisches ASCII oder nur bestimmte Schlüssel), können Sie gut hacken, aber perfekt? Nein. Nicht möglich. Sie müssen auch einen Link-List- oder Vektor-Hash-Fehltreffer-Mechanismus erstellen. Jede Variante im System (wie die Anzahl der Eingaben in Ihrem Fall) macht das perfekte Hash-Konzept ungültig.
Was Sie wollen, widersetzt sich den Gesetzen der Mathematik.
Sie können nahe O (1) erreichen, aber es gibt hier unbeantwortete Fragen. Die Fragen sind:
Obwohl ein perfekter Hash nicht möglich ist, wird es völlig akademisch, wenn Sie einfach eine einfache verknüpfte Liste mit einer Bucket-Größe haben, die mindestens zwei Standardabweichungen vom Mittelwert Ihrer möglichen eindeutigen Hashes entfernt. Es ist minimal Speicher (relativ natürlich und abhängig von der gesamten potenziellen Größe), löschungsfreundlich, und wäre fast O (1) Lookup-Zeit, solange Frage 3 so etwas wie "viel kleiner" beantwortet wird .
Folgendes sollte Sie zum Einstieg bringen, aber ich überlasse Entscheidungen darüber, welcher Hash-Algorithmus Sie verwenden soll ...
%Vor% Anwendungsbeispiele (als Assertions) und Effizienztests. Verwenden Sie int als Datenwerttyp ...
Zusätzlich habe ich einige Tests mit 100.000 zufällig generierten ASCII-Schlüsseln mit Längen zwischen 5 und 1000 Zeichen durchgeführt, die folgendes zeigten:
Wie Sie sehen können, hat es das Potenzial, sich gut zu entwickeln. Eine Effizienz von 80% bedeutet, dass ungefähr 80% der Suchvorgänge O (1) sind, ungefähr 16% der Suchvorgänge O (2) sind, ungefähr 3,2% der Suchvorgänge O (3) sind und ungefähr 0,8% Suchvorgänge sind O (4+). Dies bedeutet, dass eine Suche im Durchschnitt O (1.248)
dauertGleichermaßen bedeutet eine Effizienz von 50%, dass 50% der Nachschlagevorgänge O (1), 25% O (2), 12,5% O (3) und 12,5% O (4 +)
Sie müssen wirklich nur den richtigen Hash-Algorithmus für Ihre bekannten Faktoren auswählen (oder schreiben) und die Dinge für Ihre speziellen Bedürfnisse optimieren.
Anmerkungen:
move() , swap() , sort() , insert() usw. hinzufügen, indem Sie entry->prev und entry->next verwalten.
Wenn Sie die Menge aller möglichen Variablennamen kennen, dann wäre es möglich, die Namen auf Zahlen zu perfektionieren
aber jede der Hash-Tabellen würde am Ende die gleiche Länge haben ein Beispiel ist, wenn X und y die Namen sind, dann wäre die Karte immer von Länge 2
wenn perfect(str) 'x' und 'y' zu 0 und 1 macht; dann wäre die Funktion get
Tags und Links c hash perfect-hash