LinkedHashMap实现LRU缓存算法

缓存这个东西就是为了提高运行速度的，由于缓存是在寸土寸金的内存里面，不是在硬盘里面，所以容量是很有限的。LRU这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。先说说List：每次访问一个元素后把这个元素放在 List一端，这样一来最远使用的元素自然就被放到List的另一端。缓存满了t的时候就把那最远使用的元素remove掉。但更实用的是HashMap。因为List太慢，要删掉的数据总是位于List底层数组的第一个位置，删掉之后，后面的数据要向前补位。。所以复杂度是O(n)，那就用链表结构的LinkedHashMap呗~，LinkedHashMap默认的元素顺序是put的顺序，但是如果使用带参数的构造函数，那么LinkedHashMap会根据访问顺序来调整内部顺序。 LinkedHashMap的get()方法除了返回元素之外还可以把被访问的元素放到链表的底端，这样一来每次顶端的元素就是remove的元素。

构造函数如下：

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

initialCapacity 初始容量

loadFactor 加载因子，一般是 0.75f

accessOrder false 基于插入顺序 true 基于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU 最近最少被使用的调度算法）

来个例子吧：

[java] view plain copy

import java.util.*;
class Test
{
public static void main(String[] args) throws Exception{
Map<Integer,Integer> map=new LinkedHashMap<Integer,Integer>(10,0.75f,true);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
//现在遍历的话顺序肯定是9,7,5,3
//下面访问了一下9,3这个键值对，输出顺序就变喽~
map.get(9);
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}

输出7
5
3
9好玩吧~
（上面部分为转载 http://blog.csdn.net/yangpl_tale/article/details/44998365）
下面开始实现LRU缓存喽~

import java.util.*;
import java.util.Map.Entry;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

//扩展一下LinkedHashMap这个类，让他实现LRU算法  
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private static final long serialVersionUID = -3791412708654730531L;
// 定义缓存的容量
private int capacity;
// 多线程
private Lock lock;

// 带参数的构造器
LRULinkedHashMap(int capacity) {
// 调用LinkedHashMap的构造器，传入以下参数
super(16, 0.75f, true);
// 传入指定的缓存最大容量
this.capacity = capacity;
lock = new ReentrantLock();
}

// 实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}

@Override
public V get(Object k) {
V v;
lock.lock();
v = super.get(k);
lock.unlock();
return v;
}

@Override
public V put(K key, V value) {
V v;
lock.lock();
v = super.put(key, value);
lock.unlock();
return v;
}

@Override
public V remove(Object key) {
V v;
lock.lock();
v = super.remove(key);
lock.unlock();
return v;
}

public List<V> getValues() {
ArrayList<V> arraylist;
lock.lock();
ArrayList<V> list = new ArrayList<V>();
list.addAll(super.values());
arraylist = list;
lock.unlock();
return arraylist;
}

// 测试
static LRULinkedHashMap<Integer, Integer> map = new LRULinkedHashMap<>(5);

public static void main(String[] args) {
map.put(1, 10);
map.put(2, 20);
map.put(3, 30);
map.put(4, 40);
map.put(5, 50);
map.get(1);
map.put(6, 60);

for (Iterator<Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) {
Entry<Integer, Integer> a = it.next();
System.out.println(a.getKey() + " = " + a.getValue());
}
}
}

3 = 30
4 = 40
5 = 50
1 = 10
6 = 60

在put 1 - 5 的时候应该输出1-5的值，但是get(1)操作会将1放到最后，顺序变成23451 。而put(6,60)的时候超过了容量上限，因此，会删除第一个元素2

秒客网

LinkedHashMap实现LRU缓存算法

相关文章