从LRU 说到 LinkedHashMap

最前面的解释

LRU

漫画：什么是LRU算法？
LRU是一种页面置换算法,Least recently used，最近最少使用;
根据数据的历史访问记录来进行淘汰数据，缓存不够时，最近最少使用元素被删除;
核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

对立的，有LFU

如何动手撸一个简单的LFU缓存

LinkedHashMap简述

图解LinkedHashMap原理

笔记

LinkedHashMap是有序的，且默认为插入顺序,底层是HashMap+双向链表

//空参的构造方法
    public LinkedHashMap() {
        // 调用HashMap的构造方法，其实就是初始化Entry[] table
        super();
        // 这里是指是否基于访问排序，默认为false
        accessOrder = false;
    }

accessOrder = false，这就跟存储的顺序有关了，LinkedHashMap存储数据是有序的，而且分为两种：插入顺序（默认缺省状态，accessOrder = false）和访问顺序（accessOrder = true）

其实这里就已经感受到了，和LRU的共同点 访问顺序排序

LinkedHashMap没有重写put方法，所以还是调用HashMap得到put方法;

LinkedHashMap有自己的静态内部类Entry，它继承了HashMap.Entry

  /**
      * LinkedHashMap entry.
      */
  private static class Entry<K,V> extends HashMap.Entry<K,V> {
      // These fields comprise the doubly linked list used for iteration.
      Entry<K,V> before, after;

      Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
          super(hash, key, value, next);
      }

LinkedHashMap构造函数，主要就是调用HashMap构造函数初始化了一个Entry[] table，然后调用自身的init初始化了一个只有头结点的双向链表
LinkedHashMap重写了transfer方法，数据的迁移；

LinkedHashMap扩容时，数据的再散列和HashMap是不一样的。

HashMap是先遍历旧table，再遍历旧table中每个元素的单向链表，取得Entry以后，重新计算hash值，然后存放到新table的对应位置。

LinkedHashMap是遍历的双向链表，取得每一个Entry，然后重新计算hash值，然后存放到新table的对应位置。

从遍历的效率来说，遍历双向链表的效率要高于遍历table，因为遍历双向链表是N次（N为元素个数）；而遍历table是N+table的空余个数（N为元素个数）。
在LinkedHashMap中，只有accessOrder为true，即是访问顺序模式，才会put时对更新的Entry进行重新排序，而如果是插入顺序模式时，不会重新排序，这里的排序跟在HashMap中存储没有关系，只是指在双向链表中的顺序。

部分源码

    
    //在访问元素之后，将该元素放到双向链表的尾巴处(所以这个函数只有在按照读取的顺序的时候才会执行)
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

    //在删除元素之后，将元素从双向链表中删除
    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

    //在插入新元素之后，需要回调函数判断是否需要移除一直不用的某些元素
    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);
        }
    }
    // 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存
    // removeEldestEntry 方法表示移除规则, 在 LinkedHashMap 里一直返回 false
    // LinkedHashMap是默认返回false的，我们可以继承LinkedHashMap然后复写该方法即可
    // 例如 LeetCode 第 146 题就是采用该种方法，直接 return size() > capacity;
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

设计LRU缓存结构

LinkedHashMap实现，用了jdk自带的轮子实现

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        int resultLength = 0;
        for (int[] operator : operators) {
            //对于每个操作2，输出一个答案 
            if (operator[0] == 2) {
                resultLength++;
            }
        }
        int[] results = new int[resultLength];
        int index = 0;
         
        LRUCache cache = new LRUCache(k);
        List<Integer> resultList = new LinkedList<>();
        for (int[] operator : operators) {
            switch (operator[0]) {
                case 1:
                    cache.put(operator[1], operator[2]);
                    break;
                case 2:
                    Integer value = cache.get(operator[1]);
                    results[index++] = value == null ? -1 : value;
            }
        }
        return results;
    }
}

/**
    * LRU Cache
    */
class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache;
    public LRUCache(int capacity) {
        this.cap=capacity;
        //为什么是0.75
        //提高空间利用率和 减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小，
        cache=new LinkedHashMap<Integer, Integer>(cap,0.75f,true){   
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return cache.size()>cap;//设置put更新后，size()超过容量设置就移除最久远的元素
            }
        };
    }//LRUCache(int capacity) end

    public int get(int key) {
        return cache.getOrDefault(key,-1);//getOrDefault()再次出现
    }

    public void put(int key, int value) {
        cache.put(key,value);
    }
}

HashMap + 双向链表实现，leetcode官方题解版本

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

LRU的实现

LRU

LinkedHashMap简述

设计LRU缓存结构