JavaScript记忆化函数实现原理解惑及替代实现方式咨询

一、为什么memoize内部的Map能持续生效？ #

你疑惑的核心点在于：memoize函数执行完后，内部的cache Map按理说应该被销毁，但实际调用返回的函数时缓存却能正常工作——这是JavaScript的闭包特性在起作用。

当你调用memoize(expensiveFunction)时，memoize函数会创建一个cache Map实例，然后返回一个匿名函数。这个匿名函数在定义时就绑定了memoize的作用域，哪怕memoize已经执行完毕，只要这个返回的匿名函数还被引用（比如赋值给了memoizedExpensiveFunction），它就能一直访问到那个cache变量。也就是说，cache的生命周期和返回的匿名函数绑定在了一起，只要后者存在，前者就不会被垃圾回收。所以每次调用memoizedExpensiveFunction，都是在操作同一个cache Map，自然能实现缓存持久化。

二、其他函数记忆化的实现方式 #

1. 用普通对象做缓存 #

适合参数能被序列化为字符串的场景，实现简单：

function memoizeWithObject(func) {
  const cache = {};
  return function(...args) {
    const key = JSON.stringify(args);
    if (key in cache) {
      return cache[key];
    }
    const result = func(...args);
    cache[key] = result;
    return result;
  };
}

2. 用WeakMap做缓存（针对引用类型参数） #

如果被记忆的函数参数是对象这类引用类型，WeakMap的优势在于：当缓存的键（对象）没有其他引用时，会自动被垃圾回收，避免内存泄漏。注意WeakMap的键只能是对象：

function memoizeWithWeakMap(func) {
  const cache = new WeakMap();
  return function(arg) {
    if (cache.has(arg)) {
      return cache.get(arg);
    }
    const result = func(arg);
    cache.set(arg, result);
    return result;
  };
}

3. 自定义缓存键生成逻辑 #

默认用JSON.stringify生成键有局限性：比如无法区分键顺序不同的对象（{a:1,b:2}和{b:2,a:1}会被序列化为相同字符串）、某些值（比如函数、Symbol）无法序列化。可以自定义键生成函数来解决：

function memoizeWithCustomKey(func, getKey) {
  const cache = new Map();
  return function(...args) {
    const key = getKey(...args);
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = func(...args);
    cache.set(key, result);
    return result;
  };
}

// 示例：用参数的字符串拼接作为键
const memoizedFunc = memoizeWithCustomKey(expensiveFunction, (n) => `num_${n}`);

4. 借助第三方库 #

比如lodash的_.memoize，提供了更灵活的配置，支持自定义缓存键和缓存容器：

const _ = require('lodash');
const memoizedFunc = _.memoize(expensiveFunction);

三、关于面试官提到的“use try data structure” #

你听到的应该是口误，大概率是以下两种情况之一：

• Hash data structure：指用Map、普通对象这类哈希表结构存储缓存，这是记忆化最常用的实现方式，核心是通过键值对快速查找缓存结果，时间复杂度接近O(1)。
• Tree data structure：比如用二叉搜索树存储缓存，适合需要有序遍历缓存键的场景，但日常开发中很少用，因为哈希表的查找效率比树结构更高。

内容的提问来源于stack exchange，提问作者Achu Anil