Используйте LinkedHashMap для реализации кэша LRU
Я пытался реализовать кэш LRU с помощью LinkedHashMap. В документации LinkedHashMap ( http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html) говорится:
Обратите внимание, что порядок вставки не изменяется, если ключ повторно вставлен в карту.
Но когда я делаю следующее ставит
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);
}
}
Выход
{1=1, 3=3}
Что указывает на то, что повторная вставка повлияла на порядок. Кто-нибудь знает какие-либо объяснения?
6 ответов
Как отметил Джеффри, вы используете accessOrder. Когда вы создали LinkedHashMap, третий параметр указывает, как изменяется порядок.
"true for access-order, false for insertion-order"
Для более подробной реализации LRU, вы можете посмотреть на этом http://www.programcreek.com/2013/03/leetcode-lru-cache-java/
Но вы не используете порядок вставки, вы используете порядок доступа.
порядок итерации - это порядок, в котором к последним элементам обращались к ним: от наименее недавнего доступа к последнему (порядок доступа)
...
Вызов метода put или get приводит к доступу к соответствующей записи
Итак, это состояние вашего кэша, когда вы его модифицируете:
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 }
Вот моя реализация с использованием LinkedHashMap в AccessOrder. Он переместит последний элемент, к которому был получен доступ, вперед, что приводит к накладным расходам 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
}
}
Технически LinkedHashMap имеет следующий конструктор. Которые помогают нам сделать порядок доступа True/False. Если оно ложно, то он сохраняет порядок вставки.
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
(#Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode)
Ниже приведена простая реализация LRU Cache ---
class LRUCache {
private LinkedHashMap<Integer, Integer> linkHashMap;
public LRUCache(int capacity) {
linkHashMap = new LinkedHashMap<Integer, Integer>(capacity, 0.75F, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
};
}
public void put(int key, int value) {
linkHashMap.put(key, value);
}
public int get(int key) {
return linkHashMap.getOrDefault(key, -1);
}
}
Я использовал следующий код и его работы!!!! Я принял размер окна равным 4, но можно принять любое значение.
для порядка вставки:
1: Проверьте, присутствует ли ключ.
2: если да, то удалите его (используя lhm.remove(ключ))
3: Добавьте новую пару Key Value.
для заказа доступа:
Не нужно удалять ключи, только положить и получить операторы делают все автоматически.
Этот код для ЗАКАЗА ДОСТУПА:
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);
}
}
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 +
'}';
}
}