Kennt jemand eine java.util.Map-Implementierung, die für einen geringen Speicherverbrauch optimiert ist?

Question

Ich habe an den üblichen Stellen gesucht (apache commons, google) und keinen gefunden ...

Es sollte Open Source sein.

Ich suche im Grunde nach einer, die auf einer verketteten Liste basiert. Der Anwendungsfall sind 10.000 Karten, mit möglicherweise nicht vielen Werten. Es muss nicht skalierbar sein, da ich es konvertieren kann, wenn es zu groß wird.

Einige Zahlen, Größen unter Verwendung einiger berechneter JVM-Werte (8 Bytes/java.lang.Object, 4 Bytes/Ref) der HashMap beträgt ca. 100+32n Bytes, das theoretisch beste ist 12+20*n. <-- Das will ich, für kleine n.

Answer 1

Könnte einen Blick auf commons-collections Flat3Map werfen, es ist optimiert, um 3 Werte in 3 Feldern zu speichern und überläuft zu einer anderen Map bei 4.

Ich habe mir die Implementierung nicht angesehen, aber es könnte sich lohnen, darüber nachzudenken. Das einzige Problem ist, dass es keine Generics gibt, da commons-collections mit 1.3 kompatibel ist.

Answer 2

Umschließen Sie ein ArrayList mit dem Map-Interface. Der ArrayList verwendet selbst nur wenige Bytes. Jeder Knoten benötigt zwei Zeiger, einen für den Schlüssel und einen für den Wert. Verwenden Sie eine sequenzielle Suche, um Werte nachzuschlagen. Solange es nur wenige Einträge gibt, wird die Leistung in Ordnung sein[*]. Dies gibt Ihnen den Spielraum, echte Maps für die wenigen Fälle zu verwenden, in denen Sie eine große Anzahl von Werten haben.

*: Angenommen die durchschnittliche Kartengröße beträgt 10. Moderne Computer können grob geschätzt etwa 100 Millionen Schlüssel pro Sekunde vergleichen, daher wird jeder Suchvorgang im Durchschnitt weniger als fünf Mikrosekunden dauern.

Wenn die Leistung immer noch zu schlecht ist für Ihren Anwendungsfall, können Sie versuchen, das Array nach Schlüssel zu sortieren und die binäre Suche zu verwenden.

Answer 3

Ok, ich habe es am Ende selbst implementiert. Ich habe einen Geschwindigkeitsvergleich durchgeführt und festgestellt, dass es im Vergleich zu einem HashMap immer noch etwas schneller ist mit 4 Einträgen, aber langsamer mit 5 oder mehr. Ich habe die Tests mit einer langen Liste von Schlüsseln durchgeführt, die ich ähnlich wie eine Liste zufälliger englischer Wörter gestaltet habe.

import java.util.*;

// ÖFFENTLICHER BEREICH
public class SmallMap extends AbstractMap {

    private Entry entry = null;

    public void clear() { entry = null; }
    public boolean isEmpty() { return entry==null; }    
    public int size() {
        int r = 0;
        for(Entry e = entry; e!=null; e = e.next) r++;
        return r;
    }

    public boolean containsKey(Object key) {
        for(Entry e = entry; e!=null; e = e.next){
            if(e.key.equals(key)){
                return true;
            }
        }
        return false;
    }

    public boolean containsValue(Object value) {
        for(Entry e = entry; e!=null; e = e.next){
            if(e.value==null){
                if(value==null) return true;
            }else if(e.value.equals(value)){
                return true;
            }
        }
        return false;
    }

    public Object get(Object key) {
        for(Entry e = entry; e!=null; e = e.next){
            if(e.key.equals(key)){
                return e.value;
            }
        }
        return null;
    }

    public Object put(Object key, Object value) {
        for(Entry e = entry; e!=null; e = e.next){
            if(e.key.equals(key)){
                Object r = e.value;
                e.value = value;
                return r;
            }
        }
        entry = new Entry(key, value, entry);
        return null;
    }

    public Object remove(Object key) {
        if(entry!=null){
            if(entry.key.equals(key)){
                Object r = entry.value;
                entry = entry.next;
                return r;
            }
            for(Entry e = entry; e.next!=null; e = e.next){
                if(key.equals(e.next.key)){
                    Object r = e.next.value;
                    e.next = e.next.next;
                    return r;
                }
            }
        }
        return null;
    }

    public Set entrySet() { return new EntrySet(); }

    class EntrySet extends AbstractSet{
        public Iterator iterator() {
            return new Iterator(){

                Entry last = null;
                Entry e = entry;
                public boolean hasNext() { return e!=null; }

                public Object next() { 
                    last = e;
                    e = e.next;
                    return last;
                }

                public void remove() { 
                    if(last == null) throw new IllegalStateException();
                    SmallMap.this.remove(last.key);
                }
            };
        }

        public int size() { return SmallMap.this.size();}
    }

    static private class Entry implements java.util.Map.Entry {
        final Object key;
        Object value;
        Entry next; 
        Entry(Object key, Object value, Entry next){
            if(key==null) throw new NullPointerException();
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public Object getKey() { return key; }
        public Object getValue() { return value; }
        public Object setValue(Object value) { 
            Object r = this.value;
            this.value = value;
            return r;
        }
        public int hashCode() {
            return (key   == null ? 0 :   key.hashCode()) ^
               (value == null ? 0 : value.hashCode());
        }
    }
}

Answer 4

LinkedHashMap verwendet eine verkettete Liste, denke ich, aber ich bezweifle, dass es für eine geringe Speicherbelegung optimiert ist. Normalerweise geht es bei einer Map darum, Suchvorgänge von Schlüssel zu Wert zu beschleunigen, was erklärt, warum du nicht das findest, was du in gängigen Orten benötigst. Es könnte am einfachsten sein, deine eigene Implementierung von Map zu schreiben, und vielleicht könntest du den Code sogar veröffentlichen, falls jemand anderes dasselbe benötigt.

Answer 5

Schreiben Sie den Code so, dass die Verwendung von Maps verborgen wird (das sollten Sie so oder so tun, und es hört sich so an, als würden Sie das auch machen). Wenn es darauf ankommt, weil Sie den Code profiliert haben und sehen, dass der Speicher wirklich ein Problem darstellt, finden Sie einen :-)

Wenn Sie zu diesem Zeitpunkt wissen, dass es ein Problem gibt, tut mir leid, ich kenne keins. Allerdings gehen Menschen allzu oft mit der "Idee" um, dass der Code langsam/zu viel Speicher usw. verbraucht und versuchen, ihn von Anfang an zu optimieren, anstatt ihn korrekt zu machen.

Das gesagt, wenn Sie etwas schreiben, von dem Sie wissen, dass es wichtig ist, sollten Sie während des Schreibens messen. Ich arbeite beispielsweise an Code zum Parsen von Klassendateien, ich mache eine kleine Änderung und sehe dann, wie sich die Leistung ändert. Zum Beispiel wusste ich genau, dass eine Änderung, die ich vorgenommen habe (3 Zeilen), mein Programm 4-mal langsamer gemacht hat... Ich habe dann die Zeit investiert, um herauszufinden, wie man es schneller machen kann.

Sind Sie sich außerdem sicher, dass Karten benötigt werden, wenn der Wert von "n" klein ist? Vielleicht reicht auch eine Liste? Haben Sie auch versucht, die bestehende Map so zu optimieren, dass sie weniger Speicher verbraucht?