在编写javascript代码时，适当地使用缓存技术可以提高数据的重复使用率，以达到优化性能的目的。

最直接最暴力的做法是，直接创建一个没有原型的空对象，然后一股脑的往里塞数据：

1
2
3
4
var _data = Object.create(null) // 这是我们实现的缓存对象（捂脸）
_data['foo'] = 123
_data['bar'] = 'hello kitty'
_data['author'] = {name: '歪闹', blog: 'http://iwhynot.me'}

使用的时候也很方便，直接读取缓存对象的属性值，有就拿来用，没有就去求值然后再按上面的方法存取。

诚然，这样做也可以满足大多数的需求，但是作为面向新世纪的fronter，我们应该要有更高的追求。

歪闹日志

先来实现一个能记录数据size的缓存对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function Cache () {
  this.size = 0
  this._data = Object.create(null)
}

var p = Cache.prototype
p.put = function (key, value) {
  var entry = this.get(key, true)
  if (!entry) {
    this.size++
  }
  this._data[key] = {
    key: key,
    value: value
  }
}

p.get = function (key, returnEntry) {
  var entry = this._data[key]
  if (entry === undefined) return
  return returnEntry ? entry : entry.value
}

现在可以愉快的存取数据了。

1
2
3
4
5
6
var cache = new Cache()
cache.put('foo', 123)
cache.put('author', {name: '歪闹', blog: 'http://iwhynot.me'})

cache.size // 2
cache.get('foo') // 123

写到这里发现，搞了半天就只是实现了个阉割版的数组功能。其实不然，数组存数据的确很方便，但是取数据就没那么好玩了，要一个个去找，效率就不高了。

这时我们发现这个缓存对象看起来可以存无限多的数据，很多数据已经没用了，还存留着浪费内存。我们再来加一个大小限制，超过限制就把最先插入的缓存删掉以给后来者腾点空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
function Cache (limit) {
  this.size = 0
  this.limit = limit
  this._keys = [] // 保存存储的数据key值
  this._data = Object.create(null)
}

var p = Cache.prototype
p.put = function (key, value) {
  var removed
  var entry = this.get(key, true)
  if (!entry) {
    if (this.size === this.limit) {
      removed = this.shift()
    }
    this._keys.push(key)
    this.size++
  }
  this._data[key] = {
    key: key,
    value: value
  }

  return removed
}

p.shift = function () {
  var head
  var key = this._keys.shift()
  if (key !== undefined) {
    delete this._data[key]
    this.size--
  }
  return head
}

p.get = function (key, returnEntry) {
  var entry = this._data[key]
  if (entry === undefined) return
  return returnEntry ? entry : entry.value
}

一切看起来很不错的样子。可这种方式有个不好的地方，后来的数据总会挤走先来的数据，而不管数据的使用频率。所以根据LRU最近最少使用算法，我们来实现更合理的链表存储方式。

歪闹日志

1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。

最终的代码实现（最新插入的数据放在了尾部，原理一样）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
function Cache (limit) {
  this.size = 0
  this.limit = limit
  this.head = this.tail = undefined
  this._data = Object.create(null)
}

var p = Cache.prototype

p.put = function (key, value) {
  var removed

  var entry = this.get(key, true)
  if (!entry) {
    if (this.size === this.limit) {
      removed = this.shift()
    }
    entry = {
      key: key
    }
    if (this.tail) {
      this.tail.newer = entry
      entry.older = this.tail
    } else {
      this.head = entry
    }
    this._data[key] = entry
    this.tail = entry
    this.size++
  }
  entry.value = value

  return removed
}

p.shift = function () {
  var entry = this.head
  if (entry) {
    this.head = entry.newer
    this.head.older = undefined
    entry.newer = entry.older = undefined
    this._data[entry.key] = undefined
    this.size--
  }
  return entry
}

p.get = function (key, returnEntry) {
  var entry = this._data[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
}