關(guān)鍵字： 緩存 前端 JavaScript

今天在看vue的1.0.0版本的時(shí)候（git版本d8e9e2e)，看到一個(gè)控制緩存的js（src/cache.js)。細(xì)細(xì)讀了下，覺得這個(gè)算法不錯(cuò)，遂寫出來和大家分享下?？醋⑨屢彩莥yx截取了某人寫的工具的一部分（地址：https://github.com/rsms/js-lru）。

原理：通過雙向鏈表實(shí)現(xiàn)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 -- 尾指針。鏈表在初始化的時(shí)候會(huì)制定長度，每次新增對象的時(shí)候會(huì)將對象放入鏈表，更新新對象和尾指針的雙向關(guān)系，然后將尾指針指向新的數(shù)據(jù)。如果超出鏈表長度則做彈出操作。
彈出操作就是頭指針指向的對象（最老的）清除，同時(shí)移動(dòng)頭指針指向第二老的對象。
每次讀取對象會(huì)將讀取的對象置為最新。從鏈表中拿出（更新原位置左右兩個(gè)對象的雙向指向）放入最尾部（更新尾指針及雙向指向）。
這樣就能保證讀取頻率高的對象一直保存在緩存中，提高命中率。
代碼如下

/**
 * 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這個(gè)工具，代碼如下

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()
  })
})

好了就那么多，希望你會(huì)有收獲。

祝爸爸媽媽身體健康！