LRU 的设计与实现

作者：Grey

原文地址：

博客园：LRU 的设计与实现

CSDN：LRU 的设计与实现

题目描述

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

题目链接见：LeetCode 146. LRU Cache

主要思路

双向链表和哈希表搭配使用，哈希表用来存加入的元素，双向链表用于标识记录的新旧程度，双向链表尾部记录最新使用过的记录，头部记录的是最久没有使用过的记录，哈希表的 size 就是当前 LRU Cache 存了多少个元素，同时要记录一个 LRU Cache 的最大容量 capacity，如果哈希表的 size 等于 capacity，说明 LRU Cache 已经满了。

  static class LRUCache {
    // 查询某个值是否在 LRU Cache 中
    private HashMap<Integer, Node> map;
    // 自定义的双向链表
    private DoubleLinkedList list;
    // LRU 的最大容量，
    // 如果 map.size = capacity 就需要淘汰了
    private final int capacity;

    public LRUCache(int capacity) {
      this.map = new HashMap<>();
      this.list = new DoubleLinkedList();
      this.capacity = capacity;
    }
    public void put(int k, int v) {
        // TODO
    }
    public int get(int k) {
        // TODO
    }
  }

具体来说，对于 LRU Cache 的 put 操作，针对加入的元素，有如下两种情况：

• 如果是未加入的元素
  • 加入后，如果整个 LRU Cache 的容量未超过 capacity，则会加入到双向链表的尾部，同时存一份到哈希表中，
  • 超过了capacity，则会最先淘汰双向链表头部的元素（因为这个元素是最久没有使用过的元素），然后把这个元素插入双向链表尾部，且存一份到哈希表中。
• 如果是已经加入的元素
  • 则直接把这个元素取出来，移动到双向链表的尾部，作为最新使用过的记录。

    public void put(int key, int value) {
      if (map.containsKey(key)) {
        // put 的记录在 cache 中已经存在了
        // 更新旧值
        Node old = map.get(key);
        old.value = value;
        // 把更新后的节点放到双向链表的尾部，作为最新使用过的记录
        list.moveToLast(old);
      } else {
        if (map.size() == capacity) {
            // map 容量已满，移除掉map中双向链表头部的元素
          map.remove(list.head.key);
          // 双向链表头部元素被新put进来的元素填充
          list.head.value = value;
          list.head.key = key;
          map.put(key, list.head);
          // 把头部元素放入双向链表最后一个位置
          list.moveToLast(list.head);
        } else {
            // map 容量没满，直接加入 map 和双向链表的尾部
          Node node = new Node(key, value);
          map.put(key, node);
          list.addLast(node);
        }
      }
    }

对于LRU Cache 的 get 操作：

• 如果 get 的 key 不存在，直接返回 -1。（题目已说明：-1 表示未找到）
• 如果 get 的 key 存在，则从哈希表中取出这个元素后，同时把这个元素移动到双向链表的尾部，作为最新使用过的记录。

    public int get(int key) {
      if (map.containsKey(key)) {
        // LRU 中有这个元素，直接取出，并且把该元素放入双向链表尾部，作为最新使用过的元素
        Node node = map.get(key);
        list.moveToLast(node);
        return node.value;
      }
      return -1;
    }

以上的 put 和 get 操作，涉及双向链表的两个自定义方法

// 把双向链表中 node 这个节点移动到末尾
moveToLast(node)
// 加入一个节点到双向链表的末尾
addLast(node)

都是比较常规的实现，不赘述

        public void moveToLast(Node node) {
            if (tail == node) {
                // 移动的节点就是尾部节点，不需要动
                return;
            }
            if (head == node) {
                head = node.next;
                head.last = null;
            } else {
                // 把 node 先和原先链表断连
                node.last.next = node.next;
                node.next.last = node.last;
            }
            // 统一把node加到尾部
            addLast(node);
        }

        public void addLast(Node node) {
            if (head == null) {
                head = node;
                tail = node;
            }
            if (tail != null) {
                node.last = tail;
                node.next = null;
                tail.next = node;
                tail = node;
            }
        }

完整代码见：

public static class LRUCache {
    public static class Node {
        public int key;
        public int value;
        public Node last;
        public Node next;

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

    public static class DoubleLinkedList {
        public Node head;
        public Node tail;

        public DoubleLinkedList() {
            head = null;
            tail = null;
        }

        public void moveToLast(Node node) {
            if (tail == node) {
                return;
            }
            if (head == node) {
                head = node.next;
                head.last = null;
            } else {
                node.last.next = node.next;
                node.next.last = node.last;
            }
            node.last = tail;
            node.next = null;
            tail.next = node;
            tail = node;
        }

        public void addLast(Node node) {
            if (head == null) {
                head = node;
                tail = node;
            }
            if (tail != null) {
                tail.next = node;
                node.last = tail;
                tail = node;
            }
        }
    }

    private HashMap<Integer, Node> map;
    private DoubleLinkedList list;
    private final int capacity;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.list = new DoubleLinkedList();
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            list.moveToLast(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node old = map.get(key);
            old.value = value;
            list.moveToLast(old);
        } else {
            if (map.size() == capacity) {
                map.remove(list.head.key);
                list.head.value = value;
                list.head.key = key;
                map.put(key, list.head);
                list.moveToLast(list.head);
            } else {
                Node node = new Node(key, value);
                map.put(key, node);
                list.addLast(node);
            }

        }
    }
}

更多

算法和数据结构笔记