算法 - 深拷贝（支持循环引用）

Posted on

1. 题目

实现一个 deepClone(source)，对一个值进行深拷贝，要求：

  • 对象、数组递归拷贝，新旧互不影响（改新不影响旧）。
  • 正确处理循环引用（a.self = a），不能栈溢出。
  • 尽量还原特殊类型：Date、RegExp、Map、Set，以及 Symbol 作为 key。
  • 函数、原始值直接返回（浅拷贝即可）。

示例:

1
2
3
4
const obj = { name: "jack", tags: ["ts", "algo"], born: new Date() };
obj.self = obj;                 // 循环引用
const copy = deepClone(obj);
copy.self === copy;             // true（保持了引用关系而非死循环）

2. 解题思路

深拷贝 = 递归遍历 + 类型分发。两大难点：

2.1 循环引用：WeakMap 记忆化

若对象 A 引用了 B，B 又引用回 A，朴素递归会无限下钻爆栈。解决：用一个 WeakMap<源对象, 克隆对象> 记录「已经克隆过的源对象 -> 其克隆结果」。每次要克隆一个对象前，先查 WeakMap，命中就直接返回缓存的克隆体，从而打断回环并保持引用一致性。用 WeakMap 而非 Map 是为了不阻止源对象被 GC。

2.2 类型分发

  • 原始值（typeof !== "object" 且非函数）→ 直接返回。

  • null → 直接返回。

  • Date → new Date(+value)。

  • RegExp → new RegExp(source, flags)。

  • Map / Set → 新建并递归克隆每个值（键一般也克隆以保险）。

  • 数组 → map 递归。

  • 普通对象 → 遍历自有属性（含 Symbol key）递归。

  • 时间复杂度：O(n)，n 为节点数。

  • 空间复杂度：O(n)（递归栈 + WeakMap）。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
function deepClone<T>(source: T, cache = new WeakMap<object, any>()): T {
    // 原始值 / null / 函数：直接返回
    if (source === null || typeof source !== "object") {
        return source;
    }

    // 命中缓存：处理循环引用的关键
    if (cache.has(source as object)) {
        return cache.get(source as object);
    }

    // Date
    if (source instanceof Date) {
        return new Date(source.getTime()) as unknown as T;
    }

    // RegExp
    if (source instanceof RegExp) {
        return new RegExp(source.source, source.flags) as unknown as T;
    }

    // Map
    if (source instanceof Map) {
        const result = new Map();
        cache.set(source as object, result);
        for (const [key, value] of source.entries()) {
            result.set(deepClone(key, cache), deepClone(value, cache));
        }
        return result as unknown as T;
    }

    // Set
    if (source instanceof Set) {
        const result = new Set();
        cache.set(source as object, result);
        for (const value of source.values()) {
            result.add(deepClone(value, cache));
        }
        return result as unknown as T;
    }

    // 数组
    if (Array.isArray(source)) {
        const result: any[] = [];
        cache.set(source as object, result);
        for (let i = 0; i < source.length; i++) {
            result[i] = deepClone(source[i], cache);
        }
        return result as unknown as T;
    }

    // 普通对象（含 Symbol key）
    const result = Object.create(Object.getPrototypeOf(source));
    cache.set(source as object, result); // 先建立映射再递归，才能扛住循环引用
    for (const key of Reflect.ownKeys(source)) {
        const descriptor = Object.getOwnPropertyDescriptor(source, key)!;
        if (descriptor.enumerable) {
            result[key] = deepClone((source as any)[key], cache);
        } else {
            Object.defineProperty(result, key, descriptor);
        }
    }
    return result as T;
}

// 测试
const obj: any = { name: "jack", tags: ["ts", "algo"], born: new Date(0) };
obj.self = obj;
const copy = deepClone(obj);
console.log(copy.self === copy);        // true
console.log(copy.tags !== obj.tags);    // true（独立副本）

划重点：cache.set 必须在递归子属性之前执行。若等子树克隆完再写缓存，遇到 obj.self = obj 时缓存里还没有 obj 的克隆体，就会无限递归。

4. 面试延伸

  • JSON.parse(JSON.stringify(obj)) 的坑：会丢失 function、Symbol、undefined，把 Date 变字符串、RegExp 变 {}，遇循环引用直接抛错——是必答的反面教材。
  • structuredClone：现代浏览器/Node 内置的深拷贝，支持循环引用与多种内建类型，但不克隆函数、DOM 节点、原型链方法。能提到它说明关注标准 API。
  • 进阶要求：拷贝不可枚举属性 / getter / 原型链（本题用 Reflect.ownKeys + getPrototypeOf 已部分覆盖）；Symbol 作 key 的还原。
  • 讲题结构建议：先点出「循环引用 + 特殊类型」两大难点，再用 WeakMap 破第一个，体现你先识别问题再逐个击破的思路。

难度：困难 | 前端手写题压轴 | 引用类型与递归