最近在看Vue的源码，不得不说的是，Vue的源码十分优雅简洁，下面就来分享下Vue的缓存利用的算法LRU算法。

LRU算法

LRU是Least recently used的简写，主要原理是根据历史访问记录来淘汰数据，说白了就是这个算法认为如果数据被访问过，那么将来被访问的几率也高。其存储结构是一个双链表，最近被访问到的放在双链表的尾部，头部放的就是最早被访问到数据。关于算法的具体流程，可以来，这个可视化过程，模拟了lru算法进行调度的过程。

缺页数

lru在笔试题中也会经常出现，经常会考到的那就是缺页数，例如页面访问序列为：2,3,2,1,5,2,4,5,3,2,5,2， 分配给某个进程3页内存，求其缺页次数。

1. 2            // 第一次缺页

2. 2 -> 3    // 第二次缺页

3. 3 -> 2    // 第三次缺页

4. 3 -> 2 -> 1

5. 2 -> 1   // 第四次缺页

6. 2 -> 1 -> 5

7. 1 -> 5 -> 2

8. 5 -> 2   // 第五次缺页

9. 5 -> 2 -> 4

10. 2 -> 4 -> 5

11. 4 -> 5   // 第六次缺页

12. 4 -> 5 -> 3

13. 5 -> 3    // 第七次缺页

14. 5 -> 3 -> 2

15. 3 -> 2 -> 5

16. 3 -> 5 -> 2

所以总共有着7次缺页，上面的这个流程也是算法的具体执行流程，可以看出的是当有新的节点进入时，首先会检测内存是否已满，如果满了的话，就先将头给移除，再在尾部添加上这个新节点；假若该节点在链表中存在，那么直接将这个节点拿到头部。下面来看下Vue对这个算法的实现：

vue中的lru

源码时src/cache.js，先来看看其构造函数：

// limit是最大容量function Cache (limit) {    this.size = 0;    this.limit = limit;    this.head = this.tail = undefined;    this._keymap = Object.create(null);}

尤大利用集合_keymap来存储已有的节点，在判断是否存在时，直接读取属性就行，不用在遍历一遍链表，这样降低了在查找过程中的时间复杂度。head代表着头节点，tail代表着尾节点，链表中的节点是这样的：

node {    value: 键值,    key: 键名,    older: 指向前一个节点，head的older指向undefined,    newer: 指向下一个节点，tail的newer指向undefined}

来看get方法：

Cache.prototype.get = function (key, returnEntry) {     var entry = this._keymap[key];     // 本身没有,则不用调度,直接将新的节点插入到尾部即可    if (entry === undefined) return;    // 访问的就是尾部节点,则不需要调度        if (entry === this.tail) {        return returnEntry ? entry : entry.value;    }    // 访问的不是尾部节点,需要将被访问节点拿到头部    if (entry.newer) {        if (entry === this.head) {            this.head = entry.newer;        }        entry.newer.older = entry.older;    }    if (entry.older) {        entry.older.newer = entry.newer;    }    entry.newer = undefined;    entry.older = this.tail;    if (this.tail) {        this.tail.newer = entry;    }    this.tail = entry;    return returnEntry ? entry : entry.value; };

get是为了得到链表中是否含有这个节点，假如有这个节点，那么还要对这个节点进行调度，也就是将节点拿到尾部。

// 将链表的头给去除Cache.prototype.shift = function () {    var entry = this.head;    if (entry) {        this.head = this.head.newer;        this.head.older = undefined;        entry.newer = entry.older = undefined;        this._keymap[entry.key] = undefined;        this.size--;    }    return entry;};p.put = function (key, value) {    var removed;    var entry = this.get(key, true);    // 插入的情况,插入到尾部    if (!entry) {        // 如果集合已经满了,移除一个,并将其return        if (this.size === this.limit) {            removed = this.shift();        }        entry = {            key: key        };        this._keymap[key] = entry;        if (this.tail) {            this.tail.newer = entry;            entry.older = this.tail;        } else {  // 链表中插入第一个节点时，头节点就是尾几点            this.head = entry;        }        this.tail = entry;   // 节点会添加或者拿到尾部        this.size++;    }    // 更新节点的value，假若本身链表中有，get方法中已经调度好，只要更新值就好    entry.value = value;    return removed;};

至此，vue的cache代码已经全部解析完，其具体的作用由于源码刚刚开始读吗，目前还不清楚，不过应该在解析指令等方面有着重大的作用。

最后希望大家关注下