LRUCache.ts

ts版 LRU 简单实现

利用了 Map key 的有序性，以及 Map 对频繁增删改的优化。

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Map

export default class LRUCache<K = string, V = any> {
  public readonly capacity: number;
  private store: Map<K, V>;

  constructor(capacity = 10) {
    this.capacity = capacity;
    this.store = new Map();
  }

  public get(k: K): V {
    const v = this.store.get(k);

    if (!v) {
      return v;
    }

    this.store.delete(k);
    this.store.set(k, v);
    return v;
  }

  public set(k: K, v: V): void {
    if (this.store.size >= this.capacity) {
      this.store.delete(this.leastKey);
    }

    if (this.store.has(k)) {
      this.store.delete(k);
    }

    this.store.set(k, v);
  }

  public getRandomItems(n = 1): V[] {
    const randomKey = this.getRandomNFromArray(Array.from(this.allKeys), n)
    return randomKey.map(this.get, this);
  }

  get leastKey(): K {
    return this.allKeys.next().value;
  }

  get mostKey(): K {
    return Array.from(this.allKeys)[this.size - 1];
  }

  get size(): number {
    return this.store.size;
  }

  get allKeys() {
    return this.store.keys();
  }
  
  getRandomNFromArray<T>(arr: T[], n = 1): T[] {
    if (!Array.isArray(arr) || n < 1 || arr.length === 0) {
        return [];
    }

    const arrLen = arr.length;
    const result: T[] = [];
    if (n > arrLen) {
        n = arrLen;
    }
    while (result.length < n) {
        const randomItem = arr[Math.floor(Math.random() * arrLen)];
        if (!result.includes(randomItem)) {
            result.push(randomItem);
        }
    }
    return result;
  }
}