java - 如何在达到限制时通过删除最旧的条目来限制地图的最大大小

Question

我想要一个具有最大尺寸的 Map 实现。我想将其用作缓存，因此一旦达到限制，就会删除最旧的条目。

我也不想引入对任何 3rd 方库的依赖。

Answer 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;
        }
    };
}

Answer 2

这是一个仅包装普通 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();
    }
}

Answer 3

我使用个人课程来满足您的需求。一旦地图已满，插入时最旧的访问对象将被删除。它使用哈希图和链表。

您有两种阅读方法：

• 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;
    }

}

Answer 4

如果这不是功课，我强烈建议使用第三方库来避免设计、测试和维护自己的解决方案的痛苦。

例如，参见Guava MapMaker机制。