实现LRU算法

LRU算法概述

LRU：Least Recently Read （最近最少访问），是一种常见的缓存淘汰算法，当容量不够时淘汰最近最少访问的元素。

使用示例

/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)
cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
cache.get(1);       // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前至队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入队头
cache.get(2);       // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据
cache.put(1, 4);    
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头

一些特点

• 查找效率高。尽量O(1)的查找效率
• 插入、删除要求效率高，容量满的时候要淘汰最近最少访问的元素。
• 元素之间是有顺序的，因为区分最近使用和久未使用的数据。

实现LRU核心数据结构

• hash表：快速查找，但是各个节点的数据不是有顺序的。
• 链表：插入删除快，有序但是查找速度不快。

最终结合两种数据结构。哈希链表

这里的两个问题：

• 为什么链表是双向链表？
  因为在容量满足了之后需要对链表尾部的节点删除，这时候要断开上一个节点和其的链，这就需要找到上一个节点。

• 为什么链表中也是key和value，不能直接放value吗？
  因为在删除尾部节点的时候需要同时删除hash表中的元素，这时候需要根据key来删除，索引链表里也要冗余key。

java代码实现

使用HashMap和LinkedList来实现

class LRUCache {
    class EasyNode {
        Integer key;
        Integer value;
        EasyNode(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }
    Map<Integer, EasyNode> map;
    LinkedList<EasyNode> cache;
    int cap;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        cache = new LinkedList<>();
        this.cap = capacity;
    }
    
    public int get(int key) {
        // 如果key在map中不存在 返回-1
        if (!map.containsKey(key)) {
            return -1;
        }

        // 存在 则维护LRU中双向链表的逻辑
        EasyNode node = map.get(key);
        // 删除再添加到队尾
        cache.remove(node);
        cache.addLast(node);
        return node.value;

    }
    
    public void put(int key, int value) {
        // map中存在 则map更新 且将该节点放入队尾
        EasyNode node = new EasyNode(key, value);
        if (map.containsKey(key)) {
            cache.remove(map.get(key));
            cache.addLast(node);
            map.put(key, node);
        } else{
            // 判断是否需要淘汰
            if (cache.size() == cap) {
                // 进行缓存的淘汰
                EasyNode removeNode = cache.removeFirst();
                map.remove(removeNode.key);
            }
            // 再添加到map和队尾
            map.put(key, node);
            cache.addLast(node);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

使用HashMap和自定义的双向链表实现

• 自定义双向链表的节点和双向链表

  /**
   * 双向链表节点
   */
  @Setter
  @Getter
  public class DeListNode <Key, Value>{
  
      private Key key;
      private Value value;
      // 前驱节点
      private DeListNode<Key, Value> prev;
      // 后继节点
      private  DeListNode<Key, Value> next;
  
      public DeListNode(Key key, Value value)
      {
          this.key = key;
          this.value = value;
      }
      public String toString() {
          return String.format(" (key:%s，value:%s) ", key, value);
      }
  }

/**
 * 简单实现双端链表
 */
public class DeLinkedList<Key, Value> {
    // 头和尾节点
    private DeListNode<Key, Value> head, tail;

    // 链表元素个数
    private int size;

    public int size() {return  size;}

    public DeLinkedList() {
        // 初始化一个 头尾巴节点 两个节点不会在真正使用中用到
        head = new DeListNode<>(null, null);
        tail = new DeListNode<>(null, null);
        // 首尾连接
        head.setNext(tail);
        tail.setPrev(head);
    }

    // 给尾巴加入新的节点
    public void addLast(DeListNode<Key, Value> node) {

        // 虚拟的尾巴
        DeListNode<Key, Value> dummyTail = tail;
        // 真实的尾节点
        DeListNode<Key, Value> trueTail = dummyTail.getPrev();

        // 加入的节点和真实尾巴节点链接
        trueTail.setNext(node);
        node.setPrev(trueTail);

        // 再链接上虚拟尾巴节点
        node.setNext(dummyTail);
        dummyTail.setPrev(node);
        size ++;
    }

    public String toString() {
        if (head.getNext() == tail) {
            return
                    "[]";
        } else {
            DeListNode current = head.getNext();
            StringBuffer sb = new StringBuffer();
            sb.append(" 旧 [");
            while (!current.equals(tail)) {
                sb.append(current.toString());
                current = current.getNext();
            }
            sb.append("] 新");
            return sb.toString();
        }
    }

    public void remove(DeListNode<Key, Value> node) {
        // 假设node 一定存在
        node.getPrev().setNext(node.getNext());
        node.getNext().setPrev(node.getPrev());
        size -- ;
    }

    // 队头移除元素
    public DeListNode<Key, Value> removeFirst() {
        // 没有元素不操作
        if (head.getNext() == tail) {
            return null;
        }

        DeListNode<Key, Value> trueHead = head.getNext();
        head.setNext(trueHead.getNext());
        trueHead.getNext().setPrev(head);
        size--;
        return trueHead;
    }
}

• 实现LRUCache

  public class 实现LRU {
      /**
       * 简单双端队列
       * @param <Key>
       * @param <Value>
       */
  
      public static class  LRUCache <Key, Value>{
          // 容量
          private int cap;
          // hash表
          private HashMap<Key, DeListNode<Key, Value>> map;
          // 双向链表缓存
          private DeLinkedList<Key, Value> cache;
  
          // 初始化函数
          public LRUCache(int cap) {
              this.cap = cap;
              map = new HashMap<>(cap);
              cache = new DeLinkedList<>();
          }
  
          /**
           * 根据key获取value
           * 逻辑：
           *      1. 如果缓存中不存在 则返回null
           *      2. 如果存在，将命中的元素移动到队头（LRU的逻辑） 返回元素
           * @param key
           * @return
           */
          public synchronized Value get(Key key) {
              if (!map.containsKey(key)) {
                  return null;
              } else {
                  //  移动元素到队尾 采用先删除再插入的方式
                  DeListNode<Key, Value> keyValueDeListNode = map.get(key);
                  cache.remove(keyValueDeListNode);
                  cache.addLast(keyValueDeListNode);
                  return keyValueDeListNode.getValue();
              }
          }
  
          /**
           * 添加一个元素到LRU缓存中
           * 逻辑：
           *      1. LRUCache中是否存在key 如果存在替换对应的node 即map.put 然后维护双向链表（插入再删除）
           *      2. 如果不存在 需要根基cap判断是否需要淘汰队头元素。 队列尾部添加节点 map中添加然后删除淘汰的key
           *
           * @param key
           * @param value
           */
          public synchronized void put(Key key, Value value) {
              // 构造新节点
              DeListNode<Key, Value> node = new DeListNode<>(key, value);
              if (map.containsKey(key)){
                  // 存在key 则去替换map中的节点 且维护双端队列（删除再添加）
                  cache.remove(map.get(key));
                  cache.addLast(node);
                  map.put(key, node);
              } else {
                  // 不存在要去判断是否触发淘汰
                  if (cap == cache.size()) {
                      // 双端队列队头淘汰（LRU逻辑）
                      DeListNode<Key, Value> first = cache.removeFirst();
                      // map中remove
                      map.remove(first.getKey());
                  }
  
                  // 直接添加到尾部即可
                  cache.addLast(node);
                  // map中添加
                  map.put(key, node);
              }
          }
          public void printf() {
              System.out.println("cachhe 队列" + cache.toString());
          }
      }
  
      public static void main(String[] args) {
          // 初始化为2的lruCache
          LRUCache<Integer, Integer> lruCache = new LRUCache<>(2);
          lruCache.put(1, 1);
          lruCache.put(2, 2);  // 新 [(2,2), (1,1)] 旧
          lruCache.printf();
  
          Integer integer = lruCache.get(1); // 新 [(1,1), (2,2)] 旧
          lruCache.printf();
  
          lruCache.put(2,3); //   新 [(2,3), (1,1)] 旧
          lruCache.printf();
  
          // 再添加 淘汰的是1
          lruCache.put(4, 4); // 新 [(4,4), (2,3)] 旧
          lruCache.printf();
      }
  }