Java中的LRU缓存，具有generics和O（1）操作

这是一个在求职面试中出现的问题。 我们的想法是定义一个数据结构，而不是使用Java内置的LinkedHashMap。

LRU高速缓存删除最近最少使用的条目以插入新条目。 因此，给出以下场景：

A - B - C - D - E 

如果A是最近最少使用的项目，如果我们要插入F，我们需要删除A.

如果我们通过（键，值）保存带有缓存条目的HashMap和包含元素的键和使用时间的单独列表，则可以很容易地实现这一点。 但是，我们需要查询列表以找到最近最少使用的项目，具有潜在的O（n）时间复杂度。

如何在Java中为通用对象和O（1）操作实现此结构？

这与可能的重复不同，因为它侧重于效率（O（1）ops）和实现数据结构本身，而不是扩展Java。

Answer 1

从问题本身，我们可以看到在查询链表时出现O（n）操作的问题。 因此，我们需要一种替代数据结构。 我们需要能够在不搜索的情况下从HashMap更新项目的上次访问时间。

我们可以保留两个独立的数据结构。 带有（Key，Pointer）对的HashMap和一个双向链表 ，它将作为删除的优先级队列并存储值。 从HashMap中，我们可以指向双向链表中的元素并更新其检索时间。 因为我们直接从HashMap到列表中的项目，我们的时间复杂度仍为O（1）

例如，我们的双向链表可能如下所示：

 least_recently_used -> A <-> B <-> C <-> D <-> E <- most_recently_used 

我们需要保持指向LRU和MRU项的指针。 条目的值将存储在列表中，当我们查询HashMap时，我们将获得指向列表的指针。 在get（）中，我们需要将项目放在列表的最右侧。 在put（key，value）上，如果缓存已满，我们需要从列表和HashMap中删除列表最左侧的项目。

以下是Java中的示例实现：

 public class LRUCache{ // Define Node with pointers to the previous and next items and a key, value pair class Node { Node previous; Node next; T key; U value; public Node(Node previous, Node next, T key, U value){ this.previous = previous; this.next = next; this.key = key; this.value = value; } } private HashMap> cache; private Node leastRecentlyUsed; private Node mostRecentlyUsed; private int maxSize; private int currentSize; public LRUCache(int maxSize){ this.maxSize = maxSize; this.currentSize = 0; leastRecentlyUsed = new Node(null, null, null, null); mostRecentlyUsed = leastRecentlyUsed; cache = new HashMap>(); } public V get(K key){ Node tempNode = cache.get(key); if (tempNode == null){ return null; } // If MRU leave the list as it is else if (tempNode.key == mostRecentlyUsed.key){ return mostRecentlyUsed.value; } // Get the next and previous nodes Node nextNode = tempNode.next; Node previousNode = tempNode.previous; // If at the left-most, we update LRU if (tempNode.key == leastRecentlyUsed.key){ nextNode.previous = null; leastRecentlyUsed = nextNode; } // If we are in the middle, we need to update the items before and after our item else if (tempNode.key != mostRecentlyUsed.key){ previousNode.next = nextNode; nextNode.previous = previousNode; } // Finally move our item to the MRU tempNode.previous = mostRecentlyUsed; mostRecentlyUsed.next = tempNode; mostRecentlyUsed = tempNode; mostRecentlyUsed.next = null; return tempNode.value; } public void put(K key, V value){ if (cache.containsKey(key)){ return; } // Put the new node at the right-most end of the linked-list Node myNode = new Node(mostRecentlyUsed, null, key, value); mostRecentlyUsed.next = myNode; cache.put(key, myNode); mostRecentlyUsed = myNode; // Delete the left-most entry and update the LRU pointer if (currentSize == maxSize){ cache.remove(leastRecentlyUsed.key); leastRecentlyUsed = leastRecentlyUsed.next; leastRecentlyUsed.previous = null; } // Update cache size, for the first added entry update the LRU pointer else if (currentSize < maxSize){ if (currentSize == 0){ leastRecentlyUsed = myNode; } currentSize++; } } } 

Answer 2

通过leetcode questiton +简单unit testing的测试的实现如下。

我已经通过以下方式提出了拉取请求： https ： //github.com/haoel/leetcode/pull/90/files

LRUCache.java

 import java.util.LinkedHashMap; import java.util.Iterator; public class LRUCache { private int capacity; private LinkedHashMap map; public LRUCache(int capacity) { this.capacity = capacity; this.map = new LinkedHashMap<>(); } public int get(int key) { Integer value = this.map.get(key); if (value == null) { value = -1; } else { this.set(key, value); } return value; } public void set(int key, int value) { if (this.map.containsKey(key)) { this.map.remove(key); } else if (this.map.size() == this.capacity) { Iterator it = this.map.keySet().iterator(); it.next(); it.remove(); } map.put(key, value); } } 

LRUCacheTest.java ：

 import java.util.ArrayList; import org.junit.Test; import static org.junit.Assert.*; public class LRUCacheTest { private LRUCache c; public LRUCacheTest() { this.c = new LRUCache(2); } @Test public void testCacheStartsEmpty() { assertEquals(c.get(1), -1); } @Test public void testSetBelowCapacity() { c.set(1, 1); assertEquals(c.get(1), 1); assertEquals(c.get(2), -1); c.set(2, 4); assertEquals(c.get(1), 1); assertEquals(c.get(2), 4); } @Test public void testCapacityReachedOldestRemoved() { c.set(1, 1); c.set(2, 4); c.set(3, 9); assertEquals(c.get(1), -1); assertEquals(c.get(2), 4); assertEquals(c.get(3), 9); } @Test public void testGetRenewsEntry() { c.set(1, 1); c.set(2, 4); assertEquals(c.get(1), 1); c.set(3, 9); assertEquals(c.get(1), 1); assertEquals(c.get(2), -1); assertEquals(c.get(3), 9); } } 

removeEldestEntry（）替代实现

不确定它是否值得，因为它需要相同的行数，但这里是完成：

 import java.util.LinkedHashMap; import java.util.Iterator; import java.util.Map; class LinkedhashMapWithCapacity extends LinkedHashMap { private int capacity; public LinkedhashMapWithCapacity(int capacity) { this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return this.size() > this.capacity; } } public class LRUCache { private LinkedhashMapWithCapacity map; public LRUCache(int capacity) { this.map = new LinkedhashMapWithCapacity<>(capacity); } public int get(int key) { Integer value = this.map.get(key); if (value == null) { value = -1; } else { this.set(key, value); } return value; } public void set(int key, int value) { if (this.map.containsKey(key)) this.map.remove(key); this.map.get(key); } } 

Answer 3

LinkedHashMap就是为此而设计的

来自javadocs：

提供了一个特殊的构造函数来创建链接的哈希映射，其迭代顺序是其条目最后一次访问的顺序，从最近访问到最近（访问顺序）。 这种地图非常适合构建LRU缓存。 调用put，putIfAbsent，get，getOrDefault，compute，computeIfAbsent，computeIfPresent或merge方法会导致访问相应的条目（假设它在调用完成后存在）。 如果替换值，则replace方法仅导致访问条目。 putAll方法为指定映射中的每个映射生成一个条目访问，按照指定映射的条目集迭代器提供键 – 值映射的顺序。 没有其他方法可以生成入口访问。 特别是，对集合视图的操作不会影响后备映射的迭代顺序。

可以重写removeEldestEntry（Map.Entry）方法，以强制在将新映射添加到映射时自动删除过时映射的策略。

Answer 4

使用Stack和HashMap：

 import java.util.HashMap; import java.util.Stack; public class LRU { private HashMap lruList; private Stack stackOrder; private int capacity; LRU(int capacity){ this.capacity = capacity; this.lruList = new HashMap(capacity); this.stackOrder = new Stack(); } public void put(String key, Object value){ if(lruList.containsKey(key) || this.capacity < lruList.size() + 1) { if(lruList.containsKey(key)){ String remove = key; }else{ String remove = this.stackOrder.firstElement(); } this.stackOrder.removeElement(remove); this.lruList.remove(remove); } this.lruList.put(key, value); this.stackOrder.add(key); } public Stack get(){ return this.stackOrder; } public Object get(String key){ Object value = lruList.get(key); put(key, value); return value; } } public static void main(String[] args) { LRU lru = new LRU(3); lru.put("k1","v1"); lru.put("k2","v2"); lru.put("k3","v3"); System.out.println(lru.get()); lru.get("k1"); System.out.println(lru.get()); lru.put("k4","v4"); System.out.println(lru.get()); } 

输出：

[k1，k2，k3]

[k2，k3，k1]

[k3，k1，k4]

Answer 5

 /*Java implementation using Deque and HashMap */ interface Cache { V get(K key) ; void set(K key, V value); } class Node { K key; V value; public Node (K key, V value) { this.key = key; this.value = value; } } public class LRUCache  implements Cache{ Deque> dq = new LinkedList<>(); Map> map = new HashMap<>(); static int SIZE; public LRUCache(int size) { this.SIZE = size; } public V get(K key) { Node result = map.get(key); if(result != null) { dq.remove(result); dq.addFirst(result); System.out.println("Get " +key +" : " +result.value); return result.value; } else { System.out.println("Cache miss"); return null; } } public void set(K key, V value) { System.out.println("Set " +key +" : " +value); Node result = map.get(key); if(result != null) { result.value = value; map.put(key, result); dq.remove(result); dq.addFirst(result); System.out.println("Updated frame " +key+" as " + value); } else { if(dq.size() == SIZE) { Node toRemove = dq.removeLast(); map.remove(toRemove); System.out.println("Frame removed " +toRemove.key +" : " +toRemove.value); } Node newNode = new Node(key, value); dq.addFirst(newNode); map.put(key, newNode); System.out.println("Frame added " + key + " : " +value); } } public static void main(String[] args) { Cache lru = new LRUCache<>(5); lru.get(2); lru.set(1, 11); lru.set(2, 22); lru.get(2); lru.set(3, 33); lru.set(4, 44); lru.set(5, 55); lru.get(2); lru.get(1); lru.set(6, 66); } } 

Answer 6

@templatetypedef

 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 

accessOrder – 排序模式 – 对于访问顺序为true，对于插入顺序为false

Answer 7

理念

缓存只不过是圆形arrayList。 此列表包含条目。 什么时候新的条目将添加到列表的末尾。 这意味着最初最少使用的元素。 假设您正在重用任何元素，然后从列表中取消链接并在末尾添加。

为了得到任何我们需要遍历列表的元素，这需要O（n）时间复杂度。 为了避免这种情况，我正在维护HashMap>。 这里k是键，IndexNode将包含指向列表中Entry的指针。 所以我们可以得到O（1）时间复杂度。

工作方案

 package lrucache; import java.util.HashMap; public class LRUCache { private transient Entry header = new Entry(null, null, null, null); public HashMap>> indexMap = new HashMap>>(); private final int CACHE_LIMIT = 3; private int size; public LRUCache() { header.next = header.previous = header; this.size = 0; } public void put(K key,V value){ Entry newEntry = new Entry(key,value,null,null); addBefore(newEntry, header); } private void addBefore(Entry newEntry,Entry entry){ if((size+1)<(CACHE_LIMIT+1)){ newEntry.next=entry; newEntry.previous=entry.previous; IndexNode> indexNode = new IndexNode>(newEntry); indexMap.put(newEntry.key, indexNode); newEntry.previous.next=newEntry; newEntry.next.previous=newEntry; size++; }else{ Entry entryRemoved = remove(header.next); indexMap.remove(entryRemoved.key); addBefore(newEntry, entry); } } public void get(K key){ if(indexMap.containsKey(key)){ Entry newEntry = remove(indexMap.get(key).pointer); addBefore(newEntry,header); }else{ System.out.println("No such element was cached. Go and get it from Disk"); } } private Entry remove(Entry entry){ entry.previous.next=entry.next; entry.next.previous = entry.previous; size--; return entry; } public void display(){ for(Entry curr=header.next;curr!=header;curr=curr.next){ System.out.println("key : "+curr.key+" value : " + curr.value); } } private static class IndexNode{ private Entry pointer; public IndexNode(Entry pointer){ this.pointer = pointer; } } private static class Entry { K key; V value; Entry previous; Entry next; Entry(K key, V value, Entry next, Entry previous) { this.key = key; this.value = value; this.next = next; this.previous = previous; } } public static void main(String[] args) { LRUCache cache = new LRUCache(); cache.put("abc", 1); //cache.display(); cache.put("def", 2); cache.put("ghi", 3); cache.put("xyz", 4); cache.put("xab", 5); cache.put("xbc", 6); cache.get("xyz"); cache.display(); System.out.println(cache.indexMap); } } 

产量

 key : xab value : 5 key : xbc value : 6 key : xyz value : 4 {xab=lrucache.LRUCache$IndexNode@c3d9ac, xbc=lrucache.LRUCache$IndexNode@7d8bb, xyz=lrucache.LRUCache$IndexNode@125ee71} 

Answer 8

我们可以使用LinkedHashMap ..它具有删除最老条目的function

 import java.util.LinkedHashMap; import java.util.Map; public LRUCache extends LinkedHashMap { private int cacheSize; public LRUCache(int cacheSize) { super(16, 0.75, true); this.cacheSize = cacheSize; } protected boolean removeEldestEntry(Map.Entry eldest) { return size() >= cacheSize; } } 

唯一的问题是，默认情况下，链接列表顺序是插入顺序，而不是访问。 但是，其中一个构造函数公开了一个选项，而是使用访问顺序。

Answer 9

我只是写了这个非常简单的通用解决方案，虽然这个解决方案不是Thread安全的。

LRUCacheDemo.java （公共类）

 import java.io.*; import java.util.*; /* We can keep two separate data structures. A HashMap with (Key,Pointer) pairs and a doubly linked list which will work as the priority queue for deletion and store the Values. From the HashMap, we can point to an element in the doubly linked list and update its' retrieval time. Because we go directly from the HashMap to the item in the list, our time complexity remains at O(1) */ public class LRUCacheDemo { public static void main(String args[]) { LRUCache lru = new LRUCache<>(3); for(int i=1; i<=9; ++i) { lru.put(i, 100*i+10*i+i); //i iii } lru.get(8); /* for(Map.Entry entry : lru.entrySet()) { System.out.printf("\n%1$-5s %2$-5s", entry.getKey(), entry.getValue()); } */ System.out.println("LRU : " + lru); } } class LRUCache extends LinkedHashMap { private final int CACHE_SIZE; //NOTE : LinkedHashMap have already given implementation for LRU, this class has just used those method //See http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedHashMap.java#LinkedHashMap // LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) // accessOrder - to maintain in order of elements from least-recently accessed to most-recently. LRUCache(final int sizeIn) { super(sizeIn, 0.75F, true); this.CACHE_SIZE = sizeIn; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > this.CACHE_SIZE; /* Returns true if this map should remove its eldest entry. This method is invoked by put and putAll after inserting a new entry into the map. It provides the implementor with the opportunity to remove the eldest entry each time a new one is added. This is useful if the map represents a cache. */ } } 

O / P：

 LRU : {7=777, 9=999, 8=888} 

Answer 10

下面是使用Generics和LinkedHashMap的java实现，以及get()和put()上的O（1）的复杂性。

 import java.util.LinkedHashMap; public class LRUCache { private LinkedHashMap lruCacheMap; private final int capacity; private final boolean SORT_BY_ACCESS = true; private final float LOAD_FACTOR = 0.75F; public LRUCache(int capacity){ this.capacity = capacity; this.lruCacheMap = new LinkedHashMap<>(capacity, LOAD_FACTOR, SORT_BY_ACCESS); } public V get(K k){ return lruCacheMap.get(k); } public void put(K k, V v){ if(lruCacheMap.containsKey(k)){ lruCacheMap.remove(k); }else if(lruCacheMap.size() >= capacity){ lruCacheMap.remove(lruCacheMap.keySet().iterator().next()); } lruCacheMap.put(k, v); } public void printSequence(){ System.out.println(lruCacheMap.keySet()); } } 

这是测试它的代码：

 import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class TestLruCache { static class MyHardDrive { Map resources = new HashMap<>(); MyHardDrive(){ for(Character i='A'; i<='Z'; i++){ resources.put(i.toString(), new Object()); } } Object loadResource(String name){ return resources.get(name); } } public static void main(String[] args) { MyHardDrive hd = new MyHardDrive(); LRUCache cache = new LRUCache<>(4); for(String key: Arrays.asList("A","B","C","A","D","E","F","E","F","G","A")){ Object object = cache.get(key); if(object==null){ object = hd.loadResource(key); cache.put(key, object); } cache.printSequence(); } } } 

Answer 11

这是java实现

 import java.util.HashMap; import java.util.Map; import com.nadeem.app.dsa.adt.Cache; // Kind of linkedHashMap public class LRUCache  implements Cache { private int capacity; private Node head, tail; private Map> map; private static final int DEFAULT_CAPACITY = 10; public LRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap>(); } public LRUCache() { this(DEFAULT_CAPACITY); } @Override public V get(K key) { V result = null; Node node = this.map.get(key); if (node != null) { result = node.value; remove(node); addAsHead(node); } return result; } @Override public void set(K key, V value) { Node node = this.map.get(key); if (node == null) { Node temp = new Node(key, value); if (this.map.size() < this.capacity) { addAsHead(temp); } else { this.map.remove(this.tail.key); remove(this.tail); addAsHead(temp); } this.map.put(key, temp); } else { node.value = value; remove(node); addAsHead(node); } } private void remove(Node node) { if (node.pre == null) { this.head = node.next; } else { node.pre.next = node.next; } if (node.next == null) { this.tail = node.pre; } else { node.next.pre = node.pre; } } private void addAsHead(Node node) { if (this.head == null) { this.head = node; this.tail = node; } else { this.head.pre = node; node.next = this.head; this.head = node; } } @Override public void remove(K key) { Node node = this.map.get(key); if (node != null) { this.remove(node); } } private static class Node  { public S key; public T value; Node pre; Node next; Node(S key, T value) { this.key = key; this.value = value; } } @Override public int size() { return this.map.size(); } 

}

这是unit testing

 public class LRUCacheTest { private LRUCache cache; @Before public void doBeforeEachTestCase() { this.cache = new LRUCache(2); } @Test public void setTest() { this.cache.set(1, 1); assertThat(this.cache.size(), equalTo(1)); assertThat(this.cache.get(1), equalTo(1)); this.cache.set(2, 2); assertThat(this.cache.size(), equalTo(2)); assertThat(this.cache.get(2), equalTo(2)); this.cache.set(3, 3); assertThat(this.cache.size(), equalTo(2)); assertThat(this.cache.get(3), equalTo(3)); this.cache.set(1, 3); assertThat(this.cache.size(), equalTo(2)); assertThat(this.cache.get(1), equalTo(3)); assertThat(this.cache.get(4), equalTo(null)); } 

}

Answer 12

 public class LeastRecentlyUsed { public static  Map leastRecentlyUsedCache(final int maxSize) { return new LinkedHashMap(maxSize , 0.7f, true) { private static final long serialVersionUID = -3588047435434569014L; @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } }; } public static void main(String[] args) { Map leastRecentlyUsed = LeastRecentlyUsed.leastRecentlyUsedCache(3); leastRecentlyUsed.put("Robert", "Raj"); leastRecentlyUsed.put("Auzi", "Aiz"); leastRecentlyUsed.put("Sandy", "S"); leastRecentlyUsed.put("Tript", "tty"); System.out.println(leastRecentlyUsed); } } 

Answer 13

正如K和其他人所说，这可以通过LinkedHashMap类来完成。 在挤压时，您可以获得15行代码的最小版本。

@Ciro Santilli ，为什么不削减额外的课程定义？ 如果使用的测试与其他java映射一样，那么我们就不必使用set方法对该方法进行别名，我们实际上希望从地图返回某种类型的set视图。

 import java.utils.LinkedHashMap import java.util.Map; public class LRUCache extends LinkedHashMap { private int maxSize; // and other constructors for load factor and hashtable capacity public LRUCache(int initialCapacity, float loadFactor, int maxSize) { super(initialCapacity, loadFactor, true); this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } // I don't like this. set should return a set put should put an item public V set(K key, V value) { put(key, value) } } 

请参阅此处和文档了解更多信息。