Random

// True random replacement. Stupidly simple, surprisingly effective.
class RandomCache<K, V> {
  private store = new Map<K, V>();
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    return this.store.get(key);
  }

  set(key: K, value: V): void {
    if (!this.store.has(key) && this.store.size >= this.capacity) {
      // Pick a random key and evict it.
      const keys = Array.from(this.store.keys());
      const victim = keys[Math.floor(Math.random() * keys.length)];
      this.store.delete(victim);
    }
    this.store.set(key, value);
  }
}

// Redis-style "sample N, evict oldest of N" — random as N -> 1,
// approaches LRU as N -> cache size.
class SampledLRU<K, V> {
  private store = new Map<K, { value: V; lastUsed: number }>();
  private clock = 0;
  constructor(private capacity: number, private samples = 5) {}

  set(key: K, value: V): void {
    if (!this.store.has(key) && this.store.size >= this.capacity) {
      const keys = Array.from(this.store.keys());
      let victim = keys[Math.floor(Math.random() * keys.length)];
      for (let i = 1; i < this.samples; i++) {
        const candidate = keys[Math.floor(Math.random() * keys.length)];
        if (this.store.get(candidate)!.lastUsed < this.store.get(victim)!.lastUsed) {
          victim = candidate;
        }
      }
      this.store.delete(victim);
    }
    this.store.set(key, { value, lastUsed: ++this.clock });
  }
}