Gibt es eine Technik, so dass ich eine Zahl n so angeben kann, dass wenn der Eintrag (n + 1) eingefügt wird, zuerst der älteste Eintrag entfernt wird und sichergestellt wird, dass die Größe der Hashtabelle immer auf n beschränkt ist?Wie beschränke ich die Anzahl der Einträge in einer Java-Hashtabelle?
Sie suchen nach einem LRU cache vielleicht? Hier ist ein Blog-Post auf einem basierend auf LinkedHashMap.
Ich kam hierher, um LinkedHashMap zu erwähnen, das ich kürzlich für einen LRU-Cache verwendet habe. –
Sie können Apache Collections verwenden. Sie haben eine Reihe von LRU-Implementierungen. Andernfalls können Sie problemlos einen ähnlichen Wrapper für die Standardbibliothekssammlungen schreiben. Ich glaube nicht, dass es einen gibt, den man direkt benutzen kann.
Sie könnten eine doppelendige Warteschlange oder Deque verwenden, und entfernen Sie einfach das erste Element, wenn Sie bei der maximalen Anzahl sind.
Wenn Sie zwischenspeichern, können Sie eine WeakHashMap oder WeakReference verwenden und müssen sich dann keine Gedanken über die Größe des Caches machen.
Nur um zu verdeutlichen, wie man ein verbreitetes Missverständnis vermeidet: WeakHashMap eignet sich NICHT für das LRU-Caching allein; Es verwendet WeakReferences für KEYS, nicht VALUES. Es ist ideal zum Speichern von Metadaten über Objekte, die nicht zu Ihnen gehören. nicht für die Annahme von Einträgen werden bei Speichermangel rausgeworfen – Cowan
LinkedHashMap macht genau das, siehe Javadoc für die removeEldestEntry Methode.
So etwas sollte es tun, wird dies den ältesten eingefügten Eintrag entfernen:
Map map = new LinkedHashMap() {
@Override
protected boolean removeEldestEntry(Entry eldest) {
return size() > N;
}
};
Sie können auch ältesten zugegriffen Eintrag entfernen, indem es im Konstruktor festgelegt wird:
Map map = new LinkedHashMap(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Entry eldest) {
return size() > N;
}
};
Wenn Sie Parallelität braucht, versuchen Sie nicht, dieses Problem selbst zu lösen. Guava CacheBuilder hat eine .maximumSize() -Methode, mit der Sie die Größe einer Karte begrenzen können, obwohl ich weiß, dass alte Einträge möglicherweise bereinigt werden, bevor Sie tatsächlich das Limit erreichen.
Es gibt an interesting page zum Design der Datenstruktur, was den Leser beeindrucken sollte, wie schwierig es wäre, etwas besser zu machen als die Implementierung von Google. :)
Dies ist vergleichbar mit http://stackoverflow.com/questions/272674/what-is-a-data-structure-kind-of-like-a-hash-table-but-infrequently-used-keys -ar. Die Frage bietet eine Lösung. –
@robhruska - denkst du, das zählt als ein Duplikat? Ich bin am Zaun. –
Ich bin mir nicht sicher. Die Perspektiven sind ein wenig anders, da diese Frage nach einer "Größenbeschränkung" fragt, während die andere Frage auf "selten verwendete" Einträge abzielt. Ich bin nicht dagegen, es offen zu lassen, wenn es nur für diejenigen, die es aus dem Blickwinkel dieser Frage betrachten, besser ist. –