将如何在Java中实现LRU缓存？

Question

不要说EHCache或OSCache等。出于这个问题的目的，假设我想仅使用SDK实现自己的实现（边做边学）。考虑到缓存将在多线程环境中使用，你将使用哪些数据结构？我已经使用LinkedHashMap和Collections＃synchronizedMap实现了一个，但是我很好奇是否有任何新的并发集合会更好。

更新：当我发现这个块时，我只是在阅读Yegge的最新文章：

如果你需要固定时间的访问权限并希望保持插入顺序，那么做一个比一个真正出色的数据结构LinkedHashMap更好的选择。可能更妙的唯一方法是有并发版本。可惜。

在进行上面提到的LinkedHashMap+ Collections#synchronizedMap实现之前，我一直在思考几乎完全相同的事情。很高兴知道我并没有忽略某些事情。

根据到目前为止的答案，听起来对于高并发LRU来说，我最好的选择是使用一些使用相同的逻辑来扩展ConcurrentHashMapLinkedHashMap。

Answer 1

我很喜欢这些建议，但现在我还是坚持使用LinkedHashMap+ Collections.synchronizedMap。如果以后再讨论这个问题，我可能会ConcurrentHashMap以LinkedHashMapextends 相同的方式进行扩展HashMap。

更新：

根据要求，这是我当前实现的要点。

private class LruCache<A, B> extends LinkedHashMap<A, B> {
    private final int maxEntries;

    public LruCache(final int maxEntries) {
        super(maxEntries + 1, 1.0f, true);
        this.maxEntries = maxEntries;
    }

    /**
     * Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
     * created.
     *
     * <p>
     * This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
     * <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
     * <code>LinkedHashMap</code>.
     * </p>
     *
     * @param eldest
     *            the <code>Entry</code> in question; this implementation doesn't care what it is, since the
     *            implementation is only dependent on the size of the cache
     * @return <tt>true</tt> if the oldest
     * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return super.size() > maxEntries;
    }
}

Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));