如何在 Java 中实现 LRU 缓存？

Question

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

更新：我刚刚阅读 Yegge 的最新作品，当我发现了这个金块：

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

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

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

Answer 1

我喜欢很多这些建议，但现在我想我会坚持使用 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));

Answer 2

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

Answer 3

这是第二轮。

第一轮是我想出的，然后我重新阅读了评论，这个域名在我的脑海中更加根深蒂固。

这是最简单的版本，带有单元测试，表明它可以基于其他一些版本工作。

首先是非并发版本：

import java.util.LinkedHashMap;
import java.util.Map;

public class LruSimpleCache<K, V> implements LruCache <K, V>{

    Map<K, V> map = new LinkedHashMap (  );


    public LruSimpleCache (final int limit) {
           map = new LinkedHashMap <K, V> (16, 0.75f, true) {
               @Override
               protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
                   return super.size() > limit;
               }
           };
    }
    @Override
    public void put ( K key, V value ) {
        map.put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map.get(key);
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        V value =  map.get ( key );
        if (value!=null) {
            map.remove ( key );
            map.put(key, value);
        }
        return value;
    }

    @Override
    public void remove ( K key ) {
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }


}

true 标志将跟踪 get 和 put 的访问。 请参阅 Java 文档。 如果构造函数没有 true 标志，removeEdelstEntry 只会实现一个 FIFO 缓存（请参阅下面有关 FIFO 和removeEldestEntry 的注释）。

下面是证明它可以作为 LRU 缓存工作的测试：

public class LruSimpleTest {

    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleCache<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        if ( !ok ) die ();

    }

现在对于并发版本...

package org.boon.cache;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LruSimpleConcurrentCache<K, V> implements LruCache<K, V> {

    final CacheMap<K, V>[] cacheRegions;


    private static class CacheMap<K, V> extends LinkedHashMap<K, V> {
        private final ReadWriteLock readWriteLock;
        private final int limit;

        CacheMap ( final int limit, boolean fair ) {
            super ( 16, 0.75f, true );
            this.limit = limit;
            readWriteLock = new ReentrantReadWriteLock ( fair );

        }

        protected boolean removeEldestEntry ( final Map.Entry<K, V> eldest ) {
            return super.size () > limit;
        }


        @Override
        public V put ( K key, V value ) {
            readWriteLock.writeLock ().lock ();

            V old;
            try {

                old = super.put ( key, value );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return old;

        }


        @Override
        public V get ( Object key ) {
            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.get ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;
        }

        @Override
        public V remove ( Object key ) {

            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.remove ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public V getSilent ( K key ) {
            readWriteLock.writeLock ().lock ();

            V value;

            try {

                value = this.get ( key );
                if ( value != null ) {
                    this.remove ( key );
                    this.put ( key, value );
                }
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public int size () {
            readWriteLock.readLock ().lock ();
            int size = -1;
            try {
                size = super.size ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return size;
        }

        public String toString () {
            readWriteLock.readLock ().lock ();
            String str;
            try {
                str = super.toString ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return str;
        }


    }

    public LruSimpleConcurrentCache ( final int limit, boolean fair ) {
        int cores = Runtime.getRuntime ().availableProcessors ();
        int stripeSize = cores < 2 ? 4 : cores * 2;
        cacheRegions = new CacheMap[ stripeSize ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) {

        cacheRegions = new CacheMap[ concurrency ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    private int stripeIndex ( K key ) {
        int hashCode = key.hashCode () * 31;
        return hashCode % ( cacheRegions.length );
    }

    private CacheMap<K, V> map ( K key ) {
        return cacheRegions[ stripeIndex ( key ) ];
    }

    @Override
    public void put ( K key, V value ) {

        map ( key ).put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map ( key ).get ( key );
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        return map ( key ).getSilent ( key );

    }

    @Override
    public void remove ( K key ) {
        map ( key ).remove ( key );
    }

    @Override
    public int size () {
        int size = 0;
        for ( CacheMap<K, V> cache : cacheRegions ) {
            size += cache.size ();
        }
        return size;
    }

    public String toString () {

        StringBuilder builder = new StringBuilder ();
        for ( CacheMap<K, V> cache : cacheRegions ) {
            builder.append ( cache.toString () ).append ( '\n' );
        }

        return builder.toString ();
    }


}

您可以明白为什么我首先介绍非并发版本。 上面尝试创建一些条带来减少锁争用。 因此，我们对密钥进行哈希处理，然后查找该哈希值以找到实际的缓存。 这使得限制大小更多地是在相当数量的错误内的建议/粗略猜测，具体取决于密钥散列算法的传播程度。

这是显示并发版本可能有效的测试。 :)（在火下测试才是真正的方法）。

public class SimpleConcurrentLRUCache {


    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 1, 4, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );

        puts (cache);
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();

        cache.put ( 8, 8 );
        cache.put ( 9, 9 );

        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        puts (cache);


        if ( !ok ) die ();

    }


    @Test
    public void test2 () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 400, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        for (int index =0 ; index < 5_000; index++) {
            cache.get(0);
            cache.get ( 1 );
            cache.put ( 2, index  );
            cache.put ( 3, index );
            cache.put(index, index);
        }

        boolean ok = cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 1 ) == 1 || die ();
        ok |= cache.getSilent ( 2 ) != null || die ();
        ok |= cache.getSilent ( 3 ) != null || die ();

        ok |= cache.size () < 600 || die();
        if ( !ok ) die ();



    }

}

这是最后一篇文章。我删除的第一篇文章，因为它是 LFU 而不是 LRU 缓存。

我想我会再试一次。 我试图使用标准 JDK 来提出最简单的 LRU 缓存版本，而无需太多实现。

这是我想出的。 我的第一次尝试有点灾难，因为我实现了 LFU 而不是 LRU，然后我添加了 FIFO 和 LRU 支持......然后我意识到它正在变成一个怪物。 然后我开始和我的好友约翰交谈，他几乎不感兴趣，然后我详细描述了我如何实现 LFU、LRU 和 FIFO 以及如何用一个简单的 ENUM arg 来切换它，然后我意识到我真正想要的只是是一个简单的 LRU。 因此，请忽略我之前的帖子，如果您想查看可通过枚举切换的 LRU/LFU/FIFO 缓存，请告诉我...不？ 好吧..他走了。

仅使用 JDK 的最简单的 LRU。 我实现了并发版本和非并发版本。

我创建了一个通用界面（它是极简主义的，所以可能会缺少一些您想要的功能，但它适用于我的用例，但是如果您想查看功能 XYZ，请告诉我......我活着就是为了编写代码。） 。

public interface LruCache<KEY, VALUE> {
    void put ( KEY key, VALUE value );

    VALUE get ( KEY key );

    VALUE getSilent ( KEY key );

    void remove ( KEY key );

    int size ();
}

您可能想知道 getSilent 是什么。 我用它来测试。 getSilent 不会更改项目的 LRU 分数。

首先是非并发的......

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LruCacheNormal<KEY, VALUE> implements LruCache<KEY,VALUE> {

    Map<KEY, VALUE> map = new HashMap<> ();
    Deque<KEY> queue = new LinkedList<> ();
    final int limit;


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );

        /*If there was already an object under this key,
         then remove it before adding to queue
         Frequently used keys will be at the top so the search could be fast.
         */
        if ( oldValue != null ) {
            queue.removeFirstOccurrence ( key );
        }
        queue.addFirst ( key );

        if ( map.size () > limit ) {
            final KEY removedKey = queue.removeLast ();
            map.remove ( removedKey );
        }

    }


    public VALUE get ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        queue.addFirst ( key );
        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

如果您有一个大的缓存，queue.removeFirstOccurrence 可能是一个昂贵的操作。 可以以 LinkedList 为例，添加从元素到节点的反向查找哈希映射，以使删除操作更快、更一致。 我也开始了，但后来发现我不需要它。 但是...也许...

当调用 put 时，密钥将被添加到队列中。 当调用 get 时，键将被删除并重新添加到队列顶部。

如果你的缓存很小并且构建一个项目很昂贵，那么这应该是一个很好的缓存。 如果您的缓存非常大，那么线性搜索可能会成为瓶颈，特别是如果您没有缓存的热点区域。 热点越强烈，线性搜索越快，因为热门项目始终位于线性搜索的顶部。 不管怎样......要想让这个过程更快，需要编写另一个具有删除操作的 LinkedList，该操作具有反向元素到节点查找以进行删除，然后删除的速度与从哈希映射中删除键一样快。

如果您的缓存少于 1,000 个项目，这应该可以正常工作。

这是一个简单的测试来展示其实际操作。

public class LruCacheTest {

    @Test
    public void test () {
        LruCache<Integer, Integer> cache = new LruCacheNormal<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == null || die ();
        ok |= cache.getSilent ( 1 ) == null || die ();
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();

        if ( !ok ) die ();

    }
}

最后一个 LRU 缓存是单线程的，请不要将其包装在同步的任何内容中......

这是对并发版本的尝试。

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentLruCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    private final ReentrantLock lock = new ReentrantLock ();


    private final Map<KEY, VALUE> map = new ConcurrentHashMap<> ();
    private final Deque<KEY> queue = new LinkedList<> ();
    private final int limit;


    public ConcurrentLruCache ( int limit ) {
        this.limit = limit;
    }

    @Override
    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );
        if ( oldValue != null ) {
            removeThenAddKey ( key );
        } else {
            addKey ( key );
        }
        if (map.size () > limit) {
            map.remove ( removeLast() );
        }
    }


    @Override
    public VALUE get ( KEY key ) {
        removeThenAddKey ( key );
        return map.get ( key );
    }


    private void addKey(KEY key) {
        lock.lock ();
        try {
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }


    }

    private KEY removeLast( ) {
        lock.lock ();
        try {
            final KEY removedKey = queue.removeLast ();
            return removedKey;
        } finally {
            lock.unlock ();
        }
    }

    private void removeThenAddKey(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }

    }

    private void removeFirstOccurrence(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
        } finally {
            lock.unlock ();
        }

    }


    @Override
    public VALUE getSilent ( KEY key ) {
        return map.get ( key );
    }

    @Override
    public void remove ( KEY key ) {
        removeFirstOccurrence ( key );
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString () {
        return map.toString ();
    }
}

主要区别是使用 ConcurrentHashMap 而不是 HashMap，以及 Lock 的使用（我本来可以使用同步，但是......）。

我还没有在火力下测试过它，但它似乎是一个简单的 LRU 缓存，可以在 80% 需要简单 LRU 映射的用例中工作。

我欢迎提供反馈，除了为什么不使用库 a、b 或 c 之外。
我不总是使用库的原因是因为我并不总是希望每个 war 文件都是 80MB，并且我编写库，所以我倾向于使用足够好的解决方案使库可插入，并且有人可以插入- 如果他们愿意的话，可以在另一个缓存提供程序中。 :)
我永远不知道什么时候有人可能需要 Guava 或 ehcache 或其他我不想包含它们的东西，但如果我使缓存可插入，我也不会排除它们。

减少依赖性有其自身的回报。 我喜欢获得一些关于如何使这变得更简单或更快或两者兼而有之的反馈。

另外，如果有人知道准备好了....

好吧..我知道你在想什么...他为什么不直接使用 LinkedHashMap 中的removeEldest条目，我应该但是....但是..但是.. 那将是一个 FIFO 而不是 LRU，我们正在尝试实现一个 LRU。

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };

上面的代码测试失败了...

        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();

所以这里是一个使用removeEldestEntry 的快速而脏的 FIFO 缓存。

import java.util.*;

public class FifoCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    final int limit;

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
         map.put ( key, value );


    }


    public VALUE get ( KEY key ) {

        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

FIFO 速度很快。 没有四处搜寻。 您可以将 FIFO 放在 LRU 前面，这样可以很好地处理大多数热条目。 更好的 LRU 将需要反向元素到节点功能。

不管怎样...现在我写了一些代码，让我浏览一下其他答案，看看我错过了什么...第一次扫描它们时。

Answer 4

LinkedHashMap 的复杂度为 O(1)，但需要同步。 无需在那里重新发明轮子。

提高并发性的 2 个选项：

1.
创建多个 LinkedHashMap，并对它们进行哈希处理：
示例：LinkedHashMap[4]，索引 0、1、2、3。 在键上执行 key%4 （或在 [key, 3] 上执行 binary OR）来选择要执行 put/get/ 操作的映射消除。

2.
您可以通过扩展 ConcurrentHashMap 来实现“几乎”LRU，并在其中的每个区域中具有类似链接的哈希映射结构。 与同步的 LinkedHashMap 相比，锁定的粒度会更细。 在 put 或 putIfAbsent 上，仅需要列表头部和尾部的锁定（每个区域）。 在删除或获取时，需要锁定整个区域。 我很好奇某种原子链表是否可能在这里有所帮助——对于列表的头部来说可能是这样。 也许是为了更多。

该结构不会保留总顺序，而只会保留每个区域的顺序。 只要条目的数量远大于区域的数量，这对于大多数缓存来说就足够了。 每个区域都必须有自己的条目计数，这将用于驱逐触发器，而不是全局计数。
ConcurrentHashMap 中的默认区域数量为 16，这对于当今的大多数服务器来说已经足够了。

1. 在中等并发情况下会更容易编写并且更快。

2. 编写起来会更困难，但在非常高的并发性下可以更好地扩展。 正常访问会更慢（就像没有并发时 ConcurrentHashMap 比 HashMap 慢一样）

Answer 5

有两个开源实现。

Apache Solr 有 ConcurrentLRUCache： https://lucene.apache .org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

有一个 ConcurrentLinkedHashMap 的开源项目：
http://code.google.com/p/concurrentlinkedhashmap/

Answer 6

我会考虑使用 java.util.concurrent.PriorityBlockingQueue，优先级由每个元素中的“numberOfUses”计数器确定。 我会非常非常小心确保所有同步正确，因为“numberOfUses”计数器意味着该元素不能是不可变的。

元素对象将是缓存中对象的包装器：

class CacheElement {
    private final Object obj;
    private int numberOfUsers = 0;

    CacheElement(Object obj) {
        this.obj = obj;
    }

    ... etc.
}

Answer 7

希望这可以帮助 。

import java.util.*;
public class Lru {

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {

        private static final long serialVersionUID = -3588047435434569014L;

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    };
 }
 public static void main(String[] args ) {
    Map<Object, Object> lru = Lru.lruCache(2);      
    lru.put("1", "1");
    lru.put("2", "2");
    lru.put("3", "3");
    System.out.println(lru);
}
}

Answer 8

LRU Cache 可以使用 ConcurrentLinkedQueue 和 ConcurrentHashMap 来实现，也可以在多线程场景中使用。 队列的头部是在队列中停留时间最长的元素。 队列的尾部是在队列中停留时间最短的元素。 当Map中存在一个元素时，我们可以将其从LinkedQueue中移除并插入到尾部。

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

public class LRUCache<K,V> {
  private ConcurrentHashMap<K,V> map;
  private ConcurrentLinkedQueue<K> queue;
  private final int size; 

  public LRUCache(int size) {
    this.size = size;
    map = new ConcurrentHashMap<K,V>(size);
    queue = new ConcurrentLinkedQueue<K>();
  }

  public V get(K key) {
    //Recently accessed, hence move it to the tail
    queue.remove(key);
    queue.add(key);
    return map.get(key);
  }

  public void put(K key, V value) {
    //ConcurrentHashMap doesn't allow null key or values
    if(key == null || value == null) throw new NullPointerException();
    if(map.containsKey(key) {
      queue.remove(key);
    }
    if(queue.size() >= size) {
      K lruKey = queue.poll();
      if(lruKey != null) {
        map.remove(lruKey);
      }
    }
    queue.add(key);
    map.put(key,value);
  }

}

Answer 9

这是我对 LRU 的实现。 我使用了 PriorityQueue，它基本上以 FIFO 的方式工作，而不是线程安全的。
使用基于页面时间创建和基于执行排序的比较器
最近最少使用时间的页面。

考虑的页面：2, 1, 0, 2, 8, 2, 4

添加到缓存的页面是：2
添加到缓存中的页面是：1
添加到缓存中的页面是：0
页：2 已存在于缓存中。 上次访问时间已更新
页面错误，页：1，替换为页：8
添加到缓存中的页面是：8
页：2 已存在于缓存中。 上次访问时间已更新
页面错误，页：0，替换为页：4
添加到缓存中的页面为：4

输出

LRUCache 页面
-------------
页面名称：8，页面创建时间：1365957019974
页面名称：2，页面创建时间：1365957020074
页面名称：4，页面创建时间：1365957020174

在此输入代码

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;


public class LRUForCache {
    private PriorityQueue<LRUPage> priorityQueue = new PriorityQueue<LRUPage>(3, new LRUPageComparator());
    public static void main(String[] args) throws InterruptedException {

        System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4");
        System.out.println("----------------------------------------------\n");

        LRUForCache cache = new LRUForCache();
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("1"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("0"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("8"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("4"));
        Thread.sleep(100);

        System.out.println("\nLRUCache Pages");
        System.out.println("-------------");
        cache.displayPriorityQueue();
    }


    public synchronized void  addPageToQueue(LRUPage page){
        boolean pageExists = false;
        if(priorityQueue.size() == 3){
            Iterator<LRUPage> iterator = priorityQueue.iterator();

            while(iterator.hasNext()){
                LRUPage next = iterator.next();
                if(next.getPageName().equals(page.getPageName())){
                    /* wanted to just change the time, so that no need to poll and add again.
                       but elements ordering does not happen, it happens only at the time of adding
                       to the queue

                       In case somebody finds it, plz let me know.
                     */
                    //next.setPageCreationTime(page.getPageCreationTime()); 

                    priorityQueue.remove(next);
                    System.out.println("Page: " + page.getPageName() + " already exisit in cache. Last accessed time updated");
                    pageExists = true;
                    break;
                }
            }
            if(!pageExists){
                // enable it for printing the queue elemnts
                //System.out.println(priorityQueue);
                LRUPage poll = priorityQueue.poll();
                System.out.println("Page Fault, PAGE: " + poll.getPageName()+", Replaced with PAGE: "+page.getPageName());

            }
        }
        if(!pageExists){
            System.out.println("Page added into cache is : " + page.getPageName());
        }
        priorityQueue.add(page);

    }

    public void displayPriorityQueue(){
        Iterator<LRUPage> iterator = priorityQueue.iterator();
        while(iterator.hasNext()){
            LRUPage next = iterator.next();
            System.out.println(next);
        }
    }
}

class LRUPage{
    private String pageName;
    private long pageCreationTime;
    public LRUPage(String pagename){
        this.pageName = pagename;
        this.pageCreationTime = System.currentTimeMillis();
    }

    public String getPageName() {
        return pageName;
    }

    public long getPageCreationTime() {
        return pageCreationTime;
    }

    public void setPageCreationTime(long pageCreationTime) {
        this.pageCreationTime = pageCreationTime;
    }

    @Override
    public boolean equals(Object obj) {
        LRUPage page = (LRUPage)obj; 
        if(pageCreationTime == page.pageCreationTime){
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return (int) (31 * pageCreationTime);
    }

    @Override
    public String toString() {
        return "PageName: " + pageName +", PageCreationTime: "+pageCreationTime;
    }
}


class LRUPageComparator implements Comparator<LRUPage>{

    @Override
    public int compare(LRUPage o1, LRUPage o2) {
        if(o1.getPageCreationTime() > o2.getPageCreationTime()){
            return 1;
        }
        if(o1.getPageCreationTime() < o2.getPageCreationTime()){
            return -1;
        }
        return 0;
    }
}

Answer 10

这是我测试的最佳性能并发 LRU 缓存实现，没有任何同步块：

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

/**
 * @param key - may not be null!
 * @param value - may not be null!
 */
public void put(final Key key, final Value value) {
    if (map.containsKey(key)) {
        queue.remove(key); // remove the key from the FIFO queue
    }

    while (queue.size() >= maxSize) {
        Key oldestKey = queue.poll();
        if (null != oldestKey) {
            map.remove(oldestKey);
        }
    }
    queue.add(key);
    map.put(key, value);
}

/**
 * @param key - may not be null!
 * @return the value associated to the given key or null
 */
public Value get(final Key key) {
    return map.get(key);
}

}

Answer 11

这是我使用的 LRU 缓存，它封装了 LinkedHashMap 并通过一个简单的同步锁来处理并发性，以保护有趣的地方。 它在使用元素时“触及”元素，使它们再次成为“最新鲜”的元素，因此它实际上是 LRU。 我还要求我的元素具有最短寿命，您也可以将其视为允许的“最大空闲时间”，然后您就可以驱逐。

不过，我同意 Hank 的结论并接受了答案——如果我今天再次开始，我会查看 Guava 的 CacheBuilder。

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;


public class MaxIdleLRUCache<KK, VV> {

    final static private int IDEAL_MAX_CACHE_ENTRIES = 128;

    public interface DeadElementCallback<KK, VV> {
        public void notify(KK key, VV element);
    }

    private Object lock = new Object();
    private long minAge;
    private HashMap<KK, Item<VV>> cache;


    public MaxIdleLRUCache(long minAgeMilliseconds) {
        this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) {
        this(minAgeMilliseconds, idealMaxCacheEntries, null);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback<KK, VV> callback) {
        this.minAge = minAgeMilliseconds;
        this.cache = new LinkedHashMap<KK, Item<VV>>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) {
            private static final long serialVersionUID = 1L;

            // This method is called just after a new entry has been added
            public boolean removeEldestEntry(Map.Entry<KK, Item<VV>> eldest) {
                // let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size.
                long age = System.currentTimeMillis() - eldest.getValue().birth;
                if (age > MaxIdleLRUCache.this.minAge) {
                    if ( callback != null ) {
                        callback.notify(eldest.getKey(), eldest.getValue().payload);
                    }
                    return true; // remove it
                }
                return false; // don't remove this element
            }
        };

    }

    public void put(KK key, VV value) {
        synchronized ( lock ) {
//          System.out.println("put->"+key+","+value);
            cache.put(key, new Item<VV>(value));
        }
    }

    public VV get(KK key) {
        synchronized ( lock ) {
//          System.out.println("get->"+key);
            Item<VV> item = getItem(key);
            return item == null ? null : item.payload;
        }
    }

    public VV remove(String key) {
        synchronized ( lock ) {
//          System.out.println("remove->"+key);
            Item<VV> item =  cache.remove(key);
            if ( item != null ) {
                return item.payload;
            } else {
                return null;
            }
        }
    }

    public int size() {
        synchronized ( lock ) {
            return cache.size();
        }
    }

    private Item<VV> getItem(KK key) {
        Item<VV> item = cache.get(key);
        if (item == null) {
            return null;
        }
        item.touch(); // idle the item to reset the timeout threshold
        return item;
    }

    private static class Item<T> {
        long birth;
        T payload;

        Item(T payload) {
            this.birth = System.currentTimeMillis();
            this.payload = payload;
        }

        public void touch() {
            this.birth = System.currentTimeMillis();
        }
    }

}

Answer 12

对于缓存来说，您通常会通过代理对象（URL、字符串......）查找一些数据，因此从接口角度来看，您将需要一个映射。 但为了把事情踢出去，你需要一个类似队列的结构。 在内部，我将维护两个数据结构，一个优先级队列和一个哈希映射。 这是一个应该能够在 O(1) 时间内完成所有事情的实现。

这是我很快就完成的课程：

import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
    int maxSize;
    int currentSize = 0;

    Map<K, ValueHolder<K, V>> map;
    LinkedList<K> queue;

    public LRUCache(int maxSize)
    {
        this.maxSize = maxSize;
        map = new HashMap<K, ValueHolder<K, V>>();
        queue = new LinkedList<K>();
    }

    private void freeSpace()
    {
        K k = queue.remove();
        map.remove(k);
        currentSize--;
    }

    public void put(K key, V val)
    {
        while(currentSize >= maxSize)
        {
            freeSpace();
        }
        if(map.containsKey(key))
        {//just heat up that item
            get(key);
            return;
        }
        ListNode<K> ln = queue.add(key);
        ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
        map.put(key, rv);       
        currentSize++;
    }

    public V get(K key)
    {
        ValueHolder<K, V> rv = map.get(key);
        if(rv == null) return null;
        queue.remove(rv.queueLocation);
        rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue
        return rv.value;
    }
}

class ListNode<K>
{
    ListNode<K> prev;
    ListNode<K> next;
    K value;
    public ListNode(K v)
    {
        value = v;
        prev = null;
        next = null;
    }
}

class ValueHolder<K,V>
{
    V value;
    ListNode<K> queueLocation;
    public ValueHolder(V value, ListNode<K> ql)
    {
        this.value = value;
        this.queueLocation = ql;
    }
}

class LinkedList<K>
{
    ListNode<K> head = null;
    ListNode<K> tail = null;

    public ListNode<K> add(K v)
    {
        if(head == null)
        {
            assert(tail == null);
            head = tail = new ListNode<K>(v);
        }
        else
        {
            tail.next = new ListNode<K>(v);
            tail.next.prev = tail;
            tail = tail.next;
            if(tail.prev == null)
            {
                tail.prev = head;
                head.next = tail;
            }
        }
        return tail;
    }

    public K remove()
    {
        if(head == null)
            return null;
        K val = head.value;
        if(head.next == null)
        {
            head = null;
            tail = null;
        }
        else
        {
            head = head.next;
            head.prev = null;
        }
        return val;
    }

    public void remove(ListNode<K> ln)
    {
        ListNode<K> prev = ln.prev;
        ListNode<K> next = ln.next;
        if(prev == null)
        {
            head = next;
        }
        else
        {
            prev.next = next;
        }
        if(next == null)
        {
            tail = prev;
        }
        else
        {
            next.prev = prev;
        }       
    }
}

这就是它的工作原理。 密钥存储在一个链接列表中，最旧的密钥位于列表的前面（新密钥位于后面），因此当您需要“弹出”某些内容时，只需将其从队列的前面弹出，然后使用该密钥即可从地图中删除该值。 当一个项目被引用时，您从映射中获取 ValueHolder，然后使用queuelocation 变量从队列中的当前位置删除该键，然后将其放在队列的后面（现在是最近使用的）。 添加东西几乎是一样的。

我确信这里有很多错误，而且我还没有实现任何同步。 但此类将提供 O(1) 添加到缓存、O(1) 删除旧项目以及 O(1) 检索缓存项目。 即使是简单的同步（只需同步每个公共方法），由于运行时间的原因，仍然会出现很少的锁争用。 如果有人有任何聪明的同步技巧，我会非常感兴趣。 另外，我确信您可以使用与地图相关的 maxsize 变量来实现一些额外的优化。

Answer 13

最好的实现方法是使用 LinkedHashMap 来维护元素的插入顺序。 以下是示例代码：

public class Solution {

Map<Integer,Integer> cache;
int capacity;
public Solution(int capacity) {
    this.cache = new LinkedHashMap<Integer,Integer>(capacity); 
    this.capacity = capacity;

}

// This function returns false if key is not 
// present in cache. Else it moves the key to 
// front by first removing it and then adding 
// it, and returns true. 

public int get(int key) {
if (!cache.containsKey(key)) 
        return -1; 
    int value = cache.get(key);
    cache.remove(key); 
    cache.put(key,value); 
    return cache.get(key); 

}

public void set(int key, int value) {

    // If already present, then  
    // remove it first we are going to add later 
       if(cache.containsKey(key)){
        cache.remove(key);
    }
     // If cache size is full, remove the least 
    // recently used. 
    else if (cache.size() == capacity) { 
        Iterator<Integer> iterator = cache.keySet().iterator();
        cache.remove(iterator.next()); 
    }
        cache.put(key,value);
}

}

Answer 14

查看 ConcurrentSkipListMap。 如果元素已包含在缓存中，它应该为您提供 log(n) 时间来测试和删除该元素，并为您提供恒定的时间来重新添加它。

您只需要一些计数器等和包装器元素来强制对 LRU 顺序进行排序，并确保在缓存已满时丢弃最近的内容。

Answer 15

这是我的简短实现，请批评或改进！

package util.collection;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Limited size concurrent cache map implementation.<br/>
 * LRU: Least Recently Used.<br/>
 * If you add a new key-value pair to this cache after the maximum size has been exceeded,
 * the oldest key-value pair will be removed before adding.
 */

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;
private int currentSize = 0;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

private synchronized void freeSpace() {
    Key key = queue.poll();
    if (null != key) {
        map.remove(key);
        currentSize = map.size();
    }
}

public void put(Key key, Value val) {
    if (map.containsKey(key)) {// just heat up that item
        put(key, val);
        return;
    }
    while (currentSize >= maxSize) {
        freeSpace();
    }
    synchronized(this) {
        queue.add(key);
        map.put(key, val);
        currentSize++;
    }
}

public Value get(Key key) {
    return map.get(key);
}
}

Answer 16

这是我自己对这个问题的实现

simplelrucache 提供了线程安全、非常简单、非分布式 LRU 缓存，并支持 TTL。 它提供了两种实现：

• 基于 ConcurrentLinkedHashMap 的
• 并发 基于 LinkedHashMap 的同步

您可以在这里找到它： http://code .google.com/p/simplelrucache/

Answer 17

我正在寻找使用 Java 代码的更好的 LRU 缓存。 您是否可以使用 LinkedHashMap 和 Collections#synchronizedMap 共享您的 Java LRU 缓存代码？ 目前，我正在使用 LRUMap 实现 Map 并且代码工作正常，但在使用以下方法使用 500 个用户进行负载测试时，我收到 ArrayIndexOutofBoundException 。 该方法将最近的对象移动到队列的前面。

private void moveToFront(int index) {
        if (listHead != index) {
            int thisNext = nextElement[index];
            int thisPrev = prevElement[index];
            nextElement[thisPrev] = thisNext;
            if (thisNext >= 0) {
                prevElement[thisNext] = thisPrev;
            } else {
                listTail = thisPrev;
            }
            //old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1
            // prev[0 old head] = new head right ; next[new head] = old head
            prevElement[index] = -1;
            nextElement[index] = listHead;
            prevElement[listHead] = index;
            listHead = index;
        }
    }

get(Object key) 和 put(Object key, Object value) 方法调用上面的 moveToFront 方法。

Answer 18

想要对 Hank 给出的答案添加评论，但有些我无法 - 请将其视为评论

LinkedHashMap 也根据其构造函数中传递的参数来维护访问顺序
它保持双行列表以维持顺序（请参阅 LinkedHashMap.Entry）

@Pacerier 如果再次添加元素，LinkedHashMap 在迭代时保持相同的顺序是正确的，但这仅适用于插入顺序模式。

这是我在 LinkedHashMap.Entry 对象的 java 文档中发现的，

    /**
     * This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }

该方法负责将最近访问的元素移动到列表的末尾。 所以总而言之LinkedHashMap是实现LRUCache的最佳数据结构。

Answer 19

另一种想法甚至是使用Java的LinkedHashMap集合的简单实现。

LinkedHashMap提供了removeEldestEntry方法，可以按照示例中提到的方式重写该方法。 默认情况下，该集合结构的实现为 false。 如果该结构的真实大小超出了初始容量，则最旧或较旧的元素将被删除。

我们可以有一个 pageno 和页面内容，在我的例子中 pageno 是整数，而 pagecontent 我保留了页码值字符串。

导入java.util.LinkedHashMap; 
  导入java.util.Map； 

  /** 
   * @作者迪帕克·辛格维 
   * 
   */ 
  公共类 LRUCacheUsingLinkedHashMap { 


       私有静态 int CACHE_SIZE = 3; 
       公共静态无效主（字符串[] args）{ 
          System.out.println("需要考虑的页数: 2, 1, 0, 2, 8, 2, 4,99"); 
          System.out.println("-------------------------------------------------------- ---\n"); 


  // accessOrder 为 true，因此每当任何页面被更改或访问时， // 它在地图中的顺序都会改变，  
                LinkedHashMap<整数,字符串>   lruCache = 新               
                   LinkedHashMap(CACHE_SIZE, .75F, true) { 

             私有静态最终长serialVersionUID = 1L; 

             protected boolean removeEldestEntry(Map.Entry;                            

                       最年长的）{ 
                            返回大小() >   缓存_大小； 
                       } 

                  }; 

    lruCache.put(2, "2"); 
    lruCache.put(1, "1"); 
    lruCache.put(0, "0"); 
    System.out.println(lruCache + " , 在缓存中的前 3 页之后"); 
    lruCache.put(2, "2"); 
    System.out.println(lruCache + " , 第 2 页成为缓存中的最新页"); 
    lruCache.put(8, "8"); 
    System.out.println(lruCache + " , 添加第 8 页，删除最老的元素 2 "); 
    lruCache.put(2, "2"); 
    System.out.println(lruCache+ " , 第 2 页成为缓存中的最新页"); 
    lruCache.put(4, "4"); 
    System.out.println(lruCache+ " , 添加第 4 页，删除最老的元素 1 "); 
    lruCache.put(99, "99"); 
    System.out.println(lruCache + " , 添加第 99 页，删除最老的元素 8 "); 

       } 

  } 
  

上述代码执行结果如下：

 Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99
--------------------------------------------------
    {2=2, 1=1, 0=0}  , After first 3 pages in cache
    {2=2, 1=1, 0=0}  , Page 2 became the latest page in the cache
    {1=1, 0=0, 8=8}  , Adding page 8, which removes eldest element 2 
    {0=0, 8=8, 2=2}  , Page 2 became the latest page in the cache
    {8=8, 2=2, 4=4}  , Adding page 4, which removes eldest element 1 
    {2=2, 4=4, 99=99} , Adding page 99, which removes eldest element 8 

Answer 20

遵循@sanjanab概念（但在修复之后），我制作了我的LRUCache版本，还提供了Consumer，允许在需要时对已删除的项目执行某些操作。

public class LRUCache<K, V> {

    private ConcurrentHashMap<K, V> map;
    private final Consumer<V> onRemove;
    private ConcurrentLinkedQueue<K> queue;
    private final int size;

    public LRUCache(int size, Consumer<V> onRemove) {
        this.size = size;
        this.onRemove = onRemove;
        this.map = new ConcurrentHashMap<>(size);
        this.queue = new ConcurrentLinkedQueue<>();
    }

    public V get(K key) {
        //Recently accessed, hence move it to the tail
        if (queue.remove(key)) {
            queue.add(key);
            return map.get(key);
        }
        return null;
    }

    public void put(K key, V value) {
        //ConcurrentHashMap doesn't allow null key or values
        if (key == null || value == null) throw new IllegalArgumentException("key and value cannot be null!");

        V existing = map.get(key);
        if (existing != null) {
            queue.remove(key);
            onRemove.accept(existing);
        }

        if (map.size() >= size) {
            K lruKey = queue.poll();
            if (lruKey != null) {
                V removed = map.remove(lruKey);
                onRemove.accept(removed);
            }
        }
        queue.add(key);
        map.put(key, value);
    }
}

Answer 21

Android 提供了 LRU 缓存 的实现。 代码干净、简单。