Java hashmap vs hashset Leistung

Question

Ich habe eine Datei bestehend aus 7.6M Zeilen. Jede Zeile hat die folgende Form: A, B, C, D, wobei B, C, D Werte sind, die zur Berechnung einer Bedeutungsebene für A verwendet werden, die eine String-Kennung ist, die für jede Zeile eindeutig ist. Mein Ansatz:

private void read(String filename) throws Throwable { 
     BufferedReader br = new BufferedReader(new FileReader(filename)); 

     Map<String, Double> mmap = new HashMap<>(10000000,0.8f); 
     String line; 
     long t0 = System.currentTimeMillis(); 
     while ((line = br.readLine()) != null) { 
      split(line); 
      mmap.put(splitted[0], 0.0); 
     } 
     long t1 = System.currentTimeMillis(); 
     br.close(); 
     System.out.println("Completed in " + (t1 - t0)/1000.0 + " seconds"); 
} 

private void split(String line) { 
    int idxComma, idxToken = 0, fromIndex = 0; 
    while ((idxComma = line.indexOf(delimiter, fromIndex)) != -1) { 
     splitted[idxToken++] = line.substring(fromIndex, idxComma); 
     fromIndex = idxComma + 1; 
    } 
    splitted[idxToken] = line.substring(fromIndex); 
} 

wo der Blindwert 0,0 wird für „Profilieren“ Zwecke eingesetzt und gespaltet ist ein einfaches String-Array für die Klasse definiert ist. Ich habe anfangs mit der split() - Methode von String gearbeitet, fand aber, dass das oben genannte schneller ist.

Wenn ich den obigen Code ausführen, dauert es 12 Sekunden, um die Datei zu analysieren, was waaaay mehr ist, als ich denke, es sollte dauern. Wenn ich z. B. die HashMap durch einen Vektor von Strings ersetze und nur den ersten Eintrag von jeder Zeile nehme (dh ich gebe keinen zugehörigen Wert ein, da dieser konstant amortisiert sein soll), kann die gesamte Datei in weniger als eingelesen werden 3 Sekunden.

Dies deutet darauf hin, dass (i) es gibt viele Kollisionen in der HashMap (Ich habe versucht, die Anzahl der Größen durch Vorabzuweisung der Größe und Einstellung der Auslastung Faktor zu minimieren) oder (ii) der HashCode() Funktion ist irgendwie langsam. Ich bezweifle es (ii), denn wenn ich ein HashSet verwende, können die Dateien in weniger als 4 Sekunden eingelesen werden.

Meine Frage ist: Was könnte der Grund sein, dass die HashMap so langsam funktioniert? Reicht der HashCode() für Karten dieser Größe nicht aus, oder gibt es etwas, was ich übersehen habe?

Answer 1

HashMap vs Vektor: Das Einfügen in HashMap ist viel kostspieliger als das Einfügen in Vector. Obwohl beide konstante Zeitoperationen amortisieren, führt die HashMap intern jedoch eine Reihe anderer Operationen durch (wie das Generieren von hashCode, Überprüfen von Kollisionen, Auflösen von Kollisionen usw.), während der Vektor das Element am Ende einfach einfügt (die Größe der Struktur erhöht sich, Falls erforderlich).

HashMap vs HashSet: HashSet verwendet intern HashMap. Es sollte also keinen Leistungsunterschied geben, wenn Sie sie für den gleichen Zweck verwenden. Im Idealfall haben beide unterschiedliche Zwecke, so dass die Diskussion darüber, was besser ist, nutzlos ist.

Da Sie B, C, D als Wert für A als Schlüssel benötigen, sollten Sie sich unbedingt an HashMap halten. Wenn Sie wirklich nur die Leistung vergleichen möchten, setzen Sie "null" anstelle von 0.0 als Wert für alle Schlüssel (weil HashSet das verwendet, während die Schlüssel in die gesicherte HashMap eingefügt werden).

Update: HashSet verwendet eine Dummy-Konstante (statische final) zum Einfügen in die HashMap, und nicht null. Das tut mir leid. Sie können Ihre 0.0 durch irgendeine Konstante ersetzen und die Leistung sollte HashSet ähnlich sein.

Answer 2

Yep, überprüfte Ihr Beispiel mit 0.0 als Dummy-Wert VS statische Endkonstante als Dummy-Wert VS HashSet. Das ist grober Vergleich, für bessere Präzision würde ich empfehlen, JHM Werkzeug zu verwenden, aber meine HashSet Leistung war ziemlich genau das gleiche wie statische Konstante als Dummy-Leistung.

also höchstwahrscheinlich ist, dass niedrige Leistung, die durch Ihren 0.0 Dummy-Wert für jede Zeile Einwickeln (durch Double.valueOf() während der Kompilierung ersetzt ist, die ausdrücklich ein neues Double Objekt jedes Mal erzeugt).

Das würde die geringe Leistung erklären, da HashSet vordefinierte statische finale Dummy-Objekt (das ist nicht null, BTW) hat.

Answer 3

Sie könnten eine speichereffizientere Bibliothek für Sammlungen verwenden.

Ich schlage vor, die Eclipse-Sammlungen (https://www.eclipse.org/collections/), die eine ObjectDoubleMap (https://www.eclipse.org/collections/javadoc/8.0.0/org/eclipse/collections/api/map/primitive/ObjectDoubleMap.html) hat, die eine Karte von Objekt (String in Ihrem Fall), die eine doppelte (ja, primitive double) als assoziierte Wert hat. Es ist viel besser im Umgang mit Speicher und in der Leistung.

Sie können ein leeres Beispiel dafür erhalten, indem Sie:

ObjectDoubleMaps.mutable.empty();