java - 使用 ArrayDeque 实现缓存

Question

简介

我使用 ArrayDeque 并遵循 Generics 解决方案实现了一个具有 LRU 策略的简单缓存:

public class Cache<T> extends ArrayDeque<T> implements Serializable {
    private static final long serialVersionUID = 1L;
    private int MAX_SIZE;

    public Cache(int maxSize) {
        MAX_SIZE = maxSize;
    }

    public void store(T e) {
        if (super.size() >= MAX_SIZE) {                 
            this.pollLast();
        }
        this.addFirst(e);       
    }

    public T fetch(T e) {
        Iterator<T> it = this.iterator();
        while (it.hasNext()) {
            T current = it.next();
            if (current.equals(e)) {
                this.remove(current);
                this.addFirst(current);
                return current;
            }
        }
        return null;
    }

}

<小时/>

问题

当我实例化该类并推送一个元素时，

Cache<CachedClass> cache = new Cache<CachedClass>(10);
cache.store(new CachedClass());

此时队列不包含任何内容。

为什么会发生这种情况？

<小时/>

观察

顺便说一下，CachedClass 重写了 .equals() 方法。

<小时/>

测试

 public class CacheTest {

    @Test
    public void testStore() {
        Cache<Integer> cache = new Cache<Integer>(3);

        cache.store(1);
        assertTrue(cache.contains(1));

        cache.store(2);
        cache.store(3);
        cache.store(4);

        assertEquals(cache.size(), 3);      
    }

    @Test
    public void testFetch() {
        Cache<Context> cache = new Cache<Context>(2);

        Context c1 = new Context(1);
        Context c2 = new Context(2);

        cache.store(c1);
        cache.store(c2);                

        assertEquals((Context) cache.peekFirst(), (new Context(2)));

        Context c = cache.fetch(c1);

        assertTrue(c == c1);        
        assertEquals(cache.size(), 2);
        assertEquals((Context) cache.peekFirst(), (new Context(1)));

    }

 }

编辑它成功通过了两项测试。

It passes the first test. It fails throwing an AssertException on

assertTrue(cache.peekFirst() == 1);

of the second test,

Answer 1

LinkedHashMap 的 Javadoc 说

"This kind of map is well-suited to building LRU caches."

你确实需要一个充分的理由来忽略这一点。我的猜测是，使用 Map 进行 put 的实现和 get 的实现之间的性能将无法区分 - 但是，嘿，为什么不运行自己的基准测试呢？

最后，您的实现(以及 LinkedHashMap 提供的实现)不是线程安全的。如果这对您来说是一个问题，那么同步逻辑将增加性能开销。