1、lru简介
LRU是Least Recently Used的缩写,即最近最少使用,常用于页面置换算法,是为虚拟页式存储管理服务的。
即当一个数据最近一段时间没有被访问,未来被访问的概率也很小。当空间被占满后,最先淘汰最近最少使用的数据。
2、java简单实现
/**
* @Title: LRU.java
* @Package com.spring.pro.lru
* @Description:
* @author ybwei
* @date 2018年11月6日 下午2:39:15
* @version V1.0
*/
public class LRU<K, V> {
/**
* LinkedHashMap负载因子默认0.75
*/
private static final float hashLoadFactory = 0.75f;
private LinkedHashMap<K, V> map;
private int cacheSize;
/**
* @param cacheSize 容量
*/
public LRU(int cacheSize) {
this.cacheSize = cacheSize;
int capacity = (int) Math.ceil(cacheSize / hashLoadFactory) + 1;
map = new LinkedHashMap<K, V>(capacity, hashLoadFactory, true) {
private static final long serialVersionUID = -5291175172111746517L;
/*
* 当map容量大于LRU的容量时,删除最近最少使用的数据
*/
@Override
protected boolean removeEldestEntry(Entry<K, V> eldest) {
return size() > LRU.this.cacheSize;
}
};
}
public synchronized V get(K key) {
return map.get(key);
}
public synchronized void put(K key, V value) {
map.put(key, value);
}
public synchronized void clear() {
map.clear();
}
public synchronized int usedSize() {
return map.size();
}
public void print() {
for (Map.Entry<K, V> entry : map.entrySet()) {
System.out.print(entry.getValue() + "--");
}
System.out.println();
}
}
HashMap的一个实例有两个影响其性能的参数: 初始容量和负载因子 。 容量是哈希表中的桶数,初始容量只是创建哈希表时的容量。 负载因子是在容量自动增加之前允许哈希表得到满足的度量。 当在散列表中的条目的数量超过了负载因数和电流容量的乘积,哈希表被重新散列 (即,内部数据结构被重建),使得哈希表具有桶的大约两倍。
作为一般规则,默认负载因子(.75)提供了时间和空间成本之间的良好折中。 更高的值会降低空间开销,但会增加查找成本(反映在HashMap类的大部分操作中,包括get和put )。 在设置其初始容量时,应考虑地图中预期的条目数及其负载因子,以便最小化重新组播操作的数量。 如果初始容量大于最大条目数除以负载因子,则不会发生重新排列操作。
3、测试
/**
* @Title: LRUTest.java
* @Package com.spring.pro.lru.test
* @Description:
* @author ybwei
* @date 2018年11月6日 下午4:39:03
* @version V1.0
*/
public class LRUTest {
/**
*
* @author ybwei
*/
@Test
public void LruTest() {
LRU<String,Integer> lru=new LRU<>(3);
for(int i=0;i<50;i++) {
lru.put("aa"+i, i);
lru.print();
}
}
}