算法：LRU 缓存实现

概述

LRU 缓存算法，是提供一种缓存实现，要求插入新数据时，当缓存达到最大空间要求，就将最久没有访问过的数据删除掉从而为新数据腾出空间。同时要求获取或插入数据的时间复杂度都为 O(1)。

基本思路

• hash 表 + 链表

hash 表的目的是为了使访问的事件复杂度为 O(1)，链表是为了维护一种时间维度上是否最近被访问的前后关系。其中 hash 表使用 Java 中的 HashMap 来替代，链表部分自己实现。

代码

代码中附带很多注释，具体逻辑请参考注释

package top.hudk.cache;

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

/**
 * 作用： LRU(最近最少使用)缓存实现，
 * 提供加入缓存 put(k,v) 和从缓存获取数据get(k)两种方法，
 * 当加入缓存的数据已经将要超过缓存容量时，
 * 就将缓存中最久没有被访问的数据删除，
 * 从而为新数据腾出空间。
 * 如果加入新数据时，缓存中已经存在该键，
 * 那么将该键对应的数据标记为最新访问，并更新其内容。
 *
 * @author hudk
 * @date 2020/5/26 17:02
 */
public class LRUCache<K,V> {

    /**
     * 初始容量
     */
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 哈希表，用于在O（1）的时间内找到目标元素
     */
    private Map<K, Node> map = new HashMap<>();

    /**
     * 链表尾部元素，每次访问，都会将访问的数据移动到尾部
     */
    private Node<K, V> tail;

    /**
     * 链表头部元素，每次空间不足，都会删除头元素对应的数据
     */
    private Node<K, V> head;

    /**
     * 添加新的键值对元素
     *
     * @param key
     * @param value
     * @return
     */
    public V put(K key, V value) {
        //若新增的内容，缓存中没有，且当下容量已经达到最大容量，则将头部元素删除（头部元素是最久没有访问过的元素）
        if (!map.containsKey(key) && map.size() == capacity) {
            deleteHead();
        }
        //如果缓存中已经存在该键的内容，则将其在链表中的位置移到链表的尾部，并更新其内容。
        if (map.containsKey(key)) {
            setLastAndUpdate(key, value);
        } else {
            //如果缓存没有该键的内容，则直接将其追加到尾部
            linkLast(key, value);
        }
        return value;
    }

    /**
     * 从缓存中获取指定键对应的值内容
     *
     * @param key
     * @return
     */
    public V get(K key) {
        //如果该键存在缓存中，则将该键值元素在链表中的位置，移到链表尾部，并返回其值内容
        if (map.containsKey(key)) {
            setLast(key);
            return this.tail.item;
        } else {
            //如果缓存中没有找到该键对应的数据，则返回null
            return null;
        }
    }

    /**
     * 将新的元素，放到链表尾部，并加入到哈希表中
     *
     * @param key
     * @param value
     */
    private void linkLast(K key, V value) {
        Node<K, V> tail = this.tail;
        Node<K, V> newNode = new Node<>(key, value, null, this.tail);
        this.tail = newNode;
        if (tail == null) {
            this.head = newNode;
        } else {
            tail.next = newNode;
        }
        map.put(key, newNode);
    }

    /**
     * 删除链表头部元素
     */
    private void deleteHead() {
        if (this.head != null) {
            map.remove(this.head.kay);
            this.head.kay = null;
            this.head.item = null;
            Node next = this.head.next;
            if (next != null) {
                this.head.next.prev = null;
                this.head.next = null;
                this.head = next;
            }
        }
    }


    /**
     * 将集合中已有的指定元素，放到尾部，并更新它的内容
     *
     * @param key
     * @param value
     */
    private V setLastAndUpdate(K key, V value) {
        setLast(key);
        return this.tail.item = value;
    }

    /**
     * 将集合中已有的指定元素，放到尾部
     *
     * @param key
     */
    private V setLast(K key) {
        Node<K, V> node = map.get(key);
        if (this.head == this.tail || node == this.tail) {
            return this.tail.item;
        }
        if (node.next != null && node.prev != null) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        if (node == this.head) {
            node.next.prev = null;
            this.head = node.next;
        }
        this.tail.next = node;
        node.prev = tail;
        node.next = null;
        this.tail = node;
        return this.tail.item;
    }

    /**
     * 双向链表元素
     *
     * @param <K>
     * @param <V>
     */
    private static class Node<K, V> {
        K kay;
        V item;
        LRUCache.Node<K, V> next;
        LRUCache.Node<K, V> prev;

        Node(K kay, V element, LRUCache.Node<K, V> next, LRUCache.Node<K, V> prev) {
            this.kay = kay;
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}