LRU 算法的 O (1) 实现

本文首发于 LOGI'S BLOG，由作者转载。

上一篇我们用单链表实现了 LRU，但判断结点是否存在和删除尾结点都是 O(n) 操作。对于页面置换算法，速度通常是第一指标，我们想到散列表可在 O(1) 时间内找到结点，而双向链表删除尾结点的操作也为 O(1)，如果采用两者组合的数据结构，便可将 LRU 的性能提升到 O(1)。与此同时，从单链表到双向链表加上额外引入的散列结构，存储密度降低为 1/3，或者说空间复杂度是 O(n)，是典型的以空间换时间行为，实际上内存的作用本就如此。在 Java 中，HashMap 是散列表的典型实现，为了突显链表操作，我们直接使用它，仅实现一个简单双链表。

package com.logi.algorithm;


import java.util.HashMap;

/**
 * @author LOGI
 * @version 1.0
 * @date 2019/7/10 16:02
 */
public class LRUWithHashMapAndDoublyLinkedList {
    DoublyLinkedListNode head;
    DoublyLinkedListNode tail;
    HashMap<Integer, DoublyLinkedListNode> map;
    int capacity;
    int size;

    public LRUWithHashMapAndDoublyLinkedList(int capacity) {
        this.head = new DoublyLinkedListNode();
        this.tail = this.head;
        this.map = new HashMap<>();
        this.capacity = capacity;
    }

    public static void main(String[] args) {
        LRUWithHashMapAndDoublyLinkedList lru = new LRUWithHashMapAndDoublyLinkedList(2);
        lru.put(1, 1);
        System.out.println(lru + ", after put(1,1)");
        lru.put(2, 2);
        System.out.println(lru + ", after put(2,2)");
        lru.get(1);
        System.out.println(lru + ", after get(1)");
        lru.put(3, 3);
        System.out.println(lru + ", after put(3,3)");
        lru.get(2);
        System.out.println(lru + ", after get(2)");
        lru.put(4, 4);
        System.out.println(lru + ", after put(4,4)");
        lru.get(1);
        System.out.println(lru + ", after get(1)");
        lru.get(3);
        System.out.println(lru + ", after get(3)");
        lru.get(4);
        System.out.println(lru + ", after get(4)");
    }


    public int get(int key) {
        DoublyLinkedListNode current = this.map.get(key);
        if (current == null) {
            return -1;
        } else {
            DoublyLinkedListNode save = current;
            this.delete(current);
            this.insert(save);
            return save.value;
        }
    }

    public void put(int key, int value) {
        DoublyLinkedListNode current = this.map.get(key);
        if (current == null) {
            current = new DoublyLinkedListNode(key, value);
            if (this.size == this.capacity) {
                // map.remove 必须在前，因为如果先删除，tail 就改变了
                this.map.remove(this.tail.key);
                this.delete(this.tail);
            }
            this.insert(current);
            this.map.put(key, current);
        }
    }

    @Override
    public String toString() {
        StringBuilder list = new StringBuilder();
        DoublyLinkedListNode current = this.head.next;
        while (current != null) {
            list.append(current.value);
            if (current != this.tail) {
                list.append("->");
            }
            current = current.next;
        }
        return list.toString();
    }

    /**
     * 删除节点
     *
     * @param current
     */
    public void delete(DoublyLinkedListNode current) {
        current.prev.next = current.next;
        if (current.next != null) {
            current.next.prev = current.prev;
        } else {
            this.tail = current.prev;
            this.tail.next = null;
        }
        this.size--;
    }

    /**
     * 插入到表头
     *
     * @param current
     */
    public void insert(DoublyLinkedListNode current) {
        current.prev = this.head;
        current.next = this.head.next;
        if (this.head.next == null) {
            this.tail = current;
            this.tail.next = null;
        } else {
            this.head.next.prev = current;
        }
        this.head.next = current;
        this.size++;
    }

}

class DoublyLinkedListNode {
    DoublyLinkedListNode prev;
    DoublyLinkedListNode next;
    int key;
    int value;

    public DoublyLinkedListNode() {
    }

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

LinkedHashMap

对 Java 集合比较熟悉的同学应该知道，LinkedHashMap 本就是 HashMap 加 DoublyLinkedList 的实现，所以我们可以直接使用封装好的数据结构简洁地实现以上操作。

package com.logi.algorithm;

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

/**
 * @author LOGI
 * @version 1.0
 * @date 2019/7/10 17:53
 */
public class LRUWithLinkedHashMap {
    Map<Integer, Integer> cache;
    int capacity;

    public LRUWithLinkedHashMap(int capacity) {
        this.capacity = capacity;
        // 0.75 是数组扩容的触发条件，true 表示将结点以访问顺序排序，默认是插入顺序
        this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                // 设置删除年长结点的触发条件为缓存满
                return size() > capacity;
            }
        };
    }

    public static void main(String[] args) {
        // 与之前我们自行实现时的设定不同，在 LinkedHashMap 中，年长结点位于链表头
        LRUWithLinkedHashMap lru = new LRUWithLinkedHashMap(2);
        lru.put(1, 1);
        System.out.println(lru + ", after put(1,1)");
        lru.put(2, 2);
        System.out.println(lru + ", after put(2,2)");
        lru.get(1);
        System.out.println(lru + ", after get(1)");
        lru.put(3, 3);
        System.out.println(lru + ", after put(3,3)");
        lru.get(2);
        System.out.println(lru + ", after get(2)");
        lru.put(4, 4);
        System.out.println(lru + ", after put(4,4)");
        lru.get(1);
        System.out.println(lru + ", after get(1)");
        lru.get(3);
        System.out.println(lru + ", after get(3)");
        lru.get(4);
        System.out.println(lru + ", after get(4)");
    }

    @Override
    public String toString() {
        StringBuilder list = new StringBuilder();
        Iterator<Integer> iterator = this.cache.values().iterator();
        while (iterator.hasNext()) {
            list.append(iterator.next()).append("->");
        }
        return list.substring(0, list.length() - 2);
    }

    public int get(int key) {
        // 自动调整顺序，不存在返回 -1
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        // 自动插入，自动判满删除
        cache.put(key, value);
    }
}

Redis 中的 LRU

Redis 是一个高速缓存数据库，通过将所有数据加载于内存中获得最高读写性能，广泛应用于各种热点业务，如新浪热搜中。

当把 Redis 做 Cache 使用时，由于内存容量限制，需要配置最大内存使用量，如果使用量超过了 maxmemory，就通过 LRU 等策略剔除数据。以下是 Redis 中 LRU 的基本思想。

1. 用一个全局时钟作参照
2. 对每个 object 初始化和操作时都更新它各自的 lru 时钟
3. 随机挑选几个 key，根据 lru 时钟计算 idle 的时间，排序后放入 EvictionPool 中，最终挑选 idle 时间最长的 free。至于为什么随机和只选择 5 个，是出于性能考虑，因为全局排序非常消耗 CPU，而实际应用中没有必要如此精确。

可见，Redis 实现的 LRU 与理论的区别主要在于第 3 点，即内存满时，随机选择 n 个排序，由此也可窥见工业领域中 LRU 的最佳实践。

参考文献

• LRU 算法原理与实践
• Java 集合框架之 LinkedHashMap 详解
• HashMap 中 capacity、loadFactor、threshold、size 等概念的解释
• LRU Cache 算法在 Redis 中的应用