Kennt jemand eine java.util.Map-Implementierung, die für wenig Arbeitsspeicher optimiert ist?

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

Könnten Sie sich commons-collections ansehen Flat3Map , es ist optimiert, um 3 Werte in 3 Feldern zu speichern und überläuft bei 4 eine andere Karte.

Ich habe die Implementierung nicht betrachtet, aber es lohnt sich, darüber nachzudenken. Das einzige Problem ist, dass seit commons-collections 1.3-kompatibel sind, gibt es keine generischen.

Wickeln Sie eine ArrayList mit der Map-Schnittstelle. Die 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 die sequenzielle Suche, um nach Werten zu suchen. Solange nur wenige Einträge vorhanden sind, ist die Leistung in Ordnung [*]. Dies wird Ihnen den Spielraum geben, echte Karten für die wenigen Vasen zu verwenden, in denen Sie eine große Anzahl von Werten haben.

*: Nehmen wir an, Ihre durchschnittliche Kartengröße beträgt 10. Heutige Computer können ungefähr 100 Millionen Schlüssel pro Sekunde vergleichen, so dass jede Suche durchschnittlich weniger als fünf Mikrosekunden dauert.

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

Ich empfehle Ihnen, entweder HashMap, Hashtable oder ConcurrentHashMap von JDK zu verwenden, abhängig von Synchronisations- oder Parallelitätsanforderungen. Wenn Sie sich dafür entscheiden, sie zu verwenden, können Sie initialCapacity und loadFactor im Konstruktor entsprechend anpassen.

Google Sammlungen und Apache Commons Sammlungen bieten mehr Funktionen: LRUMap, ReferenceMap, MultikeyMap und so weiter. Aber ich glaube nicht, dass es nicht nur eine kleine Größe gibt.

LinkedHashMap verwendet eine verkettete Liste, denke ich, aber ich bezweifle, dass es für wenig Speicher optimiert ist. In der Regel besteht der ganze Sinn einer Karte darin, Suchvorgänge von Schlüssel zu Wert zu beschleunigen, was erklärt, warum Sie nicht das finden, was Sie in den üblichen Bereichen benötigen. Es könnte einfach am einfachsten sein, eine eigene Implementierung von Map zu schreiben, und vielleicht könntest du sogar den Code freigeben, falls jemand das gleiche braucht.

Schreiben Sie den Code in einer Weise, die die Verwendung von Karten verbirgt (Sie sollten das sowieso tun, und es klingt wie Sie auch sind). An dem Punkt, an dem es darauf ankommt, weil Sie den Code profiliert haben und sehen können, dass der Speicher wirklich ein Problem ist, finden Sie einen: -)

Wenn Sie zu diesem Zeitpunkt wissen, dass es ein Problem gibt, dann entschuldige ich mich nicht. Aber zu oft beschäftigen sich die Leute mit der "Idee", dass der Code langsam sein wird / viel Speicher / etc ... und beginnen, ihn zu optimieren, anstatt den Code richtig zu machen.

Wenn Sie also etwas schreiben, von dem Sie wissen, dass es wichtig ist, sollten Sie messen, wie Sie gehen. Zum Beispiel arbeite ich an Code, um Klassendateien zu analysieren, ich mache eine kleine Änderung und sehe dann, wie es die Leistung beeinflusst. Zum Beispiel wusste ich für eine Tatsache, dass eine Änderung, die ich machte (3 Zeilen), mein Programm 4 mal langsamer machte ... Ich verbrachte die Zeit an diesem Punkt, um den schnelleren Weg herauszufinden, es zu tun.

Sind Sie auch sicher, dass Karten benötigt werden, wenn der Wert von "n" klein ist? Vielleicht ist eine Liste schnell genug? Haben Sie auch versucht, die vorhandene Map so zu optimieren, dass sie weniger Speicher benötigt?

Vielleicht ist diese Antwort ein bisschen spät, aber werfen Sie einen Blick auf Javolution Projekt. Es enthält Implementierungen vieler Datenstrukturen, die für eingebettete und Echtzeitumgebungen gedacht sind. Konkret gibt es eine FastMap Klasse, die vielleicht genau das macht, was Sie wollen.

Wenn Sie nur String s speichern, sehen Sie sich Ссылка

Bearbeiten Oh, Entschuldigung, ich sehe, du suchst nach kleinen, nicht großen Karten, vergiss meinen Rat dann.

Es hängt viel davon ab, wie Sie diese Karten verwenden werden, können Sie sie in einer Aufnahme auffüllen und dann nur nachschauen (brauchen Sie diese Suchfunktionen, um schnell zu sein)?

Eine Implementierung mit einer minimalen Menge an Speicher wäre, alle Elemente in ein Array zu setzen und einen Scan durchzuführen, um Elemente zu finden (aber ich denke, das ist nicht schnell genug für Ihre Bedürfnisse). .

Wenn Sie alle Elemente am Anfang kennen, können Sie versuchen, eine gute Hash-Methode ohne zu viele Kollisionen auszuwählen.

Oder vielleicht könnten Sie TreeMap verwenden, wenn Sie eine langsame Einfügezeit zulassen ...