LinkedHashMap

https://www.bilibili.com/video/BV1JP411379g

package java.util;
……
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
……
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
}

结点左边的“b”是 before 的意思，是指向前驱的引用类型变量；

结点右边的“a”是 after 的意思，是指向后继的引用类型变量；

next 则是按照 hashcode 取模之后存储元素的hash槽的位置；

测试元素添加和取出的顺序

package io.github.jihch;

import java.util.LinkedHashMap;

public class LinkedHashMapTest {

    public static void main(String[] args) {
        //创建水果集合
        LinkedHashMap<String, String> fruits = new LinkedHashMap<>();
        //添加水果
        fruits.put("apple", "苹果");
        fruits.put("banana", "香蕉");
        fruits.put("pear", "梨子");
        fruits.put("grape", "葡萄");
        fruits.put("lemon", "柠檬");
        fruits.forEach((k, v) -> {
            System.out.printf("key:%s,value:%s\n", k, v);
        });
    }

}

key:apple,value:苹果
key:banana,value:香蕉
key:pear,value:梨子
key:grape,value:葡萄
key:lemon,value:柠檬

可以发现，元素添加的顺序和取出的顺序一致

测试元素访问的顺序

被访问过的元素排在最后，这里的“被访问过”指的是通过

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

方法获取过；

举个例子，

添加顺序：<"apple","苹果">，<"banana","香蕉">，<"pear","梨子">，<"grape","葡萄">，<"lemon","柠檬">

如果此时访问：<"apple","苹果">

则取出时顺序：<"banana","香蕉">，<"pear","梨子">，<"grape","葡萄">，<"lemon","柠檬">，<"apple","苹果">

import java.util.LinkedHashMap;

public class LinkedHashMapTest {

    public static void main(String[] args) {
        //创建水果集合
        LinkedHashMap<String, String> fruits = new LinkedHashMap<>(16, 0.75f, true);
        //添加水果
        fruits.put("apple", "苹果");
        fruits.put("banana", "香蕉");
        fruits.put("pear", "梨子");
        fruits.put("grape", "葡萄");
        fruits.put("lemon", "柠檬");

        System.out.println("访问前：");
        fruits.forEach((k, v) -> {
            System.out.printf("key:%s,value:%s\n", k, v);
        });

        fruits.get("apple");

        System.out.println("访问后：");
        fruits.forEach((k, v) -> {
            System.out.printf("key:%s,value:%s\n", k, v);
        });
    }

}

访问前：
key:apple,value:苹果
key:banana,value:香蕉
key:pear,value:梨子
key:grape,value:葡萄
key:lemon,value:柠檬
访问后：
key:banana,value:香蕉
key:pear,value:梨子
key:grape,value:葡萄
key:lemon,value:柠檬
key:apple,value:苹果

LinkedHashMap 实现 LRU

LRU.java

import java.util.LinkedHashMap;
import java.util.Map;

public class LRU<K, V> {

    private static final float loadFactor = 0.75f;
    private LinkedHashMap<K, V> map;
    private int cacheSize;

    public LRU(int cacheSize) {
        this.cacheSize = cacheSize;
        int capacity = (int)Math.ceil(cacheSize/loadFactor)+1;
        map = new LinkedHashMap<K, V> (capacity, loadFactor, true)
        {
            private static final long serialVersionUID = 1L;

            @Override
            protected boolean removeEldestEntry(Map.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 String toString() {
        StringBuffer sb = new StringBuffer("");
        for (Map.Entry<K, V> entry:map.entrySet())
        {
            sb.append(entry.getValue()+"->");
        }
        return sb.toString();
    }

}

LRUTest.java

public class LRUTest {

    public static void main(String[] args) {
        LRU<Integer, Integer> lru = new LRU<>(5);
        for(int i = 0; i <5; i++) {
            lru.put(i, i);
        }
        System.out.println(lru);
        lru.get(3);
        System.out.println(lru);
        lru.put(5, 5);
        System.out.println(lru);
    }

}

关键点有两处：

一个是调用 LinkedHashMap 构造传参时给 accessOrder 传值为 true；LinkedHashMap 的有4个构造方法，其中3个构造方法都指定了 accessOrder 的值为 false，表示遍历元素的顺序会和 put 元素的顺序一致；还有一个构造方法接收 accessOrder 传参，accessOrder 值为 true 时，每一次通过 get 方法访问过的元素会放到在遍历元素顺序的末尾；

利用 LinkedHashMap 实现 LRU 的核心是重写 removeEldestEntry 方法，当容量到达上限时，LinkedHashMap 开始按照遍历顺序移除元素，在 accessOrder 为 true 时，队列前面的元素都是相对最近没有 get 过的，就被移除了，而队尾的则都是通过 get 方法访问过的