Estoy buscando una estructura de datos que funcione de manera similar a una tabla hash, pero donde la tabla tiene un límite de tamaño. Cuando el número de elementos en el hash alcanza el límite de tamaño, se debe invocar una función de eliminación selectiva para deshacerse de los pares clave/valor menos recuperados en la tabla.¿Qué es una estructura de datos similar a una tabla hash, pero las claves utilizadas con poca frecuencia se eliminan?
aquí hay algo de pseudocódigo de lo que estoy trabajando en:
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;
}
}
Lo que pasa es que hay algunos valores de n para los que myFunc() será llamado un montón de veces, pero muchos otros valores de n que será solo se computa una vez Entonces la memoria caché podría llenarse con millones de valores que nunca más se necesitan. Me gustaría tener una forma para que la memoria caché elimine automáticamente los elementos que no se recuperan con frecuencia.
Esto se siente como un problema que debe resolverse ya, pero no estoy seguro de cuál es la estructura de datos que utilizaría para hacerlo de manera eficiente. ¿Alguien puede señalarme en la dirección correcta?
actualización sabía que esto tenía que ser un problema resuelto ya. Se llama LRU Cache y es fácil de hacer ampliando la clase LinkedHashMap. Aquí está el código que incorpora la solución:
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;
}
}
Véase también http://stackoverflow.com/questions/224868/easy-simple-to-use-lru-cache-in-java. –