Ich bin auf der Suche nach einer Datenstruktur, die ähnlich wie eine Hash-Tabelle funktioniert, aber wo die Tabelle eine Größenbeschränkung hat. Wenn die Anzahl der Elemente im Hash die Größenbeschränkung erreicht, sollte eine Culling-Funktion aufgerufen werden, um die am wenigsten abgerufenen Schlüssel/Wert-Paare in der Tabelle zu entfernen.Wie sieht eine Datenstruktur aus wie eine Hash-Tabelle, aber selten verwendete Schlüssel werden gelöscht?
Hier einige Pseudo-Code von dem, was ich arbeite:
class MyClass {
private Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
public int myFunc(int n) {
if(cache.containsKey(n))
return cache.get(n);
int next = . . . ; //some complicated math. guaranteed next != n.
int ret = 1 + myFunc(next);
cache.put(n, ret);
return ret;
}
}
Was passiert, ist, dass es einige Werte von n sind, für die myFunc() viele Male aufgerufen werden, aber viele andere Werte von n denen nur einmal berechnet werden. Der Cache könnte sich also mit Millionen von Werten füllen, die nie wieder benötigt werden. Ich hätte gerne eine Möglichkeit für den Cache, Elemente, die nicht häufig abgerufen werden, automatisch zu entfernen.
Das fühlt sich an wie ein Problem, das bereits gelöst werden muss, aber ich bin nicht sicher, was die Datenstruktur ist, die ich verwenden würde, um es effizient zu machen. Kann mir jemand in die richtige Richtung zeigen?
aktualisieren ich das wusste, dass ein bereits gelöstes Problem sein. Es wird als LRU-Cache bezeichnet und ist einfach zu erweitern, indem die Klasse LinkedHashMap erweitert wird. Hier ist der Code, der die Lösung enthält:
class MyClass {
private final static int SIZE_LIMIT = 1000;
private Map<Integer, Integer> cache =
new LinkedHashMap<Integer, Integer>(16, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest)
{
return size() > SIZE_LIMIT;
}
};
public int myFunc(int n) {
if(cache.containsKey(n))
return cache.get(n);
int next = . . . ; //some complicated math. guaranteed next != n.
int ret = 1 + myFunc(next);
cache.put(n, ret);
return ret;
}
}
Siehe auch http://stackoverflow.com/questions/224868/easy-simple-to-use-lu-cache-in-java. –