关键字： 缓存 前端 JavaScript
今天在看vue的1.0.0版本的时候（git版本d8e9e2e)，看到一个控制缓存的js（src/cache.js)。细细读了下，觉得这个算法不错，遂写出来和大家分享下。看注释也是yyx截取了某人写的工具的一部分（地址：https://github.com/rsms/js-lru）。
原理：通过双向链表实现Least Recently Used的算法，
entry entry entry entry
______ ______ ______ ______
| head |.newer => | |.newer => | |.newer => | tail |
.newest = | A | | B | | C | | D | = .oldest
|______| <= older.|______| <= older.|______| <= older.|______|
removed <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- added
head -- 头指针，tail -- 尾指针。链表在初始化的时候会制定长度，每次新增对象的时候会将对象放入链表，更新新对象和尾指针的双向关系，然后将尾指针指向新的数据。如果超出链表长度则做弹出操作。
弹出操作就是头指针指向的对象（最老的）清除，同时移动头指针指向第二老的对象。
每次读取对象会将读取的对象置为最新。从链表中拿出（更新原位置左右两个对象的双向指向）放入最尾部（更新尾指针及双向指向）。
这样就能保证读取频率高的对象一直保存在缓存中，提高命中率。
代码如下
/**
* A doubly linked list-based Least Recently Used (LRU)
* cache. Will keep most recently used items while
* discarding least recently used items when its limit is
* reached. This is a bare-bone version of
* Rasmus Andersson's js-lru:
*
* https://github.com/rsms/js-lru
*
* @param {Number} limit
* @constructor
*/
function Cache (limit) {
this.size = 0
this.limit = limit
this.head = this.tail = undefined
this._keymap = Object.create(null)
}
var p = Cache.prototype
/**
* Put <value> into the cache associated with <key>.
* Returns the entry which was removed to make room for
* the new entry. Otherwise undefined is returned.
* (i.e. if there was enough room already).
*
* @param {String} key
* @param {*} value
* @return {Entry|undefined}
*/
p.put = function (key, value) {
var entry = {
key: key,
value: value
}
this._keymap[key] = entry
if (this.tail) {
this.tail.newer = entry
entry.older = this.tail
} else {
this.head = entry
}
this.tail = entry
if (this.size === this.limit) {
return this.shift()
} else {
this.size++
}
}
/**
* Purge the least recently used (oldest) entry from the
* cache. Returns the removed entry or undefined if the
* cache was empty.
*/
p.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
}
return entry
}
/**
* Get and register recent use of <key>. Returns the value
* associated with <key> or undefined if not in cache.
*
* @param {String} key
* @param {Boolean} returnEntry
* @return {Entry|*}
*/
p.get = function (key, returnEntry) {
var entry = this._keymap[key]
if (entry === undefined) return
if (entry === this.tail) {
return returnEntry
? entry
: entry.value
}
// HEAD--------------TAIL
// <.older .newer>
// <--- add direction --
// A B C <D> E
if (entry.newer) {
if (entry === this.head) {
this.head = entry.newer
}
entry.newer.older = entry.older // C <-- E.
}
if (entry.older) {
entry.older.newer = entry.newer // C. --> E
}
entry.newer = undefined // D --x
entry.older = this.tail // D. --> E
if (this.tail) {
this.tail.newer = entry // E. <-- D
}
this.tail = entry
return returnEntry
? entry
: entry.value
}
module.exports = Cache
vue还附带了单元测试，使用的是jasmine这个工具，代码如下
var Cache = require('../../../src/cache')
/**
* Debug function to assert cache state
*
* @param {Cache} cache
*/
function toString (cache) {
var s = ''
var entry = cache.head
while (entry) {
s += String(entry.key) + ':' + entry.value
entry = entry.newer
if (entry) {
s += ' < '
}
}
return s
}
describe('Cache', function () {
var c = new Cache(4)
it('put', function () {
c.put('adam', 29)
c.put('john', 26)
c.put('angela', 24)
c.put('bob', 48)
expect(c.size).toBe(4)
expect(toString(c)).toBe('adam:29 < john:26 < angela:24 < bob:48')
})
it('get', function () {
expect(c.get('adam')).toBe(29)
expect(c.get('john')).toBe(26)
expect(c.get('angela')).toBe(24)
expect(c.get('bob')).toBe(48)
expect(toString(c)).toBe('adam:29 < john:26 < angela:24 < bob:48')
expect(c.get('angela')).toBe(24)
// angela should now be the tail
expect(toString(c)).toBe('adam:29 < john:26 < bob:48 < angela:24')
})
it('expire', function () {
c.put('ygwie', 81)
expect(c.size).toBe(4)
expect(toString(c)).toBe('john:26 < bob:48 < angela:24 < ygwie:81')
expect(c.get('adam')).toBeUndefined()
})
})
好了就那么多，希望你会有收获。
祝爸爸妈妈身体健康！
