使用LinkedHashMap实现LRU算法

LRU算法，最近最少使用原则，如果要实现该算法，可以借助LinkedHashMap数据结构，LinkedHashMap继承HashMap，底层使用哈希表和双向链表来保存所有元素，使用LinkedHashMap可以确保元素按照顺序进行存储。

默认情况下，LinkedHashMap是按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方法，默认是返回false，即不删除数据。

下面就基于这两种存储方式，简单展示一下如何实现LRU算法：

一、基于按添加顺序存储的方式实现LRU：

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()方法。

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;
}
}

测试方法：

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());
}

输出结果：

size=6
8
4:4
5:5
6:6
7:7
9:9
8:8
size=6

最后

以上就是笑点低自行车为你收集整理的使用LinkedHashMap实现LRU算法的全部内容，希望文章能够帮你解决使用LinkedHashMap实现LRU算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。