JavaScript中的函数缓存（Memoization）进阶：LRU缓存与高阶函数封装

描述：
函数缓存（Memoization）是一种优化技术，通过存储昂贵函数调用的结果，当相同输入再次出现时直接返回缓存结果，避免重复计算。在JavaScript中，我们不仅要实现基础缓存，还需处理缓存淘汰、高阶函数封装等进阶问题。常见场景包括递归优化、动态规划计算、API响应缓存等。

解题过程循序渐进讲解：

1. 基础函数缓存实现
首先实现一个最简单的缓存，使用普通对象存储结果：

function memoizeBasic(fn) {
  const cache = {};
  return function(...args) {
    const key = JSON.stringify(args);
    if (key in cache) {
      console.log('从缓存返回');
      return cache[key];
    }
    const result = fn.apply(this, args);
    cache[key] = result;
    return result;
  };
}

问题：仅适用于可序列化的参数，且缓存会无限增长。

2. 处理特殊参数（函数、Symbol等）
使用Map和WeakMap处理不可序列化的参数：

function memoize(fn) {
  const cache = new Map();
  return function(...args) {
    // 创建缓存键：对每个参数生成唯一标识
    const key = args.map(arg => {
      if (typeof arg === 'object' && arg !== null) {
        // 为对象创建弱引用键
        return arg;
      }
      return arg;
    });
    
    // 查找缓存
    for (let [cachedKey, value] of cache) {
      if (cachedKey.length === key.length && 
          cachedKey.every((k, i) => k === key[i])) {
        return value;
      }
    }
    
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

注意：对象直接比较使用引用相等，可能造成误判。

3. 实现LRU（最近最少使用）缓存淘汰
当缓存达到上限时，淘汰最久未使用的项：

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // Map保持插入顺序
  }
  
  get(key) {
    if (!this.cache.has(key)) return undefined;
    const value = this.cache.get(key);
    // 刷新为最新使用
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }
  
  set(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // 删除最早（最久未使用）的项
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

function memoizeLRU(fn, capacity = 100) {
  const cache = new LRUCache(capacity);
  return function(...args) {
    const key = JSON.stringify(args);
    if (cache.get(key) !== undefined) {
      return cache.get(key);
    }
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

4. 支持TTL（生存时间）的缓存
添加过期时间自动清理：

class TTLCache {
  constructor(ttl = 60000) { // 默认1分钟
    this.ttl = ttl;
    this.cache = new Map();
    this.timestamps = new Map();
  }
  
  get(key) {
    if (!this.cache.has(key)) return undefined;
    
    const timestamp = this.timestamps.get(key);
    if (Date.now() - timestamp > this.ttl) {
      this.delete(key);
      return undefined;
    }
    
    return this.cache.get(key);
  }
  
  set(key, value) {
    this.cache.set(key, value);
    this.timestamps.set(key, Date.now());
  }
  
  delete(key) {
    this.cache.delete(key);
    this.timestamps.delete(key);
  }
}

5. 高阶函数封装与配置化
创建可配置的memoize高阶函数：

function memoizeAdvanced(fn, options = {}) {
  const {
    maxSize = Infinity,
    ttl = Infinity,
    resolver = (...args) => JSON.stringify(args),
    equalityCheck = (a, b) => a === b
  } = options;
  
  const cache = new Map();
  const timestamps = new Map();
  const usageOrder = [];
  
  return function(...args) {
    const key = resolver(...args);
    
    // 检查缓存命中
    if (cache.has(key)) {
      const [cachedArgs, cachedValue, timestamp] = cache.get(key);
      
      // 检查参数是否完全相等（支持自定义比较）
      if (args.every((arg, i) => equalityCheck(arg, cachedArgs[i]))) {
        // 检查TTL
        if (Date.now() - timestamp <= ttl) {
          // 更新使用顺序
          const index = usageOrder.indexOf(key);
          usageOrder.splice(index, 1);
          usageOrder.push(key);
          return cachedValue;
        } else {
          cache.delete(key);
          timestamps.delete(key);
        }
      }
    }
    
    // 执行原函数
    const result = fn.apply(this, args);
    
    // 清理过期缓存
    if (ttl < Infinity) {
      const now = Date.now();
      for (const [k, [, , timestamp]] of cache) {
        if (now - timestamp > ttl) {
          cache.delete(k);
          timestamps.delete(k);
          const idx = usageOrder.indexOf(k);
          if (idx > -1) usageOrder.splice(idx, 1);
        }
      }
    }
    
    // 清理超过最大尺寸的缓存
    if (cache.size >= maxSize) {
      const oldestKey = usageOrder.shift();
      cache.delete(oldestKey);
      timestamps.delete(oldestKey);
    }
    
    // 存储新缓存
    cache.set(key, [args, result, Date.now()]);
    usageOrder.push(key);
    
    return result;
  };
}

6. 递归函数的自动缓存
处理递归函数的特殊情况：

function memoizeRecursive(fn) {
  const cache = new Map();
  
  const memoized = function(...args) {
    const key = JSON.stringify(args);
    
    if (cache.has(key)) {
      return cache.get(key);
    }
    
    // 在调用前注入缓存版本的函数
    const originalFn = fn;
    fn = memoized;
    
    const result = originalFn.apply(this, args);
    
    // 恢复原函数引用
    fn = originalFn;
    
    cache.set(key, result);
    return result;
  };
  
  return memoized;
}

7. 实际应用示例

// 斐波那契数列计算优化
const fibonacci = memoizeAdvanced(function(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}, { maxSize: 100 });

// 计算第50项，从指数级降到线性级
console.log(fibonacci(50));

// API请求缓存示例
const cachedFetch = memoizeAdvanced(
  async (url, options) => {
    const response = await fetch(url, options);
    return response.json();
  },
  { 
    ttl: 60000, // 1分钟缓存
    resolver: (url, options) => url + JSON.stringify(options || {})
  }
);

关键要点：

1. 缓存键的生成策略至关重要，需考虑各种数据类型
2. LRU策略防止内存无限制增长
3. TTL机制确保缓存数据新鲜度
4. 递归函数需要特殊处理缓存函数自身的引用
5. 高阶函数封装提高复用性和可配置性
6. 缓存一致性：当函数有副作用时需要谨慎使用

这种缓存机制特别适用于纯函数、计算密集型操作、递归计算等场景，能显著提升应用性能。