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

Question

您将如何在Java中实现LRU缓存？请不要说EHCache或OSCache等。为了这个问题的目的，假设我只想使用SDK（从实践中学习）来实现我自己的。鉴于缓存将在多线程环境中使用，您将使用哪些数据结构？我已经使用LinkedHashMap和Collections＃synchronizedMap实现了一个，但我很好奇任何新的并发集合是否会更好。更新：当我发现这个金块时，我只是阅读Yegge的最新消息：如果您需要持续时间访问并希望维护插入顺序，那么您不能比LinkedHashMap做得更好，这是一个真正精彩的数据结构。它可能更精彩的唯一方法是如果有并发版本。可惜。在我使用上面提到的LinkedHashMap+ Collections#synchronizedMap实现之前，我的想法几乎完全相同。很高兴知道我不只是忽略了一些东西。基于到目前为止的答案，对于高度并发的LRU来说，我最好的选择是使用一些相同的逻辑来扩展ConcurrentHashMapLinkedHashMap。

Answer 1

我喜欢很多这些建议，但现在我觉得我会坚持LinkedHashMap+ Collections.synchronizedMap。如果我将来重新考虑这个，我可能会ConcurrentHashMap以同样的方式LinkedHashMap扩展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));

Answer 2

如果我今天再次从头开始这样做，我会使用番石榴CacheBuilder。