java - resolucion - tablas hash estructura de datos
¿Qué es una estructura de datos similar a una tabla hash, pero las claves utilizadas con poca frecuencia se eliminan? (6)
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.
Aquí hay un pseudocódigo de lo que estoy trabajando:
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 sucede es que hay algunos valores de n para los cuales myFunc() se llamará muchas veces, pero muchos otros valores de n que solo se computarán 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 parece un problema que ya debe resolverse, pero no estoy seguro de cuál es la estructura de datos que usarí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 ya resuelto. 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;
}
}
Eche un vistazo a WeakHashMap
Es probable que WeakHashMap no haga lo que usted espera ... lea detenidamente la documentación y asegúrese de saber exactamente de las referencias fuertes y débiles.
Yo recomendaría que eche un vistazo a java.util.LinkedHashMap y use su método removeEldestEntry para mantener su caché. Si su matemática consume muchos recursos, es posible que desee mover las entradas al frente siempre que se utilicen para garantizar que solo las entradas no utilizadas caigan al final del conjunto.
La política de caché de reemplazo adaptable está diseñada para evitar que las solicitudes únicas contaminen su caché. Esto puede ser más elegante de lo que está buscando, pero aborda directamente su "llenado de valores que nunca se necesitan de nuevo".
Probablemente desee implementar una política de uso menos reciente para su mapa. Hay una manera simple de hacerlo en la parte superior de un LinkedHashMap:
http://www.roseindia.net/java/example/java/util/LRUCacheExample.shtml
Buscar en Google "LRU map" y "Me siento afortunado" te da esto:
Una implementación de Mapa con un tamaño máximo fijo que elimina la entrada usada menos recientemente si se agrega una entrada cuando está llena.
Suena bastante perfecto en :)
Está buscando un LRUList / Map . Echa un vistazo a LinkedHashMap :
El removeEldestEntry(Map.Entry) puede removeEldestEntry(Map.Entry) para imponer una política para eliminar mapeos obsoletos automáticamente cuando se agregan nuevas asignaciones al mapa.