Java 使用 LinkedHashMap 实现 LRU 缓存
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/27475797/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Use LinkedHashMap to implement LRU cache
提问by Lei Chen
I was trying to implement a LRU cache using LinkedHashMap. In the documentation of LinkedHashMap (http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html), it says:
我试图使用 LinkedHashMap 实现 LRU 缓存。在 LinkedHashMap ( http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html)的文档中，它说：
Note that insertion order is not affected if a key is re-inserted into the map.
请注意，如果将键重新插入到映射中，则插入顺序不会受到影响。
But when I do the following puts
但是当我执行以下操作时
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int size;
public static void main(String[] args) {
LRUCache<Integer, Integer> 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<K, V> eldest) {
return size() > size;
}
public static <K, V> LRUCache<K, V> newInstance(int size) {
return new LRUCache<K, V>(size);
}
}
The output is
输出是
{1=1, 3=3}
Which indicates that the re-inserted did affected the order. Does anybody know any explanation?
这表明重新插入确实影响了订单。有人知道任何解释吗？
采纳答案by 1736964698
As pointed out by Jeffrey, you are using accessOrder. When you created the LinkedHashMap, the third parameter specify how the order is changed.
正如 Jeffrey 所指出的，您正在使用 accessOrder。当您创建 LinkedHashMap 时，第三个参数指定如何更改顺序。
"true for access-order, false for insertion-order"
For more detailed implementation of LRU, you can look at this http://www.programcreek.com/2013/03/leetcode-lru-cache-java/
LRU更详细的实现可以看这个 http://www.programcreek.com/2013/03/leetcode-lru-cache-java/
回答by Jeffrey
But you aren't using insertion order, you're using access order.
但是您没有使用插入顺序，而是使用访问顺序。
order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order)
迭代顺序是其条目上次访问的顺序，从最近最少访问到最近访问（访问顺序）
...
...
Invoking the put or get method results in an access to the corresponding entry
调用 put 或 get 方法会导致访问相应的条目
So this is the state of your cache as you modify it:
所以这是您修改缓存时的状态：
LRUCache<Integer, Integer> 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 }
回答by Emilio Zhao
Here is my implementation by using LinkedHashMap in AccessOrder. It will move the latest accessed element to the front which only incurs O(1) overhead because the underlying elements are organized in a doubly-linked list while also are indexed by hash function. So the get/put/top_newest_one operations all cost O(1).
这是我在 AccessOrder 中使用 LinkedHashMap 的实现。它将最新访问的元素移到前面，这只会产生 O(1) 开销，因为底层元素组织在双向链表中，同时也由哈希函数索引。所以 get/put/top_newest_one 操作的成本都是 O(1)。
class LRUCache extends LinkedHashMap<Integer, Integer>{
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<Integer, Integer> eldest) {
return this.size() > maxSize; //must override it if used in a fixed cache
}
}
回答by Rajeev Rathor
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<String, String> 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<K, T>{
private Map<K,T> cache;
private int windowSize;
public LRUCache( final int windowSize) {
this.windowSize = windowSize;
this.cache = new LinkedHashMap<K, T>(){
@Override
protected boolean removeEldestEntry(Map.Entry<K, T> 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 +
'}';
}
}
回答by Shrey Suri
I used the following code and its works!!!! I have taken window size to be 4, but any value can be taken.
我使用了以下代码及其工作原理！！！！我已将窗口大小设为 4，但可以采用任何值。
for Insertion order:
1: Check if the key is present.
对于插入订单：
1：检查密钥是否存在。
2: If yes, then remove it (by using lhm.remove(key))
2：如果是，则将其删除（通过使用 lhm.remove(key)）
3: Add the new Key Value pair.
3：添加新的键值对。
for Access Order:
对于访问顺序：
No need of removing keys only put and get statements do everything automatically.
无需删除键，只需 put 和 get 语句自动完成所有操作。
This code is for ACCESS ORDER:
此代码用于访问订单：
import java.util.LinkedHashMap;
public class LRUCacheDemo {
public static void main(String args[]){
LinkedHashMap<String,String> lhm = new LinkedHashMap<String,String>(4,0.75f,true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String,String> eldest) {
return size() > 4;
}
};
lhm.put("test", "test");
lhm.put("test1", "test1");
lhm.put("1", "abc");
lhm.put("test2", "test2");
lhm.put("1", "abc");
lhm.put("test3", "test3");
lhm.put("test4", "test4");
lhm.put("test3", "test3");
lhm.put("1", "abc");
lhm.put("test1", "test1");
System.out.println(lhm);
}
}
