如何在 Java 中实现 LRU 缓存？

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

最新消息: 我正在通读 Yegge 是最新的的时候，发现了这个金块:

如果您需要常量时间访问并且希望维护插入顺序，那么 LinkedHashMap 是最好的选择，它是一个非常棒的数据结构。如果有一个并发版本，那么它可能会更加出色。但是，唉。

在我使用上面提到的 LinkedHashMap + Collections#synchronizedMap实现之前，我的想法几乎完全一样。很高兴我没有忽略什么。

基于到目前为止的答案，对于一个高度并发的 LRU 来说，最好的办法是使用与 LinkedHashMap相同的逻辑来扩展 ConcurrentHashMap。

131536 次浏览
小开

我会考虑使用 并发。优先级 BlockingQueue，其优先级由每个元素中的“ numberOfUse”计数器决定。我将是 非常非常小心，以获得所有的同步正确，因为“ numberOfUse”计数器意味着元素不能是不可变的。

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

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


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


... etc.
}
小开

看看 ConcurrentSkipListMap。如果一个元素已经包含在缓存中，那么它应该为您提供 log (n)时间来测试和删除该元素，并为重新添加该元素提供常量时间。

您只需要一些计数器等和包装器元素，以强制 LRU 顺序的顺序，并确保最近的东西是丢弃时，缓存已满。

小开

对于一个缓存，你通常会通过一个代理对象(URL，String...)来查找一些数据，所以在接口方面你需要一个映射。但是为了把东西踢出去，你需要一个类似于队列的结构。在内部，我将维护两个数据结构，一个优先级队列和一个 HashMap。这里有一个应该能够在 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，然后使用队列位置变量从队列中的当前位置删除密钥，然后把它放在队列的后面(它现在是最近使用的)。添加东西几乎是一样的。

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

小开

LinkedHashMap是 O (1) ，但是需要同步。不需要在那里重新发明轮子。

增加并发性的两种选择:

1. 创建多个 LinkedHashMap，并将其散列为: 例子: LinkedHashMap[4], index 0, 1, 2, 3。在键上执行 key%4(或 [key, 3]上的 binary OR)来选择执行 put/get/remove 操作的映射。

2. 您可以通过扩展 ConcurrentHashMap来实现一个“几乎”LRU，并在其中的每个区域中具有类似于链接散列映射的结构。与同步的 LinkedHashMap相比，锁定发生的粒度更大。在 put或 putIfAbsent上，只需要在列表的头部和尾部(每个区域)设置一个锁。在移除或获取时，需要锁定整个区域。我很好奇，如果原子链表的某种形式可能有助于这里-可能是这样的名单的头部。也许更多。

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

  1. 在适度的并发情况下，编写起来更容易，速度更快。

  2. 将更难编写，但是在高并发性下可以扩展得更好。对于正常访问，它会慢一些(就像 ConcurrentHashMap比没有并发的 HashMap慢一样)

小开

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

有两种开源实现。

ApacheSolr 具有 ConcurrentLRUCache: https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

有一个用于 ConcurrentLinkedHashMap 的开源项目: Http://code.google.com/p/concurrentlinkedhashmap/

小开

我正在寻找一个更好的 LRU 缓存使用 Java 代码。您可以使用 LinkedHashMap和 Collections#synchronizedMap共享您的 JavaLRU 缓存代码吗？目前我使用的是 LRUMap implements 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方法。

小开

这里是我的简短执行，请批评或改进！

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);
}
}
小开

下面是我测试过的性能最好的不带任何同步块的并发 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);
}

}

小开

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

Impleelrucache 提供了支持 TTL 的线程安全、非常简单的非分布式 LRU 缓存:

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

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

小开

本想对汉克给出的答案加上评论，但不知为何我不能——请把它当作评论

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 的最佳数据结构。

小开
最佳答案

如果我今天从头再做一次，我会使用番石榴的 CacheBuilder。

小开

这是我使用的 LRU 缓存，它封装了一个 LinkedHashMap，并使用一个保护多汁点的简单同步锁来处理并发。它“触及”的元素，因为他们使用，使他们成为“最新鲜”的元素，所以它实际上是 LRU。我还要求我的元素有一个最短的生命周期，你也可以认为是“最大的空闲时间”允许的，然后你就可以被驱逐了。

然而，我同意汉克的结论和接受的答案——如果我今天重新开始，我会查看番石榴的 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();
}
}


}
小开

下面是我的 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
PageName: 4，PageCreationTime: 1365957020174 < br/>

在这里输入密码

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;
}
}
小开

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

LinkedHashMap 提供了 RemoveEldestEntry 方法，可以按照示例中提到的方式重写该方法。默认情况下，此集合结构的实现为 false。如果这个结构的真实性和大小超出了初始容量，那么最年长或更老的元素将被删除。

我们可以有一个页码和页面内容在我的情况下，页码是整数和页面内容我保留了页码值字符串。

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


/**
* @author Deepak Singhvi
*
*/
public class LRUCacheUsingLinkedHashMap {




private static int CACHE_SIZE = 3;
public static void main(String[] args) {
System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99");
System.out.println("----------------------------------------------\n");




// accessOrder is true, so whenever any page gets changed or accessed,    // its order will change in the map,
LinkedHashMap<Integer,String> lruCache = new
LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) {


private static final long serialVersionUID = 1L;


protected boolean removeEldestEntry(Map.Entry<Integer,String>


eldest) {
return size() > CACHE_SIZE;
}


};


lruCache.put(2, "2");
lruCache.put(1, "1");
lruCache.put(0, "0");
System.out.println(lruCache + "  , After first 3 pages in cache");
lruCache.put(2, "2");
System.out.println(lruCache + "  , Page 2 became the latest page in the cache");
lruCache.put(8, "8");
System.out.println(lruCache + "  , Adding page 8, which removes eldest element 2 ");
lruCache.put(2, "2");
System.out.println(lruCache+ "  , Page 2 became the latest page in the cache");
lruCache.put(4, "4");
System.out.println(lruCache+ "  , Adding page 4, which removes eldest element 1 ");
lruCache.put(99, "99");
System.out.println(lruCache + " , Adding page 99, which removes eldest element 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
小开

这是第二回合。

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

所以这里是最简单的版本与单元测试，显示它的工作基于其他一些版本。

首先是非并发版本:

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




}

真正的标志将跟踪 get 和 put 的访问。参见 JavaDocs。没有构造函数的真正标志的 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 ();


}

现在说说并发版本。

包 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 w/o 实现来构建一个最简单的 LRU 缓存版本。

这是我想到的。我的第一次尝试是一个有点灾难，因为我实现了一个 LFU 而不是和 LRU，然后我添加了 FIFO，和 LRU 的支持... 然后我意识到它正在成为一个怪物。然后我开始和我的朋友约翰交谈，他几乎不感兴趣，然后我详细描述了我如何实现 LFU，LRU 和 FIFO，以及如何可以切换到一个简单的 ENUM 参数，然后我意识到我真正想要的是一个简单的 LRU。所以忽略我前面的帖子，让我知道如果你想看到一个 LRU/LFU/FIFO 缓存，可以通过枚举切换... 没有？好吧。.他来了。

最简单的可能的 LRU 只使用 JDK。我实现了一个并发版本和一个非并发版本。

我创建了一个通用的界面(它是极简主义的，所以很可能缺少一些你喜欢的特性，但是它适用于我的用例，但是如果你想看到特性 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 不会改变一个项目的 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 ();
}
}

如果您有一个大的缓存，那么 首次发生是一个潜在的昂贵操作。我们可以以 LinkedList 为例，添加从元素到节点的反向查找散列映射，以使删除操作更快、更一致。我也开始了，但后来意识到我不需要了。但是，也许。

当调用 把时，键被添加到队列中。当调用 快点时，键被删除并重新添加到队列的顶部。

如果您的缓存很小，并且构建一个项目的成本很高，那么这应该是一个很好的缓存。如果您的缓存真的很大，那么线性搜索可能是一个瓶颈，特别是如果您没有缓存的热区域。热点越强烈，线性搜索作为热点项目的速度越快，总是位于线性搜索的顶部。无论如何... 要让这个过程更快，需要编写另一个 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 (我本可以使用 synized，但是... ...)。

我还没有测试它在炮火，但它似乎是一个简单的 LRU 缓存，可能工作在80% 的用例中，你需要一个简单的 LRU 地图。

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

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

还有，如果有人知道准备好了..。

好吧。.我知道你在想什么... ... 为什么他不直接从 LinkedHashMap 中删除最长的条目呢? 我应该这么做，但是... ..。但是。.但是。.这将是一个先进先出，而不是一个 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 ();

因此，这里有一个快速和肮脏的 FIFO 缓存使用 RemoveEldestEntry。

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 很快。不要到处找。你可以前面一个先进先出的前面一个 LRU，这将处理大多数热门条目相当不错。一个更好的 LRU 将需要节点功能的反向元素。

无论如何... 现在我写了一些代码，让我看看其他的答案，看看我错过了什么... 第一次我扫描它们。

小开

LRU 缓存可以通过使用 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);
}


}
小开

Android 提供了一个 LRU 缓存的实现。

小开

希望这个能帮上忙。

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);
}
}
小开

遵循@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);
}
}
小开

最好的方法是使用 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);
}

}


提交答案