手写实现简化版LRU

通过LinkedHashMap实现简化版LRU算法

LinkedHashMap提供了很好的方法，便于我们快速实现一个LRU算法。实现的方式以及 原理在代码中通过注释都已经给出。

package LRU;

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

/**
 * 手写LRU
 *
 * @author
 * @date 2020.4.4
 */
public class LruTest {

    public static void main(String[] args) {

        MyLRU<String, String> myLRU = new MyLRU<>(5, 0.75f);
        // 这里传入的是5，最后通过计算，hash table的数组长度应该是8
        // hashMap中的put源码
        //    ---->
        //         if (++size > threshold)
        //            // 当本次执行put后table中结点的个数大于阈值时扩容(当前阈值为 8*0.75 = 6)
        //            resize();
        //        // 删除头结点
        //        afterNodeInsertion(evict);

        myLRU.put("1", "1");
        myLRU.put("2", "2");
        myLRU.put("3", "3");
        myLRU.put("4", "4");
        myLRU.put("5", "5");
        myLRU.forEach((k, v) -> System.out.println(k + ":" + v));
        //     @Override
        //    protected boolean removeEldestEntry(Map.Entry eldest) {
        //        // 当 执行put后，hash table中结点的总数大于LRUSize的时候，自动删除 头结点
        //        return size() > LRUSize;
        //    }
        myLRU.put("6", "6");
        // 本例子中 当添加完第6个结点时应该删除 第1个结点
        System.out.println("============================");
        myLRU.forEach((k, v) -> System.out.println(k + ":" + v));
        // 当执行更新已存在的结点时，该节点会成为尾结点。->afterNodeAccess(e);
        //      HashMap.putval源码->
        //             if (e != null) { // existing mapping for key
        //                V oldValue = e.value;
        //                if (!onlyIfAbsent || oldValue == null)
        //                    e.value = value;
        //                afterNodeAccess(e);
        //                return oldValue;
        //            }
        myLRU.put("4", "1");
        System.out.println("============================");
        myLRU.forEach((k, v) -> System.out.println(k + ":" + v));
    }
}

/**
 * 自定义LRU实现
 * @param <K>
 * @param <V>
 */
class MyLRU<K, V> extends LinkedHashMap<K, V> {

    private final int LRUSize;
    private float loadFactor = 0.75f;

    /**
     * @param initialCapacity 希望存取的元素大小
     * @param loadFactor 负载因子，传0.75即可
     */
    public MyLRU(int initialCapacity, float loadFactor) {
        // initialCapacity/loadFactor + 1 这个计算公式，可以参考 阿里编码规约初始化容量
        // 作用就是：避免扩容
        super((int) (initialCapacity/loadFactor + 1), loadFactor, true);
        this.loadFactor = loadFactor;
        this.LRUSize = initialCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        // 当 put时，新增的个数大于LRUSize的时候，自动删除 头结点
        return size() > LRUSize;
    }

    /**
     * 当执行put结点后，并且执行完++size，会调用下面这个方法。可以看到会调用
     * removeEldestEntry(first) 来删除头结点
     */
//    void afterNodeInsertion(boolean evict) { // possibly remove eldest
//        LinkedHashMap.Entry<K,V> first;
//        if (evict && (first = head) != null && removeEldestEntry(first)) {
//            K key = first.key;
//            removeNode(hash(key), key, null, false, true);
//        }
//    }
}

执行结果：
1:1
2:2
3:3
4:4
5:5
============================
2:2
3:3
4:4
5:5
6:6
============================
2:2
3:3
5:5
6:6
4:1