使用LinkedHashMap实现LRU缓存

我试图使用LinkedHashMap实现LRU缓存。 在LinkedHashMap（ http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html ）的文档中，它说：

请注意，如果将键重新插入地图，则不会影响插入顺序。

但是当我做下面的提示

public class LRUCache extends LinkedHashMap { private int size; public static void main(String[] args) { LRUCache cache = LRUCache.newInstance(2); cache.put(1, 1); cache.put(2, 2); cache.put(1, 1); cache.put(3, 3); System.out.println(cache); } private LRUCache(int size) { super(size, 0.75f, true); this.size = size; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > size; } public static  LRUCache newInstance(int size) { return new LRUCache(size); } } 

输出是

 {1=1, 3=3} 

这表明重新插入确实影响了订单。 有人知道任何解释吗？

Answer 1

正如Jeffrey指出的那样 ，您正在使用accessOrder。 创建LinkedHashMap时，第三个参数指定顺序的更改方式。

 "true for access-order, false for insertion-order" 

有关LRU的更详细实现，您可以查看http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

Answer 2

但是您没有使用广告订单，而是使用了访问顺序 。

迭代次序是上次访问其条目的顺序，从最近访问到最近访问（访问顺序）

…

调用put或get方法会导致访问相应的条目

因此，当您修改缓存时，这是缓存的状态：

  LRUCache cache = LRUCache.newInstance(2); cache.put(1, 1); // { 1=1 } cache.put(2, 2); // { 1=1, 2=2 } cache.put(1, 1); // { 2=2, 1=1 } cache.put(3, 3); // { 1=1, 3=3 } 

Answer 3

这是我在AccessOrder中使用LinkedHashMap的实现。 它会将最新访问的元素移动到前面，这只会产生O（1）开销，因为底层元素被组织在一个双向链表中，同时也被哈希函数索引。 因此get / put / top_newest_one操作都需要花费O（1）。

 class LRUCache extends LinkedHashMap{ private int maxSize; public LRUCache(int capacity) { super(capacity, 0.75f, true); this.maxSize = capacity; } //return -1 if miss public int get(int key) { Integer v = super.get(key); return v == null ? -1 : v; } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return this.size() > maxSize; //must override it if used in a fixed cache } } 

Answer 4

 I also implement LRU cache with little change in code. I have tested and it works perfectly as concept of LRU cache. package com.first.misc; import java.util.LinkedHashMap; import java.util.Map; public class LRUCachDemo { public static void main(String aa[]){ LRUCache lruCache = new LRUCache<>(3); lruCache.cacheable("test", "test"); lruCache.cacheable("test1", "test1"); lruCache.cacheable("test2", "test2"); lruCache.cacheable("test3", "test3"); lruCache.cacheable("test4", "test4"); lruCache.cacheable("test", "test"); System.out.println(lruCache.toString()); } } class LRUCache{ private Map cache; private int windowSize; public LRUCache( final int windowSize) { this.windowSize = windowSize; this.cache = new LinkedHashMap(){ @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > windowSize; } }; } // put data in cache public void cacheable(K key, T data){ // check key is exist of not if exist than remove and again add to make it recently used // remove element if window size is exhaust if(cache.containsKey(key)){ cache.remove(key); } cache.put(key,data); } // evict functioanlity @Override public String toString() { return "LRUCache{" + "cache=" + cache.toString() + ", windowSize=" + windowSize + '}'; } }