LRU算法，最近最少使用原则，如果要实现该算法，可以借助LinkedHashMap数据结构，LinkedHashMap继承HashMap，底层使用哈希表和双向链表来保存所有元素，使用LinkedHashMap可以确保元素按照顺序进行存储。
默认情况下，LinkedHashMap是按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方法，默认是返回false，即不删除数据。
下面就基于这两种存储方式，简单展示一下如何实现LRU算法：
一、基于按添加顺序存储的方式实现LRU：
代码语言：javascript复制public class LRUTest
{
int capacity;
LinkedHashMap<Integer, Integer> cache;
LRUTest(int capacity)
{
cache = new LinkedHashMap<>();
this.capacity = capacity;
}
//访问元素
public int get(int key)
{
if(!cache.containsKey(key))
{
return -1;
}
//存在，先从链表头部删除删除，在插入到链表尾部
int val = cache.get(key);
cache.remove(key);
cache.put(key, val);
return val;
}
//添加元素
public void put(int key, int val)
{
if(cache.containsKey(key))
{
cache.remove(key);
}
//如果链表已经满了，则删除头部节点
if(cache.size() == capacity)
{
Set<Integer> keySet = cache.keySet();
Iterator<Integer> iterator = keySet.iterator();
cache.remove(iterator.next());
}
cache.put(key, val);
}
}二、基于按访问顺序存储的方式实现LRU：
该方式的核心就是继承LinkedHashMap，并设置LinkedHashMap的accessOrder参数为true，然后重写LinkedHashMap的removeEldestEntry()方法。
代码语言：javascript复制public class LRUTest extends LinkedHashMap<String, String>
{
private int capacity;
/**
* 当LinkedHashMap的accessOrder参数为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
*/
public LRUTest(int capacity) {
super(16, 0.75f, true);
this.capacity = capacity;
}
/**
* LinkedHashMap自带的判断是否删除最老的元素方法，默认返回false，即不删除老数据
*/
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest)
{
return size() > capacity;
}
}测试方法：
代码语言：javascript复制 public static void main(String[] args)
{
Map<String, String> linkedHashMap = new LRUTest(6);
linkedHashMap.put("1", "1");
linkedHashMap.put("2", "2");
linkedHashMap.put("3", "3");
linkedHashMap.put("4", "4");
linkedHashMap.put("5", "5");
linkedHashMap.put("6", "6");
linkedHashMap.put("7", "7");
linkedHashMap.put("8", "8");
linkedHashMap.put("9", "9");
System.out.println("size=" linkedHashMap.size());
System.out.println(linkedHashMap.get("8"));
linkedHashMap.forEach((k,v) ->{
System.out.print(k ":" v " ");
});
System.out.println();
System.out.println("size=" linkedHashMap.size());
}输出结果：
代码语言：javascript复制size=6
8
4:4 5:5 6:6 7:7 9:9 8:8
size=6发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/100026.html原文链接：https://javaforall.cn
