tablas - ¿Cómo limito el número de entradas en una tabla hash de Java?

tablas hash en java

Question

¿Existe una técnica tal que pueda especificar un número n tal que cuando se inserta la entrada (n + 1) th, la entrada más antigua se elimine primero asegurándose de que el tamaño de la tabla hash siempre se limite a n?

Answer 1

¿Está buscando un LRU caché quizás? Aquí hay una publicación de blog en una basada en LinkedHashMap .

Answer 2

Es posible que desee considerar el uso de Colecciones Apache. Tienen un montón de implementaciones de LRU. De lo contrario, puede escribir fácilmente un contenedor similar para las colecciones de biblioteca estándar; No creo que haya uno que pueda usar directamente.

Answer 3

Podría usar una cola de dos extremos, o Deque , y simplemente eliminar el primer elemento cuando esté en el conteo máximo.

Answer 4

Si está almacenando en caché, podría usar WeakHashMap o WeakReference y no tener que preocuparse por el tamaño de la caché.

Answer 5

LinkedHashMap hace exactamente eso, vea javadoc para el método removeEldestEntry .

Algo así debería funcionar, esto eliminará la entrada insertada más antigua:

Map map = new LinkedHashMap() {
    @Override
    protected boolean removeEldestEntry(Entry eldest) {
        return size() > N;
    }
};

También puede eliminar la entrada más antigua a la que se accede al especificarla en el constructor:

    Map map = new LinkedHashMap(16, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Entry eldest) {
            return size() > N;
        }
    };

Answer 6

Si tiene necesidades de concurrencia, no trate de resolver este problema usted mismo. Guava''s CacheBuilder tiene un método .maximumSize () que te permite limitar el tamaño de un mapa, aunque entiendo que es posible que las entradas antiguas se eliminen antes de que llegues al límite.

Hay una página interesante sobre el diseño de la estructura de datos, que debería impresionar al lector sobre lo difícil que sería hacer algo mejor que la implementación de Google. :)