Offline Hash-Lookup mit 55 Mio. Datensätzen – wie löst man das ohne Datenbank?

[LordOfHelm]

Hallo zusammen,

ich stehe aktuell vor einer Herausforderung, bei der ich hoffe, dass mir jemand aus der Community weiterhelfen kann.

Für ein berufliches Projekt habe ich eine offlinefähige HTML-Seite mit einer eingebetteten Datenstruktur entwickelt. Ziel ist es, Kennziffern zu speichern und daraus mittels eines Hash-Verfahrens nicht umkehrbare Output-Werte zu generieren. Beispiel:

Eingabe (Kennziffer): 9000
Ausgabe (gehashter Wert): 14194901194611390735
Die Hashing-Methode ist bewusst so gewählt, dass keine Rückrechnung möglich ist. Soweit funktioniert alles.

Das Problem
Die Suche innerhalb der Seite funktioniert aktuell nur über die ursprüngliche Kennziffer. Das Problem ist: der Nutzer kennt in der Praxis nur den Output-Wert, z. B. 14194901194611390735, und möchte wissen, welche Kennziffer dahintersteckt. Da der Hash nicht umkehrbar ist, ist ein direkter Lookup aktuell nur auf der aktiven Seite mit den angezeigten Daten möglich.

Und genau hier liegt der Haken:
Ich habe 55 Millionen solcher Kennziffern
Pro HTML-Seite werden 500 Datensätze generiert
Das ergibt über 110.000 Seiten

Es gibt keine zentrale Datenbank zur Suche, weil aus Speicher- und Performancegründen alles offline und möglichst klein gehalten werden soll

Einschränkungen
Das gesamte Projekt (HTML, CSS, JavaScript + Datenstruktur) soll offline lauffähig und unter 100 MB bleiben

Der Einsatz eines Server-Backends oder großer Datenbanken (>5 GB) ist nicht möglich oder gewünscht

Die Datenstruktur wächst jährlich um mehrere Millionen Datensätze

Was ich bisher versucht habe
Ich habe überlegt, beim Laden jeder Seite 500 neue Kennziffern zu erzeugen und deren gehashte Outputs direkt clientseitig berechnen zu lassen. Das funktioniert gut für die Anzeige – aber nicht für die Suche nach einem bestimmten Output-Wert.
Eine umgekehrte Hash-Suche ist natürlich ausgeschlossen, da das Verfahren absichtlich keine Rückwärtsauflösung erlaubt.

Meine Frage
Gibt es eine effiziente Möglichkeit, mit der ein Nutzer bei Eingabe eines Output-Werts wie 14194901194611390735 die zugehörige Kennziffer offline ermitteln kann – ohne dass ich eine vollständige Datenbank mit allen 55 Millionen Hash-Paaren speichern oder laden muss?

Mir ist klar, dass eine vollständige Map (Kennziffer → Hash) dafür nötig wäre – aber gibt es ggf. ein smarteres Vorgehen wie:

Bloomfilter mit Rückverweis?

Gezielte Partitionierung?

Hash-Index mit gezieltem Zugriff?

Ich bin für jeden technischen Denkanstoß oder Lösungsansatz offen – auch gerne minimalistische Kompressionsverfahren oder Lookup-Strategien.

Vielen Dank im Voraus für jede Unterstützung!
Ich tüftele jetzt seit Tagen an diesem Ding und komme nicht weiter.

Hier nur ein Beispiel, wie die Kennziffern und deren Ergebnisse aussehen:
9000 | 14194901194611390735
9001 | 1420772774969051074
9002 | 16576014318843989704

 

[Sempervivum]

Mein erster Gedanke: Bei deiner Randbedingung, max. Speicherplatz 100 MB, ist es nicht möglich, den vollständigen Datenbestand mit Kennziffern und Ergebnissen vorzuhalten. Bleibt nur eine lineare Suche, wobei bei jeder Kennziffer das Ergebnis bzw. der Hash ermittelt und mit dem zu suchenden Wert verglichen wird. Bei Millionen von Kennziffern wird die Performance indiskutabel werden.

Mein zweiter Gedanke: Nur die Kennziffern speichern aber in einem einmaligen Initialisierungslauf nicht nach der Kennziffer selbst sondern nach dem Hash sortieren. Wenn so die Kennziffern sortiert gespeichert sind, ohne die Hashs, kann man eine binäre Suche durchführen und bei jedem Vergleich die beiden Hashs on-the-fly ermitteln und vergleichen. Auf diese Weise muss man nicht alle Kennziffern durchsuchen und den Hash ermitteln wodurch sich die Performance entscheidend verbessern dürfte.

Was die Implementierung betrifft, könnte man prüfen, ob man die Browser-interne Indexed-DB verwenden kann. In die Frage, wie weit diese Suchverfahren bereit stellt, die ebenfalls dein Problem lösen könnten, bin ich nicht eingestiegen.

 

[Sempervivum]

PS, dritter Gedanke: Das Beschriebene funktioniert nur wenn der Hash rein durch einen Algorithmus aus der Kennziffer ermittelt wird. Werden dabei zusätzlich andere Daten benötigt, geht es nicht.