引言

leetcode和牛客都出了对应的题目

146. LRU 缓存机制

设计LRU缓存结构_

lru简介

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的数据予以淘汰。

设计思想

• 所谓缓存，必须要有读+写两个操作，按照命中率的思路考虑，写操作+读操作时间复杂度都需要为O(1)
• 特性要求
  • 必须要有顺序之分，区分最近使用的和很久没有使用的数据排序。
  • 写和读操作一次搞定。

如果容量满了要删除最不常用的数据，每次新访问还要把新的数据插入到队头(按照业务你自己设定左右那一边是队头)

换言之,查找快、插入快、删除快，且还需要先后排序,哈希链表可以解决这个问题

使用LinkedHashMap实现LRU算法

由于LinkedHashMap可以记录下Map中元素的访问顺序，所以可以轻易的实现LRU算法。只需要将构造方法的accessOrder传入true，并且重写removeEldestEntry方法即可。accessOrder传入true可以实现LRU缓存算法（访问顺序）

package com.company;

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

/**
 * @author shoukailiang
 * @version 1.0
 * @date 2021/9/2 8:24
 */
public class LRU<K,V> extends LinkedHashMap<K,V> {
    private int capacity;

    public LRU(int capacity) {
        super(capacity,0.75f,true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return super.size()>capacity;
    }

    public static void main(String[] args) {
        LRU lru = new LRU(3);
        lru.put(1,"a");
        lru.put(2,"b");
        lru.put(3,"c");
        System.out.println(lru.keySet());
        lru.put(4,"d");
        System.out.println(lru.keySet());
        lru.put(3,"c");
        System.out.println(lru.keySet());
        lru.put(3,"c");
        System.out.println(lru.keySet());
        lru.put(3,"c");
        System.out.println(lru.keySet());
        lru.put(5,"e");
        System.out.println(lru.keySet());

    }
}
// accessOrder true 
[1, 2, 3]
[2, 3, 4]
[2, 4, 3]
[2, 4, 3]
[2, 4, 3]
[4, 3, 5]
// accessOrder false
[1, 2, 3]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[3, 4, 5]
复制代码

哈希表 + 双向链表

package com.company;

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

/**
 * @author shoukailiang
 * @version 1.0
 * @date 2021/9/2 8:38
 */
public class LRUCache2 {

    // map负责查找,构建虚拟的双向链表,里面装的就是一个个node节点,作为数据载体

    //构造一个node节点,作为数据载体
    class Node<K,V>{
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;
        public Node(){
            this.prev = this.next = null;
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }
    }
    // 新的插入头部，旧的从尾部移除
    class DoubleLinkedList<K,V>{
        Node<K, V> head;
        Node<K, V> tail;

        // 构造一个虚拟的双向链表,里面放的就是node
        public DoubleLinkedList(){
            //头尾哨兵节点
            head = new Node<K, V>();
            tail = new Node<K, V>();
            head.next = tail;
            tail.prev = head;
        }
        public void addHead(Node<K, V> node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }

        public void removeNode(Node<K, V> node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
        }

        // 获得最后一个节点
        public Node<K, V> getLast() {
            if(tail.prev == head) {
                return null;
            }
            return tail.prev;
        }

    }

    private int cacheSize;
    private Map<Integer, Node<Integer, String>> map;
    private DoubleLinkedList<Integer, String> doubleLinkedList;
    public LRUCache2(int cacheSize) {
        this.cacheSize = cacheSize;
        map = new HashMap<>();
        doubleLinkedList = new DoubleLinkedList<>();
    }
    public String get(int key) {
        if(!map.containsKey(key)) {
            return null;
        }

        Node<Integer, String> node = map.get(key);

        //更新节点位置，将节点移置链表头
        doubleLinkedList.removeNode(node);
        doubleLinkedList.addHead(node);

        return node.value;
    }
    public void put(int key, String value) {

        if(map.containsKey(key)) {

            Node<Integer, String> node = map.get(key);
            node.value = value;
            map.put(key, node);


            doubleLinkedList.removeNode(node);
            doubleLinkedList.addHead(node);
        }else {
            if(map.size() == cacheSize) {//已达到最大容量了，把旧的移除，让新的进来
                Node<Integer, String> lastNode = doubleLinkedList.getLast();
                map.remove(lastNode.key);
                doubleLinkedList.removeNode(lastNode);
            }
            Node<Integer, String> newNode = new Node<>(key, value);
            map.put(key, newNode);
            doubleLinkedList.addHead(newNode);
        }
    }

    public static void main(String[] args) {
        LRUCache2 lru = new LRUCache2(3);
        lru.put(1,"a");
        lru.put(2,"b");
        lru.put(3,"c");
        System.out.println(lru.map.keySet());
        lru.put(4,"d");
        System.out.println(lru.map.keySet());
        lru.put(3,"c");
        System.out.println(lru.map.keySet());
        lru.put(3,"c");
        System.out.println(lru.map.keySet());
        lru.put(3,"c");
        System.out.println(lru.map.keySet());
        lru.put(5,"e");
        System.out.println(lru.map.keySet());
    }
}
// 
[1, 2, 3]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[3, 4, 5]
复制代码