LRU 缓存算法技术文档

LRU（Least Recently Used，最近最少使用）缓存算法是一种常用的缓存淘汰策略，它通过移除最长时间未被访问的数据来为新数据腾出空间。以下是对本项目实现的LRU缓存算法的详细说明。

1. 安装指南

通过复制代码

推荐将lru.js或lru.js和lru.d.ts文件复制到您的源代码目录中。对于最小功能需求，您只需要复制到注释“以下是可选代码”的部分。

使用NPM

yarn add lru_map

请注意，由于NPM是一个大的扁平命名空间，您需要将模块导入为“lru_map”而不是简单的“lru”。

使用AMD

使用AMD模块加载器（例如amdld）也可以加载此模块，无需任何配置。

测试

• 运行测试：npm test
• 运行基准测试：npm run benchmark

使用TypeScript

此模块包含完整的类型覆盖，以便与TypeScript一起使用。如果您复制了代码或文件而不是使用模块加载器，请确保将lru.d.ts包含在与lru.js相同的目录中。

import { LRUMap } from './lru'

2. 项目使用说明

LRU缓存算法项目使用了一个双向链表来实现，以下是示例代码：

let c = new LRUMap(3)
c.set('adam', 29)
c.set('john', 26)
c.set('angela', 24)
console.log(c.toString()) // -> "adam:29 < john:26 < angela:24"
console.log(c.get('john')) // -> 26
console.log(c.toString()) // -> "adam:29 < angela:24 < john:26"
c.set('zorro', 141)
console.log(c.toString()) // -> "angela:24 < john:26 < zorro:141"

3. 项目API使用文档

LRUMap类的API模仿了JavaScript的Map对象，这意味着在大多数情况下，您可以直接使用LRUMap替代Map。

export class LRUMap<K, V> {
  constructor(limit: number, entries?: Iterable<[K, V]>)
  size: number
  limit: number
  oldest: Entry<K, V>
  newest: Entry<K, V>
  assign(entries: Iterable<[K, V]>): void
  set(key: K, value: V): LRUMap<K, V>
  shift(): [K, V] | undefined
  get(key: K): V | undefined
  has(key: K): boolean
  find(key: K): V | undefined
  delete(key: K): V | undefined
  clear(): void
  keys(): Iterator<K>
  values(): Iterator<V>
  entries(): Iterator<[K, V]>
  [Symbol.iterator](): Iterator<[K, V]>
  forEach(fun: (value: V, key: K, m: LRUMap<K, V>) => void, thisArg?: any): void
  toJSON(): Array<{ key: K, value: V }>
  toString(): string
}

interface Entry<K, V> {
  key: K
  value: V
}

如果需要在项从缓存中逐出时进行任何形式的最终处理，包装shift方法是一个很好的方式：

let c = new LRUMap(123);
c.shift = function() {
  let entry = LRUMap.prototype.shift.call(this);
  doSomethingWith(entry);
  return entry;
}

内部实现会在需要逐出条目时调用shift方法，所以这个方法对于从缓存中移除的任何项都是保证会被调用的。返回的条目必须不包含对其他条目的任何强引用。有关更多详细信息，请参阅LRUMap.prototype.set()方法的文档。