你将如何在Java中实现LRU缓存?

请不要说EHCache或OSCache等。为了这个问题的目的,假设我想用我自己的SDK来实现(边干边学)。 鉴于缓存将在多线程环境中使用,您将使用哪种数据结构? 我已经使用LinkedHashMap和Collections#synchronizedMap实现了一个,但是我很好奇新的并发集合是否更好。

更新:当我发现这块金块时,我正在阅读Yegge的最新消息:

如果您需要恒定时间的访问权限并希望维护插入顺序,那么您无法比LinkedHashMap做得更好,这是一个非常棒的数据结构。 唯一可能更好的方法是如果有一个并发版本。 可惜。

在我使用前面提到的LinkedHashMap + Collections#synchronizedMap实现之前,我正在考虑几乎完全一样的事情。 很高兴知道我不只是忽略了一些东西。

根据迄今为止的答案,这听起来像是我最好的选择,高度并发的LRU将使用LinkedHashMap使用的一些相同的逻辑来扩展ConcurrentHashMap。


我喜欢这些建议,但现在我认为我会坚持使用LinkedHashMap + Collections.synchronizedMap 。 如果我将来会重新讨论这个问题,那么我可能会以与LinkedHashMap扩展HashMap相同的方式来扩展ConcurrentHashMap

更新:

根据要求,这是我目前实施的要点。

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

或者使用这个Apache Commons数据结构:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/LRUMap.html


如果我今天再次从头开始,我会使用Guava的CacheBuilder

链接地址: http://www.djcxy.com/p/44041.html

上一篇: How would you implement an LRU cache in Java?

下一篇: What are the pros and cons of the assorted Java web frameworks?