Benötigen Sie eine effiziente Map oder ein Set, das beim Hinzufügen und Entfernen KEINEN Müll produziert?

Question

Da Javolution also nicht funktioniert ( siehe hier ) Ich brauche dringend eine Java Map-Implementierung, die effizient ist und bei einfacher Verwendung keinen Müll produziert. java.util.Map erzeugt Müll, wenn Sie Schlüssel hinzufügen oder entfernen. Ich habe Trove und Guava überprüft, aber es sieht nicht so aus, als hätten sie Set<E>-Implementierungen. Wo kann ich eine einfache und effiziente Alternative finden für java.util.Map ?

Bearbeiten für EJP:

Ein Eintragsobjekt wird zugewiesen, wenn Sie einen Eintrag hinzufügen, und an GC freigegeben, wenn Sie ihn entfernen :(

   void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

Answer 1

Wörtlich genommen, ist mir keine bestehende Implementierung von Map oder Set bekannt, die niemals erzeugt beim Hinzufügen und Entfernen eines Schlüssels beliebigen Müll.

Tatsächlich ist die einzige Möglichkeit, die technisch möglich wäre (in Java, unter Verwendung der Map y Set APIs) ist, wenn Sie eine strenge Obergrenze für die Anzahl der Einträge festlegen würden. Praktische Map- und Set-Implementierungen benötigen einen zusätzlichen Zustand, der proportional zur Anzahl der Elemente ist, die sie enthalten. Dieser Zustand muss irgendwo gespeichert werden, und wenn die aktuelle Zuweisung überschritten wird, muss dieser Speicher erweitert werden. In Java bedeutet dies, dass neue Knoten zugewiesen werden müssen.

(OK, man könnte eine Datenstrukturklasse entwerfen, die alte nutzlose Knoten für immer festhält und daher nie irgendwelche sammelbar Müll ... aber er erzeugt immer noch Müll).

---

Was können Sie also in der Praxis tun, um ... reduzieren. die Menge des erzeugten Mülls. Nehmen wir HashMap als Beispiel:

• Wenn Sie einen Eintrag entfernen, entsteht Müll. Dies ist unvermeidlich, es sei denn, Sie ersetzen die Hash-Ketten durch eine Implementierung, die die Knoten, die die Ketteneinträge darstellen, niemals freigibt. (Und das ist eine schlechte Idee ... es sei denn, Sie können garantieren, dass die Größe des freien Knotenpools immer klein sein wird. Siehe unten für warum Es ist eine schlechte Idee.)

• Wenn die Größe des Haupt-Hash-Arrays geändert wird, entsteht Müll. Dies kann auf mehrere Arten vermieden werden:

  • Sie können ein 'capacity'-Argument im HashMap-Konstruktor angeben, um die Größe des anfänglichen Hash-Arrays so groß zu machen, dass Sie es nie ändern müssen. (Aber das verschwendet potentiell Platz ... besonders wenn Sie nicht genau vorhersagen können, wie groß das HashMap wird wachsen.)

  • Sie können einen lächerlichen Wert für das 'load factor'-Argument angeben, um die HashMap zu veranlassen, ihre Größe nie zu ändern. (Aber das führt zu einer HashMap, deren Hash-Ketten nicht begrenzt sind, und Sie enden mit O(N) Verhalten beim Nachschlagen, Einfügen, Löschen usw.

---

Tatsächlich ist die Erzeugung von Müll nicht zwangsläufig schlecht für Leistung. Das Festhalten an Knoten, damit der Garbage Collector sie nicht einsammelt, ist in der Tat kann sogar noch schlimmer sein für Leistung.

Die Kosten eines GC-Laufs (unter der Annahme eines modernen Kopiersammlers) verteilen sich hauptsächlich auf drei Bereiche:

• Auffinden von Knoten, die kein Müll sind.
• Kopieren dieser Nicht-Müll-Knoten in den "Nach-Raum".
• Aktualisierung von Verweisen in anderen Nicht-Müll-Knoten, um auf Objekte im "Zu-Raum" zu zeigen.

(Wenn Sie einen Kollektor mit geringem Pausenanteil verwenden, fallen auch andere Kosten an ... im Allgemeinen proportional zur Menge des Nicht-Mülls).

Der einzige Teil der Arbeit des GC, der tatsächlich von der Menge an Garbage abhängt, ist das Löschen des Speichers, den die Garbage-Objekte einst belegten, um ihn für die Wiederverwendung bereit zu machen. Und das kann mit einem einzigen bzero Aufruf des gesamten "Von-Raums" ... oder Verwendung von Tricks des virtuellen Speichers.

Angenommen, Ihre Anwendung/Datenstruktur bleibt an Knoten hängen, um die Erzeugung von Müll zu vermeiden. Wenn nun die GC läuft, muss sie zusätzliche Arbeit leisten, um all diese zusätzlichen Knoten zu durchlaufen und sie in den "to-space" zu kopieren, obwohl sie keine nützlichen Informationen enthalten. Außerdem verbrauchen diese Knoten Speicher, was bedeutet, dass weniger Platz zur Verfügung steht, wenn der Rest der Anwendung Garbage erzeugt, und die GC häufiger ausgeführt werden muss.

Und wenn Sie schwache/weiche Referenzen verwendet haben, damit die GC Knoten aus Ihrer Datenstruktur zurückholen kann, dann bedeutet das noch mehr Arbeit für die GC ... und Platz, um diese Referenzen darzustellen.

Hinweis: Ich behaupte nicht, dass das Pooling von Objekten die Leistung immer verschlechtert, sondern nur, dass dies häufig der Fall ist, insbesondere wenn der Pool unerwartet groß wird.

Und natürlich ist das der Grund, warum HashMap und ähnliche allgemeine Datenstrukturklassen kein Objekt-Pooling betreiben. Wenn sie es täten, würden sie in Situationen, in denen der Programmierer es nicht erwartet, deutlich schlechter abschneiden ... und sie wirklich gebrochen werden würde , IMO.

---

Schließlich gibt es eine einfache Möglichkeit, eine HashMap so abzustimmen, dass ein Hinzufügen unmittelbar gefolgt von einem Entfernen desselben Schlüssels (garantiert) keinen Müll erzeugt. Verpacken Sie sie in eine Map-Klasse, die den letzten "hinzugefügten" Eintrag zwischenspeichert und nur die put in der Realität HashMap wenn der nächste Eintrag hinzugefügt wird. Natürlich ist dies KEINE Allzwecklösung, aber es entspricht dem Anwendungsfall Ihrer früheren Frage.

Answer 2

Ich schätze, Sie brauchen eine Version von HashMap, die offene Adressierung verwendet, und Sie werden etwas Besseres als lineares Sondieren wollen. Ich weiß nicht von einer spezifischen Empfehlung aber.

Answer 3

http://sourceforge.net/projects/high-scale-lib/ hat Implementierungen von Set und Map, die beim Hinzufügen oder Entfernen von Schlüsseln keinen Müll erzeugen. Die Implementierung verwendet ein einzelnes Array mit abwechselnden Schlüsseln und Werten, so dass put(k,v) kein Entry-Objekt erzeugt.

Es gibt jedoch einige Vorbehalte:

• Rehash erzeugt Müll, weil es das zugrunde liegende Array ersetzt
• Ich denke, dass diese Karte bei genügend verschachtelten Einfüge- und Löschvorgängen wieder zerfallen wird, selbst wenn die Gesamtgröße stabil ist. (Um Tombstone-Werte zu sammeln)
• Diese Karte erstellt ein Eintragsobjekt, wenn Sie nach dem Eintragssatz fragen (einen nach dem anderen, während Sie iterieren)

Die Klasse heißt NonBlockingHashMap.

Answer 4

Eine Möglichkeit besteht darin, die HashMap-Implementierung so zu ändern, dass ein Pool von Einträgen verwendet wird. Das habe ich getan. :) Es gibt auch andere Optimierungen für die Geschwindigkeit, die man dort machen kann. Ich stimme mit Ihnen überein: das Problem mit Javolution FastMap ist unfassbar :(