首页 > 代码库 > LinkedHashMap 和 LRU算法实现
LinkedHashMap 和 LRU算法实现
个人觉得LinkedHashMap 存在的意义就是为了实现 LRU 算法。
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } ....
1、LinkedHashMap 的 <K,V>用HashMap存储。
2、LinkedHashMap 的Key 用双向链表维护。
当用get 和 set 方法的时候，内部维护key的双向链表的结构顺序会变动。
3、accessOrder：false 基于插入顺序 true 基于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU 最近最少被使用的调度算法）。
4、removeEldestEntry方法，考虑清楚是否要重载。如果最大容量固定，则需要重载，否则表现为自适应。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
最简单的LRU算法实现
update1:第二个实现，读操作不必要采用独占锁，缓存显然是读多于写，读的时候一开始用独占锁是考虑到要递增计数和更新时间戳要加锁，不过这两个变量都是采用原子变量，因此也不必采用独占锁，修改为读写锁。
update2:一个错误，老是写错关键字啊，LRUCache的maxCapacity应该声明为volatile，而不是transient。
最简单的LRU算法实现，就是利用jdk的LinkedHashMap，覆写其中的removeEldestEntry(Map.Entry)方法即可，如下所示：
import java.util.ArrayList;import java.util.Collection;import java.util.LinkedHashMap;import java.util.concurrent.locks.Lock;import java.util.concurrent.locks.ReentrantLock;import java.util.Map;/** * 类说明：利用LinkedHashMap实现简单的缓存， 必须实现removeEldestEntry方法，具体参见JDK文档 * * @author dennis * * @param <K> * @param <V> */public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> { private final int maxCapacity; private static final float DEFAULT_LOAD_FACTOR = 0.75f; private final Lock lock = new ReentrantLock(); public LRULinkedHashMap(int maxCapacity) { super(maxCapacity, DEFAULT_LOAD_FACTOR, true); this.maxCapacity = maxCapacity; } @Override protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) { return size() > maxCapacity; } @Override public boolean containsKey(Object key) { try { lock.lock(); return super.containsKey(key); } finally { lock.unlock(); } } @Override public V get(Object key) { try { lock.lock(); return super.get(key); } finally { lock.unlock(); } } @Override public V put(K key, V value) { try { lock.lock(); return super.put(key, value); } finally { lock.unlock(); } } public int size() { try { lock.lock(); return super.size(); } finally { lock.unlock(); } } public void clear() { try { lock.lock(); super.clear(); } finally { lock.unlock(); } } public Collection<Map.Entry<K, V>> getAll() { try { lock.lock(); return new ArrayList<Map.Entry<K, V>>(super.entrySet()); } finally { lock.unlock(); } }}
如果你去看LinkedHashMap的源码可知，LRU算法是通过双向链表来实现，当某个位置被命中，通过调整链表的指向将该位置调整到头位置，新加入的内容直接放在链表头，如此一来，最近被命中的内容就向链表头移动，需要替换时，链表最后的位置就是最近最少使用的位置。
LRU算法还可以通过计数来实现，缓存存储的位置附带一个计数器，当命中时将计数器加1，替换时就查找计数最小的位置并替换，结合访问时间戳来实现。这种算法比较适合缓存数据量较小的场景，显然，遍历查找计数最小位置的时间复杂度为O(n)。我实现了一个，结合了访问时间戳，当最小计数大于MINI_ACESS时(这个参数的调整对命中率有较大影响），就移除最久没有被访问的项：
package net.rubyeye.codelib.util.concurrency.cache;import java.io.Serializable;import java.util.ArrayList;import java.util.Collection;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.Set;import java.util.concurrent.atomic.AtomicInteger;import java.util.concurrent.atomic.AtomicLong;import java.util.concurrent.locks.Lock;import java.util.concurrent.locks.ReadWriteLock;import java.util.concurrent.locks.ReentrantLock;import java.util.concurrent.locks.ReentrantReadWriteLock;/** * * @author dennis 类说明：当缓存数目不多时，才用缓存计数的传统LRU算法 * @param <K> * @param <V> */public class LRUCache<K, V> implements Serializable { private static final int DEFAULT_CAPACITY = 100; protected Map<K, ValueEntry> map; private final ReadWriteLock lock = new ReentrantReadWriteLock(); private final Lock readLock = lock.readLock(); private final Lock writeLock = lock.writeLock(); private final volatile int maxCapacity; //保持可见性 public static int MINI_ACCESS = 5; public LRUCache() { this(DEFAULT_CAPACITY); } public LRUCache(int capacity) { if (capacity <= 0) throw new RuntimeException("缓存容量不得小于0"); this.maxCapacity = capacity; this.map = new HashMap<K, ValueEntry>(maxCapacity); } public boolean ContainsKey(K key) { try { readLock.lock(); return this.map.containsKey(key); } finally { readLock.unlock(); } } public V put(K key, V value) { try { writeLock.lock(); if ((map.size() > maxCapacity - 1) && !map.containsKey(key)) { // System.out.println("开始"); Set<Map.Entry<K, ValueEntry>> entries = this.map.entrySet(); removeRencentlyLeastAccess(entries); } ValueEntry new_value = new ValueEntry(value); ValueEntry old_value = map.put(key, new_value); if (old_value != null) { new_value.count = old_value.count; return old_value.value; } else return null; } finally { writeLock.unlock(); } } /** * 移除最近最少访问 */ protected void removeRencentlyLeastAccess( Set<Map.Entry<K, ValueEntry>> entries) { // 最小使用次数 long least = 0; // 访问时间最早 long earliest = 0; K toBeRemovedByCount = null; K toBeRemovedByTime = null; Iterator<Map.Entry<K, ValueEntry>> it = entries.iterator(); if (it.hasNext()) { Map.Entry<K, ValueEntry> valueEntry = it.next(); least = valueEntry.getValue().count.get(); toBeRemovedByCount = valueEntry.getKey(); earliest = valueEntry.getValue().lastAccess.get(); toBeRemovedByTime = valueEntry.getKey(); } while (it.hasNext()) { Map.Entry<K, ValueEntry> valueEntry = it.next(); if (valueEntry.getValue().count.get() < least) { least = valueEntry.getValue().count.get(); toBeRemovedByCount = valueEntry.getKey(); } if (valueEntry.getValue().lastAccess.get() < earliest) { earliest = valueEntry.getValue().count.get(); toBeRemovedByTime = valueEntry.getKey(); } } // System.out.println("remove:" + toBeRemoved); // 如果最少使用次数大于MINI_ACCESS，那么移除访问时间最早的项(也就是最久没有被访问的项） if (least > MINI_ACCESS) { map.remove(toBeRemovedByTime); } else { map.remove(toBeRemovedByCount); } } public V get(K key) { try { readLock.lock(); V value = null; ValueEntry valueEntry = map.get(key); if (valueEntry != null) { // 更新访问时间戳 valueEntry.updateLastAccess(); // 更新访问次数 valueEntry.count.incrementAndGet(); value = valueEntry.value; } return value; } finally { readLock.unlock(); } } public void clear() { try { writeLock.lock(); map.clear(); } finally { writeLock.unlock(); } } public int size() { try { readLock.lock(); return map.size(); } finally { readLock.unlock(); } } public long getCount(K key) { try { readLock.lock(); ValueEntry valueEntry = map.get(key); if (valueEntry != null) { return valueEntry.count.get(); } return 0; } finally { readLock.unlock(); } } public Collection<Map.Entry<K, V>> getAll() { try { readLock.lock(); Set<K> keys = map.keySet(); Map<K, V> tmp = new HashMap<K, V>(); for (K key : keys) { tmp.put(key, map.get(key).value); } return new ArrayList<Map.Entry<K, V>>(tmp.entrySet()); } finally { readLock.unlock(); } } class ValueEntry implements Serializable { private V value; private AtomicLong count; private AtomicLong lastAccess; public ValueEntry(V value) { this.value =http://www.mamicode.com/ value; this.count = new AtomicLong(0); lastAccess = new AtomicLong(System.nanoTime()); } public void updateLastAccess() { this.lastAccess.set(System.nanoTime()); } }}
参考：
简单LRU算法实现缓存-update2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。