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

Einfach gesagt, empfehle ich die Verwendung von HashMap, Hashtable und ConcurrentHashMap aus dem JDK je nach Synchronisierungs- oder Nebenläufigkeitsanforderungen. Wenn Sie sich für deren Verwendung entscheiden, kann das Festlegen von initialCapacity und loadFactor beim Instanziieren helfen.

Google Collections und Apache Commons Collections bieten weitere Funktionen wie LRUMap, ReferenceMap, MultikeyMap und so weiter. Aber ich denke, dass sie nicht nur für kleine Größen gedacht sind.

Answer 2

Es hängt stark davon ab, wie du diese Karten verwenden wirst. Kannst du sie auf einmal bevölkern und dann nur noch Abfragen machen (müssen diese Abfragen schnell sein)?

Eine Implementierung, die eine minimale Menge an Speicher verwendet, wäre, alle Elemente in einem Array zu platzieren und einen Scan durchzuführen, um Elemente zu finden (aber ich vermute, das ist nicht schnell genug für deine Bedürfnisse)...

Wenn du alle Elemente von Anfang an kennst, kannst du versuchen, eine gute Hash-Methode ohne zu viele Kollisionen auszuwählen.

Oder vielleicht könntest du TreeMap verwenden, wenn du eine langsame Einfügezeit erlaubst...

Answer 3

Vielleicht ist diese Antwort etwas spät, aber schauen Sie sich das Javolution Projekt an. Es enthält Implementierungen vieler Datenstrukturen, die für eingebettete und Echtzeitumgebungen gedacht sind. Konkret gibt es eine FastMap Klasse, die genau das tun könnte, was Sie möchten.

Answer 4

Wenn Sie nur Strings speichern, werfen Sie einen Blick auf http://code.google.com/p/flatmap

bearbeiten Oh, entschuldigung, ich sehe, dass Sie nach kleinen und nicht riesigen Karten suchen, vergessen Sie dann meinen Rat.

Answer 5

Ich weiß, es ist eine alte Frage, aber vielleicht könnte jemand weitere Ideen hinzufügen.

NB: Die folgenden würde wirklich nur für eine spezifische Untermenge von Anwendungsfällen Sinn ergeben:

Wenn die Anforderung sich auf stark überlappende Schlüsselsätze bezieht (im Extremfall der gleiche Schlüsselsatz für alle Maps), dann könnte eine sehr effektive Lösung darin bestehen, die Schlüssel im Hinblick auf Maps "extern" zu machen und die Maps nur Werte, in einem Array, zu enthalten.

Die Implementierung sollte nicht "strukturell" vom Überlappungsfaktor abhängig sein, aber meine funktioniert besser, je mehr die Schlüssel sich überlappen. Wie du erwarten würdest.

Ich kann keine genauen Details meiner Implementierung geben, aber es ist wichtig, einen geeigneten Mechanismus zu haben, um Schlüssel (außerhalb Ihres Map-Objekts gespeichert) in Indizes des Wertearrays umzuwandeln, während es dem Wertearray ermöglicht wird, kompakt zu bleiben, also eine Länge von fünf zu haben, wenn Ihre Map fünf Zuordnungen enthält.

Angenommen, die Schlüssel für all diese Maps sitzen in einer separaten Map, zugeordnet zu Zahlen. Dann geht es darum, eine Möglichkeit zu haben, die Zahlen und Array-Indizes in Beziehung zu setzen.

Entschuldigung, wenn das nicht spezifisch genug ist, aber ich fand die Idee interessant und gleichzeitig einfach und könnte als alternative Richtung bei der Entwicklung einer speichereffizienten Map verwendet werden.

Es ist von Natur aus für Anwendungsfälle mit hoher "Schlüsselüberlappung" geeignet, aber an sich ist es allgemein gültig. Es kann durchaus Leistungsprobleme haben, wenn die Überlappung zu gering ist, abhängig von den Implementierungsdetails.