用map实现LRU算法（LinkedHashMap）

2025-06-06 01:59:56 • 06世界杯意大利

LinkedHashMap是把HashMap和双向链表合二为一，它将所有entry节点放入一个双向链表的hashmap，其内部维持的顺序是元素插入的顺序，而且能实现lru算法。

下面是get方法的定义：

public V get(Object key) {

Entry e = (Entry)getEntry(key);

if (e == null)

return null;

e.recordAccess(this);

return e.value;

}

其中recordAccess定义如下：

void recordAccess(HashMap m) {

LinkedHashMap lm = (LinkedHashMap)m;

if (lm.accessOrder) {

lm.modCount++;

remove();

addBefore(lm.header);

}

}

这里的addBefore方法：

private void addBefore(Entry existingEntry) {

after = existingEntry;

before = existingEntry.before;

before.after = this;

after.before = this;

}

可以看到addBefore方法中，是把当前访问的元素挪到了head的前面，即放到了链表头，如此要实现lru只需要从链表末尾往前删除就可以了。注意在初始化LinkedHashMap的时候，会传入一个accessOrder属性，如果为true，则代表entry是按照访问顺序排序的，如果为false，则代表是按照插入顺序排序的，即在put的时候，entry会放在双向链表的尾部。put方法也会调用addBefore()

put顺序：

LinkedHashMap map = new LinkedHashMap<>();map.put("星期一", 40);map.put("星期二", 43);map.put("星期三", 35);map.put("星期四", 55);map.put("星期五", 45);map.put("星期六", 35);map.put("星期日", 30);for (Map.Entry entry : map.entrySet()){ System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());}

结果：

key: 星期一, value: 40key: 星期二, value: 43key: 星期三, value: 35key: 星期四, value: 55key: 星期五, value: 45key: 星期六, value: 35key: 星期日, value: 30

花熊APP制作表情的操作过程
三元的解释