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 的最佳实践。

参考文献

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,937评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,503评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,712评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,668评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,677评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,601评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,975评论 3赞 396
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,637评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,881评论 1赞 298
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,387评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,971评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2赞 342