实现一个LRU Cache

0x00 简介

Least Recently Used (LRU)是一种缓存替换策略。其实First In First Out (FIFO)、Last In First Out (LIFO)等都是缓存替换策略。基于LRU策略我们可以设计 LRU Cache。

LRU Cache在很多场景下都有应用，比如网易云音乐中的「最近播放」功能，把最近播放的100首单曲或歌单/专辑记录下来，这个「最近播放」的判断依据就是LRU。又比如很多项目里都有的「登录历史」，可以把最近登录的帐号记录下来。又比如图片缓存，什么时候清除内存中的图片(放弃引用，让gc做处理)？

Android 2.3（Level 9）时代，垃圾回收机制更倾向于回收 SoftReference 或 WeakReference 的对象。后来，又来到了 Android3.0，图片缓存在内容中，因为不知道要在是什么时候释放内存，没有策略，没用一种可以预见的场合去将其释放。这就造成了内存溢出。

我们知道SoftReference的策略是，只有当内存告急（即将 OOM）时，才会对只剩下Soft Reference 的变量进行回收，因此 SoftReference 比较适合用来做 Cache。但它的问题也很明显，无法提供足够的信息可以让 runtime决定什么时候清除引用的对象，也不知道是应该清除SoftReference还是增大Heap。所以Android建议使用LRU Cache。

Avoid Soft References for Cacheing

那本文的目的就在于实现一个有put和get功能的数据结构，名字叫LRUCache:

LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

0x01 使用什么数据结构

举网易云音乐那个例子，看起来其实很容易，只要把播放的新的音乐放到首位就行了。
是这样的，比如采用ArrayList，听一首新歌，把它add到list的首位，然后把末位的歌曲删除就行了。但问题是，如果这个音乐就在list里就会重复。所以必须要在add之前，先搜索list里是否有这首歌。如果采用list，搜索用的时间是O(n)。

这件事其实就是put的时候把entry放到优先级最高的slot，get的时候把已有的元素抽出来，挪到优先级最高的slot。

如何在O(1)时间实现put和get？
要用O(1)时间，那Array、Queue、Stack甚至LinkedList都做不到（LinkedList能做到快速put和get，但是必须知道对象的地址，这个地址需要用O(n)时间搜索）。

说道O(1)，很容易想到用HashMap。其实仔细想想，HashMap就是对链表的优化，针对链表不能快速定位对象所在位置的缺陷，把对象的地址用key的hash作为依据保存起来，这样get的复杂度就是O(1)了。

但HashMap有个缺陷，就是，HashMap的保存的key-value不是有序的，而是用散列的方法根据key的hash计算得到index分配到固定位置的。

怎么办，用LinkedHashMap吧。

0x02 LinkedHashMap

这里先不提它的原理是什么，要知道它是可以保持你put的顺序的就行了。
这样的话是不是直接记录一下Map的Size和Capacity就差不多搞定了？其实连这个也不要。。LinkedHashMap有两种模式，一种是普通模式，就是有序地插入；第二种就直接帮你实现了LRUCache的功能，只要把它的第三个构造参数写成true，那就开启了accessOrder模式，如果覆写removeEldestEntry，会自动根据它的条件移除LEAST USED的元素。于是，一个简单的LruCache就实现了！

public class LruCache {
    public class LRUCache {
        private LinkedHashMap<Integer, Integer> map;
        private final int CAPACITY;

        public LRUCache(int capacity) {
            CAPACITY = capacity;
            map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return size() > CAPACITY;
                }
            };
        }

        public int get(int key) {
            return map.getOrDefault(key, -1);
        }

        public void set(int key, int value) {
            map.put(key, value);
        }
    }
}

那么，LinkedHashMap是怎么做到有序存储的？

0x03 模仿LinkedHashMap实现LruCache

前面说过，如果知道node的地址，链表的插入删除是O(1)的。具体来讲，我们需要的是一个双向链表（因为需要前一个node的地址），这样就可以保证在只知道当前节点的地址的情况下，在O(1)时间实现插入删除。

具体来讲，对于get方法，只需要利用一个HashMap（或是线程安全的HashTable）的get方法，get到了之后把包含key和value的node移动到双向链表的表头位置即可。

    public int get(int key) {

        DLinkedNode node = hashTable.get(key);
        if (node == null) {
            return -1; // should raise exception here.
        }

        // move the accessed node to the head;
        this.moveToHead(node);

        return node.value;
    }

对于set方法，需要区分这个node是否已经在链表中。
如果不在链表中，需要：

  1. 创建一个node
  2. 把新的node加入到链表开头。
  3. 检查node数量是否超过了capacity，如果超过了，要把结尾的node删除。

如果node在链表中，需要:

  1. 获取这个node，更新它的value（对于网易云音乐那种不改变值的情形来说，不需要value）。
  2. 移动node到表头。
    public void set(int key, int value) {
        DLinkedNode node = hashTable.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            hashTable.put(key, newNode);
            addNode(newNode);

            ++count;

            if (count > capacity) {
                // pop the tail
                DLinkedNode tail = popTail();
                hashTable.remove(tail.key);
                --count;
            }
        } else {
            // update the value.
            node.value = value;
            moveToHead(node);
        }

    }

基于这种想法，完整实现的LruCache如下：

public class LruCache {
    private Hashtable<Integer, DLinkedNode> hashTable = new Hashtable<Integer, DLinkedNode>();
    private int count;
    private int capacity;
    private DLinkedNode head, tail;

    static class DLinkedNode {
        int key;
        int value;
        DLinkedNode pre;
        DLinkedNode post;
    }

    public LruCache(int capacity) {
        count = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        head.pre = null;

        tail = new DLinkedNode();
        tail.post = null;

        head.post = tail;
        tail.pre = head;
    }

    /**
     * Always add the new node right after head;
     * 把新的Node加入到链表开头
     */
    private void addNode(DLinkedNode node) {
        node.pre = head;
        node.post = head.post;
        head.post.pre = node;
        head.post = node;
    }

    /**
     * Remove an existing node from the linked list.
     * 从链表移除一个Node。这个操作是O(1)的，因为给的是Node的地址
     */
    private void removeNode(DLinkedNode node) {
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;

        pre.post = post;
        post.pre = pre;
    }

    /**
     * Move certain node in between to the head.
     * 把中间的Node移动到链表开头
     */
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addNode(node);
    }

    // pop the current tail.
    private DLinkedNode popTail() {
        DLinkedNode res = tail.pre;
        removeNode(res);
        return res;
    }

    public int get(int key) {

        DLinkedNode node = hashTable.get(key);
        if (node == null) {
            return -1; // should raise exception here.
        }

        // move the accessed node to the head;
        this.moveToHead(node);

        return node.value;
    }

    public void set(int key, int value) {
        DLinkedNode node = hashTable.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            hashTable.put(key, newNode);
            addNode(newNode);

            ++count;

            if (count > capacity) {
                // pop the tail
                DLinkedNode tail = popTail();
                hashTable.remove(tail.key);
                --count;
            }
        } else {
            // update the value.
            node.value = value;
            moveToHead(node);
        }

    }
}

其实node仍然保存在Hashtable原来的bucket里面，只是我们另外用一个DoubleLinkedList把Node连接起来了。

0x04 总结

本文讲了LruCache和LinkedList的原理，实现了一个简单的LruCache。其实Android SDK中的LruCache的实现跟这个略有不同，比如它的put方法和get方法都用了同步锁:

public final V put(K key, V value) {
    ...
    synchronized (this) {
        ...
        // 计算双向链表中的node数量
        size += safeSizeOf(key, value);
        ...
    }
    ...
    trimToSize(maxSize);
    return previous;
}

那是因为LinkedHashMap是继承了LinkedHashMap而不是HashTable。
利用LruCache我们还可以实现DisLruCache，which，可以用来实现图片缓存之类的工具，比如：

mMemoryCache = new LruCache<String, Bitmap>(cacheSize) {
            @Override
            protected int sizeOf(String key, Bitmap bitmap) {
                 //return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
                return bitmap.getByteCount() / 1024;
            }
        };

不过这些都不重要了，我们已经知道什么是LruCache了，并且体会到了链表和Map的巧妙联系。

Ref:
https://www.jianshu.com/p/833adadc9eb6

by DrunkPaino

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