Ich habe 111 Millionen Schlüssel-Wert-Paare gespeichert (ein Schlüssel kann mehrere Werte haben - maximal 2/3), deren Schlüssel 50-Bit-Ganzzahlen und Werte sind 32-Bit (maximal) Ganzzahlen. Jetzt sind meine Anforderungen:
- Schnelles Einfügen von (Schlüssel, Wert) Paar [Erlaube Duplikate]
- Schnelles Abrufen von Werten / Werten basierend auf Schlüssel.
Eine nette Lösung davon ist hier basierend auf MultiMap. Ich möchte jedoch mehr Schlüssel / Wert-Paare im Hauptspeicher speichern, ohne die Leistung zu beeinträchtigen. Ich habe aus Webartikeln gelernt, dass B + Baum, R + Baum, B Baum, Kompakt Multimap etc. eine schöne Lösung dafür sein können. Kann mir jemand helfen?
Gibt es eine Java-Bibliothek, die all diese Bedürfnisse richtig erfüllt? (oben erwähnt / andere ds auch akzeptabel. kein Problem damit)? Eigentlich möchte ich eine effiziente Java-Bibliothek Datenstruktur zum Speichern / Abrufen Schlüssel-Wert / Werte-Paare, die weniger Speicherbedarf haben und sein müssen Eingebauter Speicher.
NB: Ich habe mit HashMultiMap (Guava mit einigen Modifikationen mit Trove) versucht, wie von Louis Wasserman, Kyoto / Tokyo Cabinet etc. erwähnt. Meine Erfahrung ist nicht gut mit Disk-gebackenen Lösungen. Also bitte vermeide das :). Ein anderer Punkt ist, dass für die Auswahl von Bibliothek / ds ein wichtiger Punkt ist: Schlüssel sind 50 Bit (wenn wir also 64 Bit zuweisen) werden 14 Bit verloren und Werte sind 32 Bit Int (Maximum) - meistens sind es 10-12-14 Bits. So können wir dort auch Platz sparen.
Ich glaube nicht, dass es irgendwas im JDK gibt, das das tun wird.
Das Implementieren einer solchen Sache ist jedoch eine einfache Sache der Programmierung. Hier ist eine offen adressierte Hashtabelle mit linearem Sondieren, wobei Schlüssel und Werte in parallelen Arrays gespeichert sind:
%Vor%Beachten Sie, dass dies eine Struktur fester Größe ist. Sie müssen es groß genug, um alle Ihre Daten zu halten - 110 Millionen Einträge für mich nimmt 1,32 GB. Je größer Sie es machen, über das hinaus, was Sie zum Speichern der Daten benötigen, desto schneller werden Einfügungen und Suchvorgänge durchgeführt. Ich fand heraus, dass für 110 Millionen Einträge mit einem Ladefaktor von 0,5 (2,64 GB, doppelt so viel Speicherplatz wie nötig) durchschnittlich 403 Nanosekunden benötigt wurden, um einen Schlüssel zu suchen, aber mit einem Ladefaktor von 0,75 (1,76 GB, a Drittel mehr Platz als benötigt wird), dauerte es 575 Nanosekunden. Eine Verringerung des Lastfaktors unter 0,5 macht normalerweise keinen großen Unterschied, und tatsächlich erreicht ich mit einem Lastfaktor von 0,33 (4,00 GB, dreimal mehr Platz als benötigt) eine durchschnittliche Zeit von 394 Nanosekunden. Also, obwohl Sie 5 GB zur Verfügung haben, verwenden Sie nicht alles.
Beachten Sie auch, dass Null als Schlüssel nicht zulässig ist. Wenn dies ein Problem ist, ändern Sie den Nullwert, um etwas anderes zu sein, und füllen Sie das Schlüsselarray mit diesem bei der Erstellung voraus.
Es ist eine gute Idee, nach Datenbanken zu suchen, weil solche Probleme für sie typisch sind. In den letzten Jahren wurden Key-Value-Datenbanken sehr populär, z. für Webservices (Stichwort "NoSQL") sollte man also etwas finden.
Die Wahl für eine benutzerdefinierte Datenstruktur hängt auch davon ab, ob Sie eine Festplatte verwenden möchten, um Ihre Daten zu speichern (und wie sicher diese sein muss) oder ob sie beim Programmende vollständig verloren geht.
Wenn ich die Implementierung manuell durchführe und die ganze db leicht in den Speicher passt, würde ich einfach eine hashmap in C implementieren. Erstellen Sie eine Hash-Funktion, die aus einem Wert eine (gut verbreitete) Speicheradresse ergibt. Fügen Sie dort oder daneben ein, wenn Sie bereits zugewiesen sind. Zuweisen und Abrufen ist dann O (1). Wenn Sie es in Java implementieren, haben Sie den 4-Byte-Overhead für jedes (primitive) Objekt.
Basierend auf @ Tom Andersons Lösung habe ich die Notwendigkeit, Objekte zuzuweisen, entfernt und einen Leistungstest hinzugefügt.
%Vor%druckt
%Vor%Laufen Sie auf einem 3,8 GHz i7 mit Java 7 Update 3.
Dies ist viel langsamer als der vorherige Test, weil Sie auf den Hauptspeicher und nicht zufällig auf den Cache zugreifen. Dies ist wirklich ein Test für die Geschwindigkeit Ihres Gedächtnisses. Die Schreibvorgänge sind schneller, da sie asynchron zum Hauptspeicher ausgeführt werden können.
Diese Sammlung verwenden
%Vor% Wenn ich den gleichen Test mit 50 Millionen Einträgen (die etwa 16 GB benutzten) und -mx20g durchführe, gehe ich zu folgendem Ergebnis.
Für 110 M Einträge benötigen Sie etwa 35 GB Arbeitsspeicher und eine Maschine 10 x schneller als meine (3,8 GHz), um 5 Millionen Adds pro Sekunde durchzuführen.
Wenn Sie Java verwenden müssen, implementieren Sie Ihre eigene Hashtabelle / hashmap. Eine wichtige Eigenschaft Ihrer Tabelle ist die Verwendung einer verketteten Liste zur Behandlung von Kollisionen. Wenn Sie also nachschlagen, können Sie alle Elemente in der Liste zurückgeben.