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

caching data-structures java lru

2022-08-31 06:57:01

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

更新：当我发现这个金块时，我刚刚阅读了Yegge的最新内容：

如果您需要恒定时间访问并希望保持广告顺序，那么您没有比LinkedHashMap更好的了，这是一个真正美妙的数据结构。它可能更精彩的唯一方法是如果有一个并发版本。但是，唉。

在我使用上面提到的+实现之前，我的想法几乎完全相同。很高兴知道我没有忽略一些东西。LinkedHashMapCollections#synchronizedMap

根据到目前为止的答案，听起来我对高度并发LRU的最佳选择是使用一些与使用相同的逻辑来扩展ProcurrentHashMap。LinkedHashMap

答案 1

我喜欢很多这样的建议，但现在我想我会坚持+。如果我将来重新审视这一点，我可能会以同样的方式扩展。LinkedHashMapCollections.synchronizedMapConcurrentHashMapLinkedHashMapHashMap

更新：

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

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));

答案 2

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