谈谈经常出现的出现的“深拷贝”

发表于 更新于 分类于 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 8 分钟

想想已经 N 久没有写文章了，有点怠惰，之后还是尽量学了什么，就写文章记录下来；写文章的过程也是自己把知识联系起来的过程。
写这篇文章主要原因还是之前字节跳动三面，面试官一开始就要去写一个深拷贝，然而之前对这方面了解的很少很少，面试表现可以说相当差了，结果也是直接挂掉…
之后重新学习了，这里就记录下吧

怎样定义深拷贝？深拷贝到底要拷贝什么？

说起深拷贝，就得说下内存结构了，内存就是一断特殊的电路，我们通过对内存的储存结构进行编码，某个内存地址对应内存某一个储存数据的地方，最小储存单元是 8 个 bit; 我们甚至可以把最小储存单元定义为 1 个 bit，但是这通常没有必要，因为我们需要针对每一个储存单元设置清除电路，而现实使用时的数据大多都会超过 1 个 bit，为了更小的储存单元而把电路变得更复杂完全不值得。
如果我们使用的数据超过最小储存单元，我们就把连续几个内存地址一起用了，记录首个地址，记录它使用个几个内存地址，也就是它的类型，比如int, 在大多数实现上，一般是 4 个字节，也就是连续占用 4 个地址，这些我们称之为基本类型。

而如果我们要储存的数据包含多种类型，我们也可以按照这种方式，按顺序存储下来，记录首个地址，记录它使用了那些地址，通常我们还会有一些对应的函数来操作这些对应的数据，我们通常把这种结构称作为对象，相关的操作函数就被称作方法。

当数据被作为函数的参数传递时，基本类型和对象有很明显的差异

1
2
3
4
5
6
7
8
9
10
11
let number = 4;
let obj = { num: 5 };

function test(a, b) {
  a = 0;
  b.num = 0;
}

test(number, obj);
console.log(number); // 4
console.log(obj); // {num: 0}

如果值是一个基本类型，那传递给函数的是它直接的值，也就是值的拷贝；而如果是对象，我们传递的是它的储存位置，也就是地址值，或者更抽象的说法，对象的引用，通过这个引用操作到真正的对象。

不过这其中有一个类型是个特例，那就是string，在 java 中string是一个对象，有各种操作方法，然而却表现的像基本类型一样，像是一个怪胎。在知乎中有许多相关的提问

  • [Java 语言中 String a=”a”;String b=”a”; 为什么 a==b 值为 true？]
  • [Java 到底是值传递还是引用传递？]
  • [如何理解 String 类型值的不可变？]

而在 js 中string中直接被定义为基本类型

  • [MDN-string]

实际上，字符串的确是一个对象，只不过为了更好用，我们把它改造成了一个“基本类型”，在我们日常使用中，我们一般很少把字符串进行重新修改，甚至不能修改，有大量场景直接把字符串作为 key 值，有大量密码验证场景使用的就是字符串，如果改动了，一切就乱套了。总而言之，string不应该能被修改

在老大哥 Java 的实现中，string是以常量池的形式维护，每次新建一个string，都会从常量池中寻找是否已存在相同的字符串，如果有直接就返回引用，如果没有则创建。得益于 string 的不可变性，才可以高效的复用相同字符串，甚至像基本类型一样直接比较。js 也实现了类似的设计。

而深拷贝，实际就是拷贝数据里所有可变的数据结构，把新数据和老数据隔离开，避免更改一处数据结构，而更改多处。也就是直接返回所有基本类型和不可变对象，递归复制所有可变的对象。

怎么进行深拷贝？

搞清除要复制什么东西，只是个起步，深拷贝能经常出现在面试题并不是由于它有多实用，工作中有多常见；主要深拷贝这一块儿会涉及到很多 js 的各种知识，各种边界条件，很能考察面试者的知识深度。

  1. 对于基本类型，直接返回
    js 中有 7 种基本类型，分别是 string, number, bigint, boolean, symbol, undefined, null,
    除了 null 和 function 以外，在typeof操作符下都显示为自己的类型名称，

    1
    2
    typeof null; // object
    typeof function () {}; // function

    我们可以自定义一个ownTypeof方法来正好的帮助我们在深拷贝时判断类型

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    const primitiveTypes = [
      "string",
      "number",
      "bigint",
      "boolean",
      "symbol",
      "undefined",
      "null",
    ];

    const ownTypeof = (value) => {
      const type = typeof value;
      if (primitiveTypes.includes(type) || value === null) {
        return "primitive";
      } else {
        return type;
      }
    };

    这些值就可以直接返回，不经过任何处理。

  2. 如果是对象，遍历对象的所有值
    这里也有许多门道，js 提供了太多根据 key 值循环处理的方法，

    • for in
      最常见的循环方法，遍历对象所有可遍历的字符串 key，无法遍历不可遍历的 key,会遍历到原型上的属性,无法遍历 symbol key,
    • Object.keys()
      基本等同于for in，除了不会遍历到原型上的属性
    • Reflect.ownKeys()
      获取对象所有的 key ，包括不可遍历的 key，symbol key, 等同于 Object.getOwnPropertyNames(target).concat(Object.getOwnPropertySymbols(target))。
      这里为了方便就直接用 Es6 的新方法Reflect.ownKeys()，简单又快速。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    const deepClone = (value) => {
      const typeofValue = ownTypeof(value);
      if (typeofValue === "primitive") return value;

      const keys = Reflect.ownKeys(value);
      const finalValue = {};
      for (const key of keys) {
        finalValue[key] = deepClone(value[key]);
      }
      return finalValue;
    };

  3. 解决环引用
    事实上这里我们的代码已经能勾复制大多数普通对象了，但是会碰见序列化时遇见的一个常见问题：环引用，我们通常会在使用 JSON 时遇到相似的错误

    1
    2
    3
    4
    let a = {};
    a.self = a;

    JSON.stringify(a); // Uncaught TypeError: Converting circular structure to JSON

    而在我们编写的深拷贝函数种，这会直接导致无限递归，直到栈溢出。

    1
    2
    3
    4
    let a = {};
    a.self = a;

    deepClone(a); // Maximum call stack size exceeded

    解决环引用其实很简单，栈溢出的原因是我们的函数在不停的重复拷贝一个相同的对象，而实际上，如果这是一个重复的对象，我们直接返回它自身的引用就可以了。我们可以通过建立新老对象引用的映射达到这一点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    const deepClone = (value, cache = new Map()) => {
      const typeofValue = ownTypeof(value);
      if (typeofValue === "primitive") return value;

      if (cache.has(value)) {
        return cache.get(value);
      }

      const keys = Reflect.ownKeys(value);
      const finalValue = {};
      cache.set(value, finalValue);
      for (const key of keys) {
        finalValue[key] = deepClone(value[key], cache);
      }
      return finalValue;
    };

    这里基本的一个深拷贝实际上基本就完成了，然而其实还有更多的 edge case, 也就是由于这个原因，实现一个深拷贝很难很难

  4. edge case

    • 是否考虑原型？
      在继承了 Java 一切皆对象的思想， js 每一个对象都有一个原型，实际上，我们直接返回它的原型，只把它当作单独的数据处理，因为拷贝原型的代价十分高昂

    • 是否复制函数？
      在任何实现里面，我相信函数都是不可拷贝的，也无需拷贝，这是因为函数生成以后，其执行的代码就不可更改了，这是一个不可变数据结构，我们理所当然的也不需要考虑再复制一份代码。
      除此之外还有一个重要原因是我们无法获得函数运行时的作用域，即使我们通过toString()获得源代码，也无法获得函数运行时的作用域。

    • 是否拷贝对象描述符？
      对象描述分别有两种，一种是数据描述符，一种是存取描述符，数据描述符是可复制的，存取描述符依赖于函数，无法复制

    • 如果复制内置对象？
      在 js 种，有许多对象是内置的，我们无法通过除其本身的构造函数外，创建出这个对象，比如最常见的数组

    1
    2
    let copyArray = deepClone([1, 2]);
    JSON.stringify(copyArray); // { "1": 1, "2": 2}

    即使我们拷贝了它的原型，它表现的也像是个普通对象，而不是一个数组，我们为其复制，length 属性也不会一同变换。
    这是由于数组是 js 的内置的对象，有独有的处理逻辑。
    类似的对象有许多许多：Date、RegExp、Map、Set、Blob，这也是整个过程最复杂的一块，不同的内置对象复制逻辑也不同。

    对于这种情况，则只能根据它的对象类型，使用其构造函数创建它。
    我们可以使用instanceof来确人对象是不是这些内置对象的实例，不过通常使用更方便的方法

    1
    2
    Object.prototype.toString.call([]); // [object Array]
    Object.prototype.toString.call(/test/); // [object RegExp]

    使用这个方式，我们可以直接读取这个对象类的名称，并进行相应处理。

使用上面的方式，基本就可以写出一个不错的深拷贝，在实际上编写中也是一个踩坑的过程，会了解许多日常忽视的 js 知识，对于一个面试题，称的上不错了。

但是实际使用中，我们应该尽量避免大量使用深拷贝，这是一种大量浪费内存的行为，如果你需要的是不可变性，更应该采用一些提供 Immutable 特性的库。

[Java 语言中 String a=”a”;String b=”a”; 为什么 a==b 值为 true？]: https://www.zhihu.com/question/57697842/answer/210583977 “Java 语言中 String a=”a”;String b=”a”; 为什么 a==b 值为 true？”
[Java 到底是值传递还是引用传递？]: https://www.zhihu.com/question/31203609/answer/576030121 “Java 到底是值传递还是引用传递？”
[如何理解 String 类型值的不可变？]: https://www.zhihu.com/question/20618891 “如何理解 String 类型值的不可变？”
[MDN-string]: https://developer.mozilla.org/en-US/docs/Glossary/string