Ich möchte eine große HashMap erstellen, aber die put()Leistung ist nicht gut genug. Irgendwelche Ideen?

Andere Vorschläge zur Datenstruktur sind willkommen, aber ich benötige die Suchfunktion einer Java Map:

map.get(key)

In meinem Fall möchte ich eine Karte mit 26 Millionen Einträgen erstellen. Mit der Standard-Java-HashMap wird die Put-Rate nach 2-3 Millionen Einfügungen unerträglich langsam.

Weiß jemand auch, ob die Verwendung unterschiedlicher Hashcode-Verteilungen für die Schlüssel hilfreich sein könnte?

Meine Hashcode-Methode:

byte[] a = new byte[2];
byte[] b = new byte[3];
...

public int hashCode() {
    int hash = 503;
    hash = hash * 5381 + (a[0] + a[1]);
    hash = hash * 5381 + (b[0] + b[1] + b[2]);
    return hash;
}

Ich verwende die assoziative Eigenschaft der Addition, um sicherzustellen, dass gleiche Objekte den gleichen Hashcode haben. Die Arrays sind Bytes mit Werten im Bereich von 0 bis 51. Werte werden in beiden Arrays nur einmal verwendet. Die Objekte sind gleich, wenn die a-Arrays dieselben Werte enthalten (in beliebiger Reihenfolge) und dasselbe für das b-Array gilt. Also sind a = {0,1} b = {45,12,33} und a = {1,0} b = {33,45,12} gleich.

EDIT, einige Anmerkungen:

• Einige Leute haben kritisiert, 26 Millionen Einträge mithilfe einer Hash-Karte oder einer anderen Datenstruktur zu speichern. Ich kann nicht verstehen, warum das seltsam erscheint. Es sieht für mich nach einem klassischen Problem mit Datenstrukturen und Algorithmen aus. Ich habe 26 Millionen Elemente und möchte sie schnell in eine Datenstruktur einfügen und nachschlagen können: Geben Sie mir die Datenstruktur und die Algorithmen.

• Das Festlegen der Anfangskapazität der Standard-Java-HashMap auf 26 Millionen verringert die Leistung.

• Einige Leute haben vorgeschlagen, Datenbanken zu verwenden, in anderen Situationen ist dies definitiv die kluge Option. Aber ich stelle wirklich eine Frage zu Datenstrukturen und Algorithmen. Eine vollständige Datenbank wäre übertrieben und viel langsamer als eine gute Datenstrukturlösung (schließlich ist die Datenbank nur Software, hätte aber Kommunikation und möglicherweise Overhead auf der Festplatte).

Wie viele Leute betonten, war die hashCode()Methode schuld. Es wurden nur rund 20.000 Codes für 26 Millionen verschiedene Objekte generiert. Das sind durchschnittlich 1.300 Objekte pro Hash-Bucket = sehr, sehr schlecht. Wenn ich jedoch die beiden Arrays in eine Zahl in Basis 52 verwandle, erhalte ich garantiert einen eindeutigen Hash-Code für jedes Objekt:

public int hashCode() {       
    // assume that both a and b are sorted       
    return a[0] + powerOf52(a[1], 1) + powerOf52(b[0], 2) + powerOf52(b[1], 3) + powerOf52(b[2], 4);
}

public static int powerOf52(byte b, int power) {
    int result = b;
    for (int i = 0; i < power; i++) {
        result *= 52;
    }
    return result;
}

Die Arrays werden sortiert, um sicherzustellen, dass diese Methoden den hashCode()Vertrag erfüllen, dass gleiche Objekte denselben Hashcode haben. Unter Verwendung der alten Methode betrug die durchschnittliche Anzahl von Puts pro Sekunde über Blöcke von 100.000 Puts, 100.000 bis 2.000.000:

168350.17
109409.195
81344.91
64319.023
53780.79
45931.258
39680.29
34972.676
31354.514
28343.062
25562.371
23850.695
22299.22
20998.006
19797.799
18702.951
17702.434
16832.182
16084.52
15353.083

Die Verwendung der neuen Methode ergibt:

337837.84
337268.12
337078.66
336983.97
313873.2
317460.3
317748.5
320000.0
309704.06
310752.03
312944.5
265780.75
275540.5
264350.44
273522.97
270910.94
279008.7
276285.5
283455.16
289603.25

Viel viel besser. Die alte Methode ließ sehr schnell nach, während die neue einen guten Durchsatz aufrechterhält.

Eine Sache , die ich in Ihrem bemerken hashCode()Methode ist , dass die Reihenfolge der Elemente in der Arrays a[]und b[]keine Rolle. Somit (a[]={1,2,3}, b[]={99,100})wird Hash auf den gleichen Wert wie (a[]={3,1,2}, b[]={100,99}). Eigentlich alle Schlüssel k1und k2wo sum(k1.a)==sum(k2.a)und sum(k1.b)=sum(k2.b)werden zu Kollisionen führen. Ich schlage vor, jeder Position des Arrays ein Gewicht zuzuweisen:

hash = hash * 5381 + (c0*a[0] + c1*a[1]);
hash = hash * 5381 + (c0*b[0] + c1*b[1] + c3*b[2]);

wo c0, c1und c3sind verschiedene Konstanten (Sie können verschiedene Konstanten für verwenden können , bfalls erforderlich). Das sollte die Dinge ein bisschen mehr ausgleichen.

Um Pascal näher zu erläutern: Verstehen Sie, wie eine HashMap funktioniert? Sie haben einige Slots in Ihrer Hash-Tabelle. Der Hashwert für jeden Schlüssel wird gefunden und dann einem Eintrag in der Tabelle zugeordnet. Wenn zwei Hashwerte demselben Eintrag zugeordnet sind - eine "Hash-Kollision" - erstellt HashMap eine verknüpfte Liste.

Hash-Kollisionen können die Leistung einer Hash-Map beeinträchtigen. Im Extremfall wird Ihre Hash-Map zu einer verknüpften Liste, wenn alle Ihre Schlüssel denselben Hash-Code haben oder wenn sie unterschiedliche Hash-Codes haben, aber alle demselben Slot zugeordnet sind.

Wenn also Leistungsprobleme auftreten, überprüfe ich zunächst Folgendes: Erhalte ich eine zufällig aussehende Verteilung von Hash-Codes? Wenn nicht, benötigen Sie eine bessere Hash-Funktion. Nun, "besser" kann in diesem Fall "besser für meinen speziellen Datensatz" bedeuten. Angenommen, Sie haben mit Zeichenfolgen gearbeitet und die Länge der Zeichenfolge für den Hashwert verwendet. (Nicht wie Javas String.hashCode funktioniert, aber ich mache nur ein einfaches Beispiel.) Wenn Ihre Strings sehr unterschiedliche Längen von 1 bis 10.000 haben und über diesen Bereich ziemlich gleichmäßig verteilt sind, könnte dies sehr gut sein Hash-Funktion. Wenn Ihre Zeichenfolgen jedoch nur aus 1 oder 2 Zeichen bestehen, ist dies eine sehr schlechte Hash-Funktion.

Bearbeiten: Ich sollte hinzufügen: Jedes Mal, wenn Sie einen neuen Eintrag hinzufügen, prüft HashMap, ob dies ein Duplikat ist. Bei einer Hash-Kollision muss der eingehende Schlüssel mit jedem Schlüssel verglichen werden, der diesem Steckplatz zugeordnet ist. Im schlimmsten Fall, in dem sich alles auf einen einzelnen Steckplatz bezieht, wird der zweite Schlüssel mit dem ersten Schlüssel verglichen, der dritte Schlüssel mit Nr. 1 und Nr. 2, der vierte Schlüssel mit Nr. 1, Nr. 2 und Nr. 3 usw. Bis Sie den Schlüssel Nr. 1 Million erreicht haben, haben Sie über eine Billion Vergleiche durchgeführt.

@Oscar: Ähm, ich sehe nicht, wie das ein "nicht wirklich" ist. Es ist eher wie ein "lass mich klarstellen". Aber ja, es stimmt, wenn Sie einen neuen Eintrag mit demselben Schlüssel wie einen vorhandenen Eintrag erstellen, wird der erste Eintrag dadurch überschrieben. Das habe ich gemeint, als ich im letzten Absatz über die Suche nach Duplikaten gesprochen habe: Immer wenn ein Schlüssel in denselben Steckplatz gehasht wird, muss HashMap prüfen, ob es sich um ein Duplikat eines vorhandenen Schlüssels handelt oder ob sie sich zufällig im selben Steckplatz befinden Hash-Funktion. Ich weiß nicht, dass das der "ganze Punkt" einer HashMap ist: Ich würde sagen, dass der "ganze Punkt" darin besteht, dass Sie Elemente schnell per Schlüssel abrufen können.

Aber das hat keinen Einfluss auf den "ganzen Punkt", den ich anstrebte: Wenn Sie zwei Schlüssel haben - ja, verschiedene Schlüssel, nicht derselbe Schlüssel, der wieder auftaucht -, wird diese Karte demselben Steckplatz in der Tabelle zugeordnet , HashMap erstellt eine verknüpfte Liste. Da dann jeder neue Schlüssel überprüft werden muss, um festzustellen, ob es sich tatsächlich um ein Duplikat eines vorhandenen Schlüssels handelt, muss bei jedem Versuch, einen neuen Eintrag hinzuzufügen, der demselben Slot zugeordnet ist, die verknüpfte Liste verfolgt werden, um festzustellen, ob dies der Fall ist ist ein Duplikat eines zuvor gesehenen Schlüssels oder wenn es sich um einen neuen Schlüssel handelt.

Update lange nach dem ursprünglichen Beitrag

Ich habe gerade 6 Jahre nach der Veröffentlichung eine Abstimmung über diese Antwort erhalten, was mich dazu veranlasste, die Frage erneut zu lesen.

Die in der Frage angegebene Hash-Funktion ist kein guter Hash für 26 Millionen Einträge.

Es addiert a [0] + a [1] und b [0] + b [1] + b [2]. Er sagt, dass die Werte jedes Bytes von 0 bis 51 reichen, so dass nur (51 * 2 + 1) * (51 * 3 + 1) = 15.862 mögliche Hashwerte vorliegen. Bei 26 Millionen Einträgen bedeutet dies durchschnittlich 1639 Einträge pro Hashwert. Das sind viele, viele Kollisionen, die viele, viele sequentielle Suchen durch verknüpfte Listen erfordern.

Das OP sagt, dass unterschiedliche Ordnungen innerhalb von Array a und Array b als gleich angesehen werden sollten, dh [[1,2], [3,4,5]]. Gleich ([[2,1], [5,3,4]). ]), und um den Vertrag zu erfüllen, müssen sie gleiche Hash-Codes haben. In Ordnung. Dennoch gibt es weit mehr als 15.000 mögliche Werte. Seine zweite vorgeschlagene Hash-Funktion ist viel besser und bietet einen breiteren Bereich.

Obwohl, wie jemand anderes kommentierte, es für eine Hash-Funktion unangemessen erscheint, andere Daten zu ändern. Es wäre sinnvoller, das Objekt beim Erstellen zu "normalisieren" oder die Hash-Funktion anhand von Kopien der Arrays arbeiten zu lassen. Außerdem ist die Verwendung einer Schleife zum Berechnen von Konstanten jedes Mal durch die Funktion ineffizient. Da es hier nur vier Werte gibt, hätte ich beide geschrieben

return a[0]+a[1]*52+b[0]*52*52+b[1]*52*52*52+b[2]*52*52*52*52;

Dies würde den Compiler veranlassen, die Berechnung einmal zur Kompilierungszeit durchzuführen. oder 4 statische Konstanten in der Klasse definiert haben.

Außerdem enthält der erste Entwurf einer Hash-Funktion mehrere Berechnungen, die den Ausgabebereich nicht erweitern. Beachten Sie, dass er zuerst Hash = 503 setzt und dann mit 5381 multipliziert, bevor er überhaupt Werte aus der Klasse berücksichtigt. Also ... tatsächlich addiert er 503 * 5381 zu jedem Wert. Was bringt das? Durch Hinzufügen einer Konstante zu jedem Hashwert werden nur CPU-Zyklen gebrannt, ohne dass etwas Nützliches erreicht wird. Lektion hier: Das Hinzufügen von Komplexität zu einer Hash-Funktion ist nicht das Ziel. Ziel ist es, ein breites Spektrum unterschiedlicher Werte zu erhalten und nicht nur der Komplexität halber Komplexität hinzuzufügen.

Meine erste Idee ist, sicherzustellen, dass Sie Ihre HashMap entsprechend initialisieren. Aus den JavaDocs für HashMap :

Eine Instanz von HashMap verfügt über zwei Parameter, die sich auf die Leistung auswirken: Anfangskapazität und Auslastungsfaktor. Die Kapazität ist die Anzahl der Buckets in der Hash-Tabelle, und die Anfangskapazität ist einfach die Kapazität zum Zeitpunkt der Erstellung der Hash-Tabelle. Der Auslastungsfaktor ist ein Maß dafür, wie voll die Hash-Tabelle werden darf, bevor ihre Kapazität automatisch erhöht wird. Wenn die Anzahl der Einträge in der Hash-Tabelle das Produkt aus dem Auslastungsfaktor und der aktuellen Kapazität überschreitet, wird die Hash-Tabelle erneut aufbereitet (dh interne Datenstrukturen werden neu erstellt), sodass die Hash-Tabelle ungefähr doppelt so viele Buckets enthält.

Wenn Sie also mit einer zu kleinen HashMap beginnen, werden jedes Mal, wenn die Größe geändert werden muss , alle Hashes neu berechnet. Dies könnte das sein, was Sie fühlen, wenn Sie die Einfügemarke von 2-3 Millionen erreichen.

Ich würde einen dreigliedrigen Ansatz vorschlagen:

1. Führen Sie Java mit mehr Speicher aus: java -Xmx256MZum Beispiel mit 256 Megabyte. Verwenden Sie bei Bedarf mehr und Sie haben viel RAM.

2. Zwischenspeichern Sie Ihre berechneten Hash-Werte wie von einem anderen Poster vorgeschlagen, sodass jedes Objekt seinen Hash-Wert nur einmal berechnet.

3. Verwenden Sie einen besseren Hashing-Algorithmus. Der von Ihnen gepostete Hash würde den gleichen Hash mit a = {0, 1} zurückgeben wie mit a = {1, 0}, wobei alle anderen gleich sind.

Nutzen Sie das, was Java Ihnen kostenlos bietet.

public int hashCode() {
    return 31 * Arrays.hashCode(a) + Arrays.hashCode(b);
}

Ich bin mir ziemlich sicher, dass dies viel weniger zu Konflikten führt als Ihre vorhandene hashCode-Methode, obwohl dies von der genauen Art Ihrer Daten abhängt.

Es ist eine gute Sache, in die Grauzone des "Ein / Aus-Themas" zu gelangen, die jedoch notwendig ist, um Verwirrung hinsichtlich des Vorschlags von Oscar Reyes zu vermeiden, dass mehr Hash-Kollisionen auftreten, da dadurch die Anzahl der Elemente in der HashMap verringert wird. Ich mag falsch verstehen, was Oscar sagt, aber ich scheine nicht der einzige zu sein: kdgregory, delfuego, Nash0, und ich scheine alle dasselbe (falsche) Verständnis zu teilen.

Wenn ich verstehe, was Oscar über dieselbe Klasse mit demselben Hashcode sagt, schlägt er vor, dass nur eine Instanz einer Klasse mit einem bestimmten Hashcode in die HashMap eingefügt wird. Wenn ich beispielsweise eine Instanz von SomeClass mit einem Hashcode von 1 und eine zweite Instanz von SomeClass mit einem Hashcode von 1 habe, wird nur eine Instanz von SomeClass eingefügt.

Das Java-Pastebin-Beispiel unter http://pastebin.com/f20af40b9 scheint darauf hinzudeuten, dass das oben Gesagte richtig zusammenfasst, was Oscar vorschlägt.

Unabhängig von Verständnis oder Missverständnissen passieren verschiedene Instanzen derselben Klasse nicht nur einmal in die HashMap eingefügt, wenn sie denselben Hashcode haben - erst, wenn festgestellt wird, ob die Schlüssel gleich sind oder nicht. Der Hashcode-Vertrag erfordert, dass gleiche Objekte denselben Hashcode haben. Es ist jedoch nicht erforderlich, dass ungleiche Objekte unterschiedliche Hashcodes haben (obwohl dies aus anderen Gründen wünschenswert sein kann) [1].

Das Beispiel pastebin.com/f20af40b9 (auf das Oscar mindestens zweimal verweist) folgt, wurde jedoch geringfügig geändert, um JUnit-Zusicherungen anstelle von Druckzeilen zu verwenden. Dieses Beispiel wird verwendet, um den Vorschlag zu unterstützen, dass dieselben Hashcodes Kollisionen verursachen. Wenn die Klassen identisch sind, wird nur ein Eintrag erstellt (z. B. nur ein String in diesem speziellen Fall):

@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
    String s = new String("ese");
    String ese = new String("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // AND equal
    assertTrue(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(2, map.size());

    assertEquals(2, map.get("ese"));
    assertEquals(3, map.get(some));

    assertTrue(s.equals(ese) && s.equals("ese"));
}

class SomeClass {
    public int hashCode() {
        return 100727;
    }
}

Der Hashcode ist jedoch nicht die vollständige Geschichte. Was das Pastebin-Beispiel vernachlässigt, ist die Tatsache, dass beide sund esegleich sind: Sie sind beide die Zeichenfolge "ese". So Einsetzen oder den Inhalt der Karte immer mit soder eseoder "ese"als Schlüssel sind alle gleichwertig , weils.equals(ese) && s.equals("ese") .

Ein zweiter Test zeigt, dass es falsch ist, zu dem Schluss zu kommen, dass identische Hashcodes in derselben Klasse der Grund dafür sind, dass der Schlüssel -> Wert s -> 1überschrieben wird, ese -> 2wenn map.put(ese, 2)er in Test 1 aufgerufen wird. In Test zwei sund haben eseimmer noch den gleichen Hashcode (wie durch verifiziert assertEquals(s.hashCode(), ese.hashCode());) UND sie sind die gleiche Klasse. Jedoch sund esesind MyStringInstanzen in diesem Test nicht Java - StringInstanzen - mit dem einzigen Unterschied relevant für diesen Test der Gleichen zu sein: String s equals String esein Test oben, während MyStrings s does not equal MyString esein Test zwei:

@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
    MyString s = new MyString("ese");
    MyString ese = new MyString("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // BUT not equal
    assertFalse(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(3, map.size());

    assertEquals(1, map.get(s));
    assertEquals(2, map.get(ese));
    assertEquals(3, map.get(some));
}

/**
 * NOTE: equals is not overridden so the default implementation is used
 * which means objects are only equal if they're the same instance, whereas
 * the actual Java String class compares the value of its contents.
 */
class MyString {
    String i;

    MyString(String i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return 100727;
    }
}

Basierend auf einem späteren Kommentar scheint Oscar das, was er zuvor gesagt hat, umzukehren und erkennt die Bedeutung von Gleichberechtigten an. Es scheint jedoch immer noch unklar zu sein, ob Gleichheit wichtig ist, nicht die "gleiche Klasse" (Hervorhebung von mir):

"Nicht wirklich. Die Liste wird nur erstellt, wenn der Hash derselbe ist, der Schlüssel jedoch unterschiedlich. Wenn beispielsweise ein String den Hashcode 2345 und eine Ganzzahl den gleichen Hashcode 2345 angibt, wird die Ganzzahl wegen String in die Liste eingefügt. equals (Integer) ist false. Wenn Sie jedoch dieselbe Klasse haben (oder mindestens .equals true zurückgibt), wird derselbe Eintrag verwendet. Beispielsweise werden new String ("one") und `new String (" one ") als verwendet Schlüssel, wird den gleichen Eintrag verwenden. Eigentlich ist dies der GANZE Punkt von HashMap an erster Stelle! Überzeugen Sie sich selbst: pastebin.com/f20af40b9 - Oscar Reyes "

im Vergleich zu früheren Kommentaren, die sich explizit mit der Bedeutung identischer Klassen und desselben Hashcodes befassen, ohne dass Gleiches erwähnt wird:

"@delfuego: Überzeugen Sie sich selbst: pastebin.com/f20af40b9 In dieser Frage wird also dieselbe Klasse verwendet (Moment mal, dieselbe Klasse wird verwendet, oder?). Dies bedeutet, dass bei gleichem Hash derselbe Eintrag verwendet wird wird verwendet und es gibt keine "Liste" der Einträge. - Oscar Reyes "

oder

"Tatsächlich würde dies die Leistung erhöhen. Je mehr Kollisionen gleich weniger Einträge in der Hashtabelle sind, desto weniger Arbeit ist zu erledigen. Ist weder der Hash (der gut aussieht) noch die Hashtabelle (die gut funktioniert), würde ich wetten, dass er sich auf dem Objekt befindet Schöpfung, bei der die Leistung abnimmt. - Oscar Reyes "

oder

"@kdgregory: Ja, aber nur wenn die Kollision mit verschiedenen Klassen auftritt, wird für dieselbe Klasse (was der Fall ist) derselbe Eintrag verwendet. - Oscar Reyes"

Auch hier kann ich falsch verstehen, was Oscar tatsächlich zu sagen versuchte. Seine ursprünglichen Kommentare haben jedoch genug Verwirrung gestiftet, dass es ratsam erscheint, alles mit einigen expliziten Tests zu klären, damit keine Zweifel bestehen.

[1] - Aus Effective Java, 2. Auflage von Joshua Bloch:

• Immer wenn es während der Ausführung einer Anwendung mehr als einmal für dasselbe Objekt aufgerufen wird, muss die hashCode-Methode konsistent dieselbe Ganzzahl zurückgeben, sofern keine Informationen geändert werden, die in Vergleichen gleicher Objekte für das Objekt verwendet werden. Diese Ganzzahl muss von einer Ausführung einer Anwendung zu einer anderen Ausführung derselben Anwendung nicht konsistent bleiben.

• Wenn zwei Objekte gemäß der Methode same s (Obj ect) gleich sind, muss der Aufruf der hashCode-Methode für jedes der beiden Objekte das gleiche ganzzahlige Ergebnis liefern.

• Es ist nicht erforderlich, dass beim Aufrufen der hashCode-Methode für jedes der beiden Objekte unterschiedliche ganzzahlige Ergebnisse erzielt werden müssen, wenn zwei Objekte gemäß der Methode equals s (Object) ungleich sind. Der Programmierer sollte sich jedoch bewusst sein, dass das Erzeugen unterschiedlicher ganzzahliger Ergebnisse für ungleiche Objekte die Leistung von Hash-Tabellen verbessern kann.

Wenn die Arrays in Ihrem veröffentlichten Hashcode Code Bytes sind, werden Sie wahrscheinlich viele Duplikate haben.

a [0] + a [1] liegt immer zwischen 0 und 512. Das Hinzufügen der b führt immer zu einer Zahl zwischen 0 und 768. Multiplizieren Sie diese und Sie erhalten eine Obergrenze von 400.000 eindeutigen Kombinationen, vorausgesetzt, Ihre Daten sind perfekt verteilt unter jedem möglichen Wert jedes Bytes. Wenn Ihre Daten überhaupt regelmäßig sind, haben Sie wahrscheinlich weit weniger eindeutige Ausgaben dieser Methode.

HashMap hat eine anfängliche Kapazität und die Leistung von HashMap hängt sehr stark von hashCode ab, der zugrunde liegende Objekte erzeugt.

Versuchen Sie, beide zu optimieren.

Wenn die Schlüssel ein Muster haben, können Sie die Karte in kleinere Karten aufteilen und eine Indexkarte haben.

Beispiel: Schlüssel: 1,2,3, .... n 28 Karten zu je 1 Million. Indexkarte: 1-1.000.000 -> Karte1 1.000.000-2.000.000 -> Karte2

Sie werden also zwei Suchvorgänge durchführen, aber der Schlüsselsatz wäre 1.000.000 gegenüber 28.000.000. Sie können dies auch leicht mit Stichmustern tun.

Wenn die Schlüssel völlig zufällig sind, funktioniert dies nicht

Wenn die zwei Byte-Arrays, die Sie erwähnen, Ihr gesamter Schlüssel sind, die Werte im Bereich von 0 bis 51 liegen, eindeutig sind und die Reihenfolge innerhalb der a- und b-Arrays unbedeutend ist, sagt mir meine Mathematik, dass es nur etwa 26 Millionen mögliche Permutationen gibt und dass Sie wahrscheinlich versuchen, die Karte mit Werten für alle möglichen Schlüssel zu füllen.

In diesem Fall wäre das Ausfüllen und Abrufen von Werten aus Ihrem Datenspeicher natürlich viel schneller, wenn Sie ein Array anstelle einer HashMap verwenden und es von 0 auf 25989599 indizieren.

Ich bin spät dran, aber ein paar Kommentare zu großen Karten:

1. Wie in anderen Beiträgen ausführlich besprochen, sind mit einem guten hashCode () 26 Millionen Einträge in einer Map keine große Sache.
2. Ein potenziell verstecktes Problem ist jedoch die GC-Auswirkung von Riesenkarten.

Ich gehe davon aus, dass diese Karten langlebig sind. dh Sie füllen sie und sie bleiben für die Dauer der App. Ich gehe auch davon aus, dass die App selbst langlebig ist - wie ein Server.

Jeder Eintrag in einer Java HashMap erfordert drei Objekte: den Schlüssel, den Wert und den Eintrag, der sie miteinander verbindet. 26 Millionen Einträge in der Karte bedeuten also 26 Millionen * 3 == 78 Millionen Objekte. Dies ist in Ordnung, bis Sie einen vollständigen GC erreicht haben. Dann haben Sie ein Problem mit der Pause der Welt. Der GC untersucht jedes der 78 Millionen Objekte und stellt fest, dass alle am Leben sind. 78M + Objekte sind nur eine Menge Objekte zum Anschauen. Wenn Ihre App gelegentlich lange (möglicherweise viele Sekunden) Pausen toleriert, gibt es kein Problem. Wenn Sie versuchen, Latenzgarantien zu erzielen, kann dies zu einem großen Problem führen (wenn Sie Latenzgarantien wünschen, ist Java natürlich nicht die Plattform :)) Wenn sich die Werte in Ihren Karten schnell ändern, kann dies zu häufigen vollständigen Erfassungen führen was das Problem stark verschärft.

Ich kenne keine großartige Lösung für dieses Problem. Ideen:

• Es ist manchmal möglich, GC- und Heap-Größen so einzustellen, dass "meistens" vollständige GCs verhindert werden.
• Wenn sich Ihr Karteninhalt stark ändert , können Sie FastMap von Javolution ausprobieren - es kann Eintragsobjekte bündeln, wodurch die Häufigkeit vollständiger Sammlungen verringert werden kann
• Sie können Ihr eigenes Map-Impl erstellen und eine explizite Speicherverwaltung für Byte [] durchführen (dh die CPU gegen eine besser vorhersehbare Latenz eintauschen, indem Sie Millionen von Objekten in ein einzelnes Byte serialisieren [] - ugh!)
• Verwenden Sie für diesen Teil kein Java - sprechen Sie über einen Socket mit einer vorhersehbaren In-Memory-Datenbank
• Hoffe, dass der neue G1- Sammler helfen wird (gilt hauptsächlich für den Fall mit hoher Abwanderung)

Nur ein paar Gedanken von jemandem, der viel Zeit mit riesigen Karten in Java verbracht hat.

In meinem Fall möchte ich eine Karte mit 26 Millionen Einträgen erstellen. Mit der Standard-Java-HashMap wird die Put-Rate nach 2-3 Millionen Einfügungen unerträglich langsam.

Aus meinem Experiment (Studentenprojekt 2009):

• Ich habe einen Red Black Tree für 100.000 Knoten von 1 bis 100.000 aufgebaut. Es dauerte 785,68 Sekunden (13 Minuten). Und ich konnte RBTree nicht für 1 Million Knoten aufbauen (wie Ihre Ergebnisse mit HashMap).
• Mit "Prime Tree" meine Algorithmusdatenstruktur. Ich konnte innerhalb von 21,29 Sekunden einen Baum / eine Karte für 10 Millionen Knoten erstellen (RAM: 1,97 GB). Die Kosten für den Suchschlüsselwert betragen O (1).

Hinweis: "Prime Tree" funktioniert am besten mit "fortlaufenden Schlüsseln" von 1 bis 10 Millionen. Um mit Schlüsseln wie HashMap arbeiten zu können, müssen einige Minderjährige angepasst werden.

Was ist #PrimeTree? Kurz gesagt, es handelt sich um eine Baumdatenstruktur wie Binary Tree, bei der Verzweigungsnummern Primzahlen sind (anstelle von "2" -Binär).

Sie können versuchen, eine In-Memory-Datenbank wie HSQLDB zu verwenden .

Mit SQLite können Sie es im Speicher verwenden.

Haben Sie darüber nachgedacht, eine eingebettete Datenbank zu verwenden, um dies zu tun? Schauen Sie sich Berkeley DB an . Es ist Open Source und gehört jetzt Oracle.

Es speichert alles als Schlüssel-> Wertepaar, es ist KEIN RDBMS. und es soll schnell sein.

Zuerst sollten Sie überprüfen, ob Sie Map korrekt verwenden, eine gute hashCode () -Methode für Schlüssel, die anfängliche Kapazität für Map, die richtige Map-Implementierung usw., wie viele andere Antworten beschreiben.

Dann würde ich vorschlagen, einen Profiler zu verwenden, um zu sehen, was tatsächlich passiert und wo die Ausführungszeit verbracht wird. Wird beispielsweise die Methode hashCode () milliardenfach ausgeführt?

Wenn das nicht hilft, wie wäre es dann mit EHCache oder Memcached ? Ja, es handelt sich um Produkte für das Caching, aber Sie können sie so konfigurieren, dass sie über genügend Kapazität verfügen und niemals Werte aus dem Cache-Speicher entfernen.

Eine andere Option wäre ein Datenbankmodul, das leichter ist als vollständiges SQL-RDBMS. Vielleicht so etwas wie Berkeley DB .

Beachten Sie, dass ich persönlich keine Erfahrung mit der Leistung dieser Produkte habe, aber sie könnten den Versuch wert sein.

Sie können versuchen, berechneten Hash-Code im Schlüsselobjekt zwischenzuspeichern.

Etwas wie das:

public int hashCode() {
  if(this.hashCode == null) {
     this.hashCode = computeHashCode();
  }
  return this.hashCode;
}

private int computeHashCode() {
   int hash = 503;
   hash = hash * 5381 + (a[0] + a[1]);
   hash = hash * 5381 + (b[0] + b[1] + b[2]);
   return hash;
}

Natürlich müssen Sie darauf achten, den Inhalt des Schlüssels nicht zu ändern, nachdem der hashCode zum ersten Mal berechnet wurde.

Bearbeiten: Es scheint, dass sich das Caching mit Codewerten nicht lohnt, wenn Sie jeden Schlüssel nur einmal zu einer Karte hinzufügen. In einer anderen Situation könnte dies nützlich sein.

In einem anderen Poster wurde bereits darauf hingewiesen, dass Ihre Hashcode-Implementierung aufgrund der Art und Weise, wie Sie Werte addieren, zu vielen Kollisionen führen wird. Wenn Sie sich das HashMap-Objekt in einem Debugger ansehen, werden Sie feststellen, dass Sie möglicherweise 200 verschiedene Hash-Werte mit extrem langen Bucket-Ketten haben.

Wenn Sie immer Werte im Bereich von 0 bis 51 haben, benötigt jeder dieser Werte 6 Bit zur Darstellung. Wenn Sie immer 5 Werte haben, können Sie einen 30-Bit-Hashcode mit Linksverschiebungen und Ergänzungen erstellen:

    int code = a[0];
    code = (code << 6) + a[1];
    code = (code << 6) + b[0];
    code = (code << 6) + b[1];
    code = (code << 6) + b[2];
    return code;

Die Linksverschiebung ist schnell, führt jedoch zu nicht gleichmäßig verteilten Hashcodes (da 6 Bit einen Bereich von 0 bis 63 implizieren). Eine Alternative besteht darin, den Hash mit 51 zu multiplizieren und jeden Wert zu addieren. Dies ist immer noch nicht perfekt verteilt (z. B. kollidieren {2,0} und {1,52}) und ist langsamer als die Verschiebung.

    int code = a[0];
    code *= 51 + a[1];
    code *= 51 + b[0];
    code *= 51 + b[1];
    code *= 51 + b[2];
    return code;

Wie bereits erwähnt, weist Ihre Hashcode-Implementierung zu viele Kollisionen auf, und das Beheben sollte zu einer anständigen Leistung führen. Darüber hinaus hilft das Zwischenspeichern von Hashcodes und die effiziente Implementierung von Equals.

Wenn Sie noch weiter optimieren müssen:

Nach Ihrer Beschreibung gibt es nur (52 * 51/2) * (52 * 51 * 50/6) = 29304600 verschiedene Schlüssel (von denen 26000000, dh etwa 90%, vorhanden sein werden). Daher können Sie eine Hash-Funktion ohne Kollisionen entwerfen und anstelle einer Hashmap ein einfaches Array anstelle einer Hashmap verwenden, um Ihre Daten zu speichern, den Speicherverbrauch zu reduzieren und die Suchgeschwindigkeit zu erhöhen:

T[] array = new T[Key.maxHashCode];

void put(Key k, T value) {
    array[k.hashCode()] = value;

T get(Key k) {
    return array[k.hashCode()];
}

(Im Allgemeinen ist es unmöglich, eine effiziente, kollisionsfreie Hash-Funktion zu entwerfen, die sich gut gruppiert. Aus diesem Grund toleriert eine HashMap Kollisionen, was zu einem gewissen Overhead führt.)

Angenommen aund bsortiert, könnten Sie die folgende Hash-Funktion verwenden:

public int hashCode() {
    assert a[0] < a[1]; 
    int ahash = a[1] * a[1] / 2 
              + a[0];

    assert b[0] < b[1] && b[1] < b[2];

    int bhash = b[2] * b[2] * b[2] / 6
              + b[1] * b[1] / 2
              + b[0];
    return bhash * 52 * 52 / 2 + ahash;
}

static final int maxHashCode = 52 * 52 / 2 * 52 * 52 * 52 / 6;  

Ich denke, das ist kollisionsfrei. Dies zu beweisen, bleibt dem mathematisch veranlagten Leser als Übung überlassen.

Im Effective Java: Programmiersprachenhandbuch (Java-Serie)

In Kapitel 3 finden Sie gute Regeln für die Berechnung von hashCode ().

Speziell:

Wenn das Feld ein Array ist, behandeln Sie es so, als wäre jedes Element ein separates Feld. Das heißt, berechnen Sie einen Hash-Code für jedes signifikante Element, indem Sie diese Regeln rekursiv anwenden, und kombinieren Sie diese Werte gemäß Schritt 2.b. Wenn jedes Element in einem Array-Feld von Bedeutung ist, können Sie eine der in Release 1.5 hinzugefügten Arrays.hashCode-Methoden verwenden.

Ordnen Sie am Anfang eine große Karte zu. Wenn Sie wissen, dass es 26 Millionen Einträge haben wird und Sie den Speicher dafür haben, machen Sie anew HashMap(30000000) .

Sind Sie sicher, dass Sie genug Speicher für 26 Millionen Einträge mit 26 Millionen Schlüsseln und Werten haben? Das klingt für mich nach viel Erinnerung. Sind Sie sicher, dass die Speicherbereinigung bei Ihrer Marke von 2 bis 3 Millionen noch gut funktioniert? Ich könnte mir das als Engpass vorstellen.

Sie könnten zwei Dinge ausprobieren:

Diese beiden Aktionen reduzieren den Aufwand für das Aufwärmen der Struktur erheblich und sind meiner Meinung nach ziemlich einfach zu testen.

Wenn dies nicht funktioniert, sollten Sie einen anderen Speicher wie ein RDBMS verwenden.

BEARBEITEN

Es ist seltsam, dass das Einstellen der Anfangskapazität die Leistung in Ihrem Fall verringert.

Siehe aus den Javadocs :

Wenn die anfängliche Kapazität größer ist als die maximale Anzahl von Einträgen geteilt durch den Lastfaktor, werden niemals Wiederaufbereitungsvorgänge durchgeführt.

Ich habe eine Mikrobeachmark gemacht (die keineswegs endgültig ist, aber zumindest diesen Punkt beweist).

$cat Huge*java
import java.util.*;
public class Huge {
    public static void main( String [] args ) {
        Map map = new HashMap( 30000000 , 0.95f );
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
import java.util.*;
public class Huge2 {
    public static void main( String [] args ) {
        Map map = new HashMap();
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
$time java -Xms2g -Xmx2g Huge

real    0m16.207s
user    0m14.761s
sys 0m1.377s
$time java -Xms2g -Xmx2g Huge2

real    0m21.781s
user    0m20.045s
sys 0m1.656s
$

Die Verwendung der Anfangskapazität sinkt aufgrund der Neueinstellung von 21 auf 16 Sekunden. Das lässt uns mit Ihrer hashCodeMethode als "Bereich der Gelegenheit";)

BEARBEITEN

Ist nicht die HashMap

Gemäß Ihrer letzten Ausgabe.

Ich denke, Sie sollten Ihre Anwendung wirklich profilieren und sehen, wo der Speicher / die CPU verbraucht wird.

Ich habe eine Klasse erstellt, die dasselbe implementiert hashCode

Dieser Hash-Code führt zu Millionen von Kollisionen, dann werden die Einträge in der HashMap drastisch reduziert.

Ich gehe von 21, 16 in meinem vorherigen Test auf 10 und 8 über. Der Grund dafür ist, dass der hashCode eine hohe Anzahl von Kollisionen hervorruft und Sie nicht die 26 Millionen Objekte speichern, die Sie denken, sondern eine viel signifikant niedrigere Anzahl (ungefähr 20.000 würde ich sagen). Also:

Das Problem ist NICHT DIE HASHMAP ist irgendwo anders in Ihrem Code.

Es ist an der Zeit, einen Profiler zu finden und herauszufinden, wo. Ich würde denken, dass es sich um die Erstellung des Elements handelt oder dass Sie wahrscheinlich auf die Festplatte schreiben oder Daten vom Netzwerk empfangen.

Hier ist meine Implementierung Ihrer Klasse.

Hinweis: Ich habe keinen 0-51-Bereich wie Sie verwendet, sondern -126 bis 127 für meine Werte und Zugaben wiederholt. Dies liegt daran, dass ich diesen Test durchgeführt habe, bevor Sie Ihre Frage aktualisiert haben

Der einzige Unterschied besteht darin, dass Ihre Klasse mehr Kollisionen hat und somit weniger Elemente in der Karte gespeichert sind.

import java.util.*;
public class Item {

    private static byte w = Byte.MIN_VALUE;
    private static byte x = Byte.MIN_VALUE;
    private static byte y = Byte.MIN_VALUE;
    private static byte z = Byte.MIN_VALUE;

    // Just to avoid typing :) 
    private static final byte M = Byte.MAX_VALUE;
    private static final byte m = Byte.MIN_VALUE;


    private byte [] a = new byte[2];
    private byte [] b = new byte[3];

    public Item () {
        // make a different value for the bytes
        increment();
        a[0] = z;        a[1] = y;    
        b[0] = x;        b[1] = w;   b[2] = z;
    }

    private static void increment() {
        z++;
        if( z == M ) {
            z = m;
            y++;
        }
        if( y == M ) {
            y = m;
            x++;
        }
        if( x == M ) {
            x = m;
            w++;
        }
    }
    public String toString() {
        return "" + this.hashCode();
    }



    public int hashCode() {
        int hash = 503;
        hash = hash * 5381 + (a[0] + a[1]);
        hash = hash * 5381 + (b[0] + b[1] + b[2]);
        return hash;
    }
    // I don't realy care about this right now. 
    public boolean equals( Object other ) {
        return this.hashCode() == other.hashCode();
    }

    // print how many collisions do we have in 26M items.
    public static void main( String [] args ) {
        Set set = new HashSet();
        int collisions = 0;
        for ( int i = 0 ; i < 26000000 ; i++ ) {
            if( ! set.add( new Item() ) ) {
                collisions++;
            }
        }
        System.out.println( collisions );
    }
}

Die Verwendung dieser Klasse hat den Schlüssel für das vorherige Programm

 map.put( new Item() , i );

gibt mir:

real     0m11.188s
user     0m10.784s
sys 0m0.261s


real     0m9.348s
user     0m9.071s
sys  0m0.161s

Versuchen Sie es vielleicht, wenn Sie es synchronisieren möchten

http://commons.apache.org/collections/api/org/apache/commons/collections/FastHashMap.html

Ich habe vor einiger Zeit einen kleinen Test mit einer Liste gegen eine Hashmap durchgeführt. Eine lustige Sache war das Durchlaufen der Liste und das Auffinden des Objekts dauerte in Millisekunden genauso lange wie die Verwendung der Hashmaps-Get-Funktion ... nur zu Ihrer Information. Oh ja, Speicher ist ein großes Problem bei der Arbeit mit Hashmaps dieser Größe.

Die gängigen Hash-Methoden sind für große Sets nicht wirklich gut, und wie oben erwähnt, ist der verwendete Hash besonders schlecht. Besser ist es, einen Hash-Algorithmus mit hoher Mischung und Abdeckung wie BuzHash zu verwenden (Beispielimplementierung unter http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm ).