面试必问-JAVA-LRU-双向链表+HashMap方式实现

原理如下图

为了编码方便处理各种边界值，冗余一个head和tail 来确保不会出现空指针，简化编码。

源代码如下：

package com.cache;

import java.util.HashMap;
import java.util.Map;

/**
 * 双向链表+HashMap实现LRU
 * 1.双向链表的好处是写代码方便，知道前后，删除起来更快。若是用单向也行，但是代码写起来麻烦。
 * 2.HashMap的作用是提高操作（含插入、查询、删除）效率，存储key放在链表的哪个节点。操作时
 * 能直接找到对应的节点操作。如果没有HashMap，每次操作都要去遍历链表找到要操作的节点才能操作。
 * 3.为了操作方便，设立头尾两个固定的节点，无业务语义
 *
 * @author chris
 */
public class LruCacheByDoublyLinkedListAndHashMap<K, V> {

    //定义节点
    class Node {
        //Node值，此处存储的是缓存的value值，key值在此处也冗余一个
        K key;
        V value;

        //定义节点的前后节点位置
        Node pre;
        Node next;

        public Node() {
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format("%s:%s ", key, value));
            return sb.toString();
        }
    }

    //定义双向链表
    class DoublyLinkedList {

        //头部节点
        Node head;
        //尾部节点
        Node tail;

        //链表初始化时，头尾都是一个，串联起来
        public DoublyLinkedList() {
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.pre = head;
        }

        //当一个节点被访问时，把他放到队头
        public synchronized void addToFirst(Node node) {

            //~~把当前节点插入非head最前面

            //当前节点指向原第一个节点
            node.next = head.next;
            //原第一个节点，指向当前节点
            head.next.pre = node;

            //~~调整head到第一位

            //当前节点的上一个节点改成head
            node.pre = head;
            //head的下一阶段改成当前节点
            head.next = node;
        }

        //当一个节点被访问时，把他放到队头
        public synchronized void moveToFirst(Node node) {

            //当前前节点的上下两个节点先调整好
            Node preNode = node.pre;
            Node nextNode = node.next;
            preNode.next = nextNode;
            nextNode.pre = preNode;

            //~~把当前节点插入非head最前面

            //当前节点指向原第一个节点
            node.next = head.next;
            //原第一个节点，指向当前节点
            head.next.pre = node;

            //~~调整head到第一位

            //当前节点的上一个节点改成head
            node.pre = head;
            //head的下一阶段改成当前节点
            head.next = node;
        }

        public synchronized K remove(Node node) {
            //把下一元素，指向前一元素
            node.next.pre = node.pre;
            //把前一元素的下一元素，指向下一元素
            node.pre.next = node.next;

            //废弃掉当前元素
            node.next = null;
            node.pre = null;

            return node.key;
        }

        public synchronized K removeLast() {
            //如果当前没有节点，则不删除
            if (head.next == tail) {
                return null;
            }

            //找出要被删除的节点
            Node toRemove = tail.pre;
            //执行删除
            return remove(toRemove);
        }
    }

    //~~ LRU 开始实现
    //定义双向链表
    DoublyLinkedList cache;
    //定义HashMap，key是目标key，value是Node
    Map<K, Node> map;
    //缓存容量
    int capacity;

    public LruCacheByDoublyLinkedListAndHashMap(int capacity) {
        this.capacity = capacity;
        cache = new DoublyLinkedList();
        map = new HashMap<>();
    }

    //获取key
    public V get(K key) {
        //key不存在，直接返回空
        if (!map.containsKey(key)) {
            return null;
        }
        //key存在，获取key对于的值，并调整key对应的节点到队头
        else {
            Node node = map.get(key);
            cache.moveToFirst(node);
            return node.value;
        }
    }

    //放入KV
    public void put(K key, V value) {

        //包含key，则覆盖，并挪到表头
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            cache.moveToFirst(node);
        }
        //不包含key，则要插入一个key，并判断空间是否已满，需要移除队列尾部的key
        else {
            if (map.size() >= capacity) {
                K beRemoveKey = cache.removeLast();
                map.remove(beRemoveKey);
            }

            Node newNode = new Node(key, value);
            cache.addToFirst(newNode);

            map.put(key, newNode);
        }
    }

    @Override
    public String toString() {

        Node node = cache.head.next;
        int count = 1;
        StringBuilder sb = new StringBuilder();
        while (node != null && node != cache.tail && count <= capacity) {
            sb.append(String.format("%s:%s ", node.key, node.value));
            count++;
            node = node.next;
        }

        return sb.toString();
    }

}