Как ограничить максимальный размер Карты, удалив самые старые записи, когда достигнут лимит

Ответ 1

Вы можете использовать LinkedHashMap, как это

Вы можете удалить LRU или FIFO.

public static <K, V> Map<K, V> createLRUMap(final int maxEntries) {
    return new LinkedHashMap<K, V>(maxEntries*10/7, 0.7f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxEntries;
        }
    };
}

Ответ 2

Если это не домашнее задание, я настоятельно рекомендую использовать стороннюю библиотеку, чтобы избежать боли при проектировании, тестировании и поддержании собственного решения.

См., например, механизм Guava MapMaker.

Ответ 3

Вот реализация, которая просто обертывает обычный HashMap и делегирует вызовы метода. Единственное различие заключается в том, что Карта не может превышать максимальную емкость.

import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class CacheMap<K, V> implements Map<K, V> {

    private final Map<K, V> delegate = new HashMap<K, V>();
    private Queue<K> keyInsertionOrder = new LinkedList<K>();
    private final int maxCapacity;

    public CacheMap(int maxCapacity) {
        if (maxCapacity < 1) {
            throw new IllegalArgumentException(
                    "Capacity must be greater than 0");
        }
        this.maxCapacity = maxCapacity;
    }

    @Override
    public void clear() {
        delegate.clear();
    }

    @Override
    public boolean containsKey(Object key) {
        return delegate.containsKey(key);
    }

    @Override
    public boolean containsValue(Object value) {
        return delegate.containsValue(value);
    }

    @Override
    public Set<java.util.Map.Entry<K, V>> entrySet() {
        return delegate.entrySet();
    }

    @Override
    public boolean equals(Object o) {
        return delegate.equals(o);
    }

    @Override
    public V get(Object key) {
        return delegate.get(key);
    }

    @Override
    public int hashCode() {
        return delegate.hashCode();
    }

    @Override
    public boolean isEmpty() {
        return delegate.isEmpty();
    }

    @Override
    public Set<K> keySet() {
        return delegate.keySet();
    }

    @Override
    public V put(K key, V value) {
        V previous = delegate.put(key, value);
        keyInsertionOrder.remove(key);
        keyInsertionOrder.add(key);

        if (delegate.size() > maxCapacity) {
            K oldest = keyInsertionOrder.poll();
            delegate.remove(oldest);
        }
        return previous;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for (K key : m.keySet()) {
            put(key, m.get(key));
        }
    }

    @Override
    public V remove(Object key) {
        keyInsertionOrder.remove(key);
        return delegate.remove(key);
    }

    @Override
    public int size() {
        return delegate.size();
    }

    @Override
    public Collection<V> values() {
        return delegate.values();
    }
}

Ответ 4

Я использую личный класс, который делает то, что вам нужно. После того, как карта заполнена, самые старые доступные объекты удаляются при вставке. Он использует hashmap и связанный список.

У вас есть два способа чтения:

• peek (который не помещает объект как недавно доступный)
• get (который отмечает объект как недавно доступный и, таким образом, предотвращает его удаление на время)

Здесь класс (комментарии удалены, потому что они были на французском языке):

import java.util.HashMap;
import java.util.Map;

public final class HashCache<K, T> {

    public interface Disposer<T> {
        void dispose(T t);
    }

    class Maillon {
        public K cle;

        public Maillon precedent;
        public Maillon suivant;
        public T contenu;
    }

    private Map<K, Maillon> barrette = new HashMap<K, Maillon>();

    private Maillon sommet;
    private Maillon fond;
    private int tailleCache = 100;

    private Disposer<T> disposer;

    @SuppressWarnings("unchecked")
    public HashCache(int tailleCache) {
        if (tailleCache>2) this.tailleCache = tailleCache;
        Maillon[] maillons = new HashCache.Maillon[tailleCache];
        sommet = maillons[0] = new Maillon();
        for (int i=1; i<tailleCache; i++) (maillons[i-1].suivant = maillons[i] = new Maillon()).precedent = maillons[i-1];
        fond = maillons[tailleCache-1];
        //check();
    }

    public Object getLastRead() {
        return sommet.contenu;
    }

    public Object peek(K cle) {
        Object m = barrette.get(cle);
        if (m==null) return null;
        return ((Maillon) m).contenu;
    }

    public synchronized void remove(K cle) {
        Maillon m = (Maillon) barrette.remove(cle);
        if (m!=null) {
            if (disposer!=null) disposer.dispose(m.contenu);
            m.contenu = null;
            m.precedent.suivant = m.suivant;
            m.suivant.precedent = m.precedent;
            fond.suivant = m;
            m.precedent = fond;
            fond = m;
        }
    }


    public synchronized Object put(K cle, T valeur) {
        if (cle==null) return valeur;

        if (fond.cle!=null) {
            barrette.remove(fond.cle);
            if (disposer!=null) disposer.dispose(fond.contenu);
        }
        fond.cle = cle;
        barrette.put(cle, fond);
        fond.contenu = valeur;
        fond.suivant = sommet;
        sommet.precedent = fond;
        sommet = fond;
        fond = fond.precedent;
        fond.suivant = null;

        return valeur;
    }

    public int computeDepth(K cle) {
        Maillon m = sommet;
        for (int i=0; i<tailleCache; i++) {
            if (cle.equals(m.cle)) return i;
            m=m.suivant;
            if (m==null) {
                break;
            }
        }
        return -1;
    }

    @SuppressWarnings("unchecked")
    public synchronized void removeAll() {
        if (disposer!=null) {
            for (Maillon m : barrette.values()) {
                disposer.dispose(m.contenu);
            }
        }
        barrette = new HashMap<K, Maillon>();
        Maillon[] t = new HashCache.Maillon[tailleCache];
        sommet = t[0] = new Maillon();
        for (int i=1; i<tailleCache; i++) (t[i-1].suivant = t[i] = new Maillon()).precedent = t[i-1];
        fond = t[tailleCache-1];
    }


    public synchronized T get(K cle) {
        Maillon m = barrette.get(cle);
        if (m == sommet) return m.contenu;
        if (m == null) return null;
        if (m == fond) {
            m.precedent.suivant = null;
            m.suivant = sommet;
            sommet.precedent = m;
            sommet = m;
            fond = m.precedent;
            m.precedent = null;
        } else {
            m.suivant.precedent = m.precedent;
            m.precedent.suivant = m.suivant;
            m.suivant = sommet;
            sommet.precedent = m;
            sommet = m;
        }
        return m.contenu;
    }

    public Disposer<T> getDisposer() {
        return disposer;
    }

    public void setDisposer(Disposer<T> disposer) {
        this.disposer = disposer;
    }

}