前端手写系列01-深拷贝的两种实现与局限

[venaissance]

本文是前端手写系列的第一篇

说到手写深拷贝，可以说是大多数前端的阿克琉斯之踵了，面试年年考，大部分人年年不会，网上博客遍地还都是错的。本文的目标很简单，就是提升你今后面对这个问题时的信心。

在正式讲手写深拷贝之前，先说两个错误答案：

1. Object.assign({}, a)
2. 扩展操作符 {...a}

这两个都是浅拷贝。

深拷贝的意义

我先举个例子，有这么个需求，你有一个计算器组件 NumPad 和一个对象 record ，你可以加减乘除，把计算的结果存在 record.amount 里，点击确认按钮，把 record 保存到一个数组 RecordList 里。

<Layout class="layout">
    {{record}}
    <NumPad :value.sync="record.amount"/>
    <NumPad :value.sync="record.amount" @submit="onSaveRecord"/>
</Layout>

如果不假思索的写

onSaveRecord() {
    this.recordList.push(this.record);
}

你会发现，无论计算结果是什么，RecordList 里的所有 record 都是一样的，为什么？

因为内存中只有一个 record 对象，或者说， record 对象的地址是固定不变的，所以每次往数组里 push 的其实都是同一个对象的引用，当然都是一样的了。

怎么解决这个问题呢？这就要用到深拷贝了。

由于 record 对象只有一个 amount 属性，且 amount 属性的类型为 Number，于是可以用最简单的深拷贝来解决，这个方法叫 JSON 反序列化。

onSaveRecord() {
    const recordCopy = JSON.parse(JSON.stringify(this.record));
    this.recordList.push(recordCopy);
}

所以为什么要深拷贝？

因为不希望数据被修改。

深拷贝的完整定义

数据 A 里面的所有属性都不包含对数据 B 的引用，简单点讲，A 与 B 值相等，但改动 A 并不会影响 B。

下面我们正式开始深拷贝的实现，我把深拷贝的实现方式分按需求分成两种，简单需求和复杂需求。

简单需求

最简单的手写深拷贝就一行，通过 JSON 反序列化来实现。

const B = JSON.parse(JSON.stringify(A))

如果大家了解 JSON 的话，那么缺点也是显而易见的，JSON value不支持的数据类型，都拷贝不了

1. 不支持函数
2. 不支持undefined（支持null）
3. 不支持循环引用，比如 a = {name: 'a'}; a.self = a; a2 = JSON.parse(JSON.stringify(a))
4. 不支持Date，会变成 ISO8601 格式的字符串
5. 不支持正则表达式
6. 不支持Symbol

这里附上 JSON value 支持的数据类型：

至于如何支持这些复杂需求，就需要用到递归克隆了。

复杂需求

如何实现上述 JSON 反序列化不支持的需求？

我们分情况讨论。

如果原数据为非对象的基本数据类型，则直接返回原数据即可——JS 里只有对象才存在于堆区，栈区保存对象的引用（内存地址），其余基本数据类型保存在栈区（不涉及内存地址）。

如果原数据为对象，那么需要根据不同对象的类型做出相应的调整。如果原对象为函数，好像不知道怎么复制，在这里用个骚操作供大家参考，直接用 apply 调用原函数即可：

// 深拷贝函数
if (source instanceof Function) {
  return function () {
    return source.apply(this, arguments);
  };
}

再举几个特殊对象的例子。

// 几个特殊对象
let target;
if (source instanceof Array) {
  target = new Array();
} else if (source instanceof Date) {
  target = new Date(source);
} else if (source instanceof RegExp) {
  target = new RegExp(source.source, source.flags);
}

除了对象分类型讨论，我们还需要递归克隆，这是因为对象里面的属性也可以是对象，深拷贝的深就体现在这里，不管多深，都不能包含对原数据的引用，「老死不相往来」。递归克隆时，我们还要注意的一点是由于 for...in... 是遍历对象及其原型链上可枚举的属性，为了节约内存，我们尽量不要拷贝原型链上的属性。

// 递归克隆
for (let key in source) {
  if (source.hasOwnProperty(key)) {
    target[key] = this.clone(source[key]);
  }
}

还有一个终极问题，对象有环怎么办？递归不就永远出不来了？别慌，用缓存解决。我们把原对象和克隆过的对象都放进缓存列表，如果有环，返回对应的新对象即可。

接下来给出解决这个问题，也是复杂需求的最终代码：

class DeepClone {
  constructor() {
    this.cacheList = [];
  }
  clone(source) {
    if (source instanceof Object) {
      const cache = this.findCache(source); // 如果找到缓存，直接返回
      if (cache) return cache;
      else {
        let target;
        if (target instanceof Array) {
          target = new Array();
        } else if (target instanceof Function) {
          target = function () {
            return source.apply(this, arguments);
          };
        } else if (target instanceof Date) {
          target = new Date(source);
        } else if (target instanceof RegExp) {
          target = new RegExp(source.source, source.flags);
        } else {
          target = new Object(); // 不要忘记普通对象
        }

        this.cacheList.push([source, target]); // 把原对象和新对象放进缓存列表
        for (let key in source) {
          if (source.hasOwnProperty(key)) {
            // 不拷贝原型上的属性，浪费内存
            target[key] = this.clone(source[key]); // 递归
          }
        }
        return target;
      }
    } else {
      return source;
    }
  }
  findCache(source) {
    for (let i = 0; i < this.cacheList.length; ++i) {
      if (this.cacheList[i][0] === source) {
        return this.cacheList[i][1];
      }
    }
  }
}

如果您想看递归克隆详细的测试与运行结果，请参见 我的 GitHub →

递归克隆看起来很强大，但是完美无缺吗？其实还是有不小的距离：

1. 对象类型支持不够多（Buffer，Map，Set等都不支持）
2. 存在递归爆栈的风险

如果要解决这些问题，实现一个”完美“的深拷贝，只能求教上百行代码的 Lodash.cloneDeep() 了😂。

让我们再引申一下，深拷贝有局限吗？

深拷贝的局限

如果需要对一个复杂对象进行频繁操作，每次都完全深拷贝一次的话性能岂不是太差了，因为大部分场景下都只是更新了这个对象的某几个字段，而其他的字段都不变，对这些不变的字段的拷贝明显是多余的。那么问题来了，浅拷贝不更新，深拷贝性能差，怎么办？

这里推荐3个可以实现”部分“深拷贝的库：

1. Immutable.js Immutable.js 会把对象所有的 key 进行 hash 映射，将得到的 hash 值转化为二进制，从后向前每 5 位进行分割后再转化为 Trie 树。Trie 树利用这些 hash 值的公共前缀来减少查询时间，最大限度地减少无谓 key 的比较。关于 Trie 树（字典树）的介绍，可以看我的博客算法基础06-字典树、并查集、高级搜索、红黑树、AVL 树

2. seamless-immutable，如果数据量不大但想用这种类似 updateIn 便利的语法的话可以用 seamless-immutable。这个库就没有上面的 Trie 这些幺蛾子了，就是为其扩展了 updateIn、merge 等 9 个方法的普通简单对象，利用 Object.freeze 冻结对象本身改动, 每次修改返回副本。感觉像是阉割版，性能不及 Immutable.js，但在部分场景下也是适用的。

3. Immer.js，通过用来数据劫持的 Proxy 实现：对原始数据中每个访问到的节点都创建一个 Proxy，修改节点时修改副本而不操作原数据，最后返回到对象由未修改的部分和已修改的副本组成。

总结

看完全文，你现在能回答怎么实现深拷贝了吗？概括成一句就是：简单需求用 JSON 反序列化，复杂需求用递归克隆。

对于递归克隆的深拷贝，核心有三点：

1. 对象分类
2. 递归
3. 用缓存对付环

扩展阅读

1. Deep-copying in JavaScript - DasSur.ma
2. Introducing Immer: Immutability the easy way
3. 算法基础06-字典树、并查集、高级搜索、红黑树、AVL 树
4. 处理 JavaScript 复杂对象：深拷贝、Immutable & Immer