Analysis of a LRU Cache with Weak Restriction

通常，我们可通过双向链表组合哈希表的形式实现一个存取时间复杂度都为 O(1) 的最近最少使用缓存（LRU Cache）。本文将分析 Github 上的一种宽松 LRU 算法，它的存取均摊时间复杂度也为 O(1)，且 实现非常简单。但有两个缺点。首先，它的 容量不是固定的，在最多占用 2N 个对象空间的情况下，由于 重复，能缓存的数据个数在 N ~ 2N 之间。此外，它 不保证 缓存中相邻的数据具有最近最少使用 顺序。

直接看代码：

// https://github.com/dominictarr/hashlru/blob/master/index.js

module.exports = function (max) {

  if (!max) throw Error('hashlru must have a max value, of type number, greater than 0')

  var size = 0, cache = Object.create(null), _cache = Object.create(null)

  function update (key, value) {
    cache[key] = value
    size ++
    if(size >= max) {
      size = 0
      _cache = cache
      cache = Object.create(null)
    }
  }

  return {
    has: function (key) {
      return cache[key] !== undefined || _cache[key] !== undefined
    },
    remove: function (key) {
      if(cache[key] !== undefined)
        cache[key] = undefined
      if(_cache[key] !== undefined)
        _cache[key] = undefined
    },
    get: function (key) {
      var v = cache[key]
      if(v !== undefined) return v
      if((v = _cache[key]) !== undefined) {
        update(key, v)
        return v
      }
    },
    set: function (key, value) {
      if(cache[key] !== undefined) cache[key] = value
      else update(key, value)
    },
    clear: function () {
      cache = Object.create(null)
      _cache = Object.create(null)
    }
  }
}

外层函数作为构造器导出，它接收一个 max，即上文提到的 N。该参数并不代表此 Cache 的最大容量，而是最大占用空间的一半。具体来说，在保存 max ~ 2max 个数据时，最多占用 2max 个对象空间。

检查 max 大于 0 后程序初始化了三个变量，size，cache 和 _cache。size 是 cache 变量的大小，具体来说是它的属性个数。cache 为新缓存，保存最近使用过的数据，_cache 为旧缓存，保存相对于新缓存最近没有使用的数据。代码中使用 Object.create(null) 创建对象是为了尽量减小对象体积，并加快运行速度。

紧接着定义了 update 函数。它接收一个键值对，会将键值保存到新缓存 cache，并使容量自增。如果容量超过了设定的阈值，则把容量置 0，让旧缓存引用新缓存，即保存它。之后使新缓存引用空对象，即清空它。

function update (key, value) {
  cache[key] = value
  size ++
  if(size >= max) {
    size = 0
    _cache = cache
    cache = Object.create(null)
  }
}

接下来外层构造函数返回了一个对象，该对象提供了操作缓存的接口，由于 has、remove 和 clear 都很简单，我们只关注 get 和 set。

首先是 get，对调用者而言，如果有缓存它就返回缓存数据，没有就返回 undefined。除了上述接口约定，在新缓存无数据但旧缓存有数据时，它会调用 update 方法。此时，旧缓存中的这个键值对会被拷贝到新缓存，相当于热数据刷新，那么旧缓存中的数据相对于新缓存就是最近没有使用的。如果新缓存大小达到阈值，则丢弃旧缓存中的所有数据，也就是将最近未使用数据置换掉。

get: function (key) {
  var v = cache[key]
  if(v !== undefined) return v
  if((v = _cache[key]) !== undefined) {
    update(key, v)
    return v
  }
}

最后看 set，对调用者而言，它会无条件保存传入的键值对。其内部的具体实现为，如果新缓存有值，则修改新缓存属性，实际上，该操作只有在新值不等于旧值时才有意义，并且此种情况 不占用更多空间，无需考虑旧数据置换。如果新缓存没有值，此时放入新值 会使内存增加，所以调用 update 函数检查是否需要置换最近未使用数据。

set: function (key, value) {
  if(cache[key] !== undefined) cache[key] = value
  else update(key, value)
}

接下来我们分析为何该缓存最多会占用 2N 空间。观察以下用例：

const cache = LRUCache(50)
for (const i=0; i<100; i++) cache.set(i, i)

初始化一个 max==50 的缓存，随后连续放入 100 个不同数据。根据以上分析，每次设置都会调用 update 函数，当调用到第 50 次时，新缓存会被赋值到旧缓存，当调用到第 100 次时（阈值判断之前），新旧缓存各自保存着 50 个不同数据，总共占用 100 个空间，空间利用率 100%。

再观察以下用例：

const cache = LRUCache(50)
for (const i=0; i<50; i++) cache.set(i, i)
for (const i=0; i<50; i++) cache.get(i)

我们仍初始化一个 max==50 的缓存，但先连续放入 50 个不同数据，此时，新缓存会赋值到旧缓存，随后新缓存被清空。接着，程序连续进行 50 次读取，根据上述分析，每次调用 get 都无法命中新缓存，但会命中旧缓存，所以每次都会调用 update 函数。在 update 内部，新缓存会保存旧缓存的键值对拷贝，当进行第 50 次读取时（阈值判断之前），新缓存大小为 50，旧缓存也为 50，但它们的数据完全一样，总共占用 100 个空间，空间利用率 50%。

实际使用中，set 和 get 会交替进行，所以它占用的空间以及有效数据都介于 N 到 2N 之间，但是大概率存在重复数据。

基于以上分析，该缓存的最大优点是实现简单，缺点是空间利用率低，且不固定，不保证相邻元素顺序，适用于日常使用。在其它语言中，cache 和 _cache 等价于 HashTable，是比较复杂的数据结构，建议仍搭配双向链表实现。