如何实现一个完美的深拷贝库？

👆点击“博文视点Broadview”，获取更多书讯

lodash里的cloneDeep函数可以用来解决深拷贝的场景，但你有没有思考过lodash里的cloneDeep函数是如何实现的呢？

虽然我们可以直接使用lodash，但是学习深拷贝函数的实现原理仍然是非常有意义的，深拷贝也是一道非常经典的前端面试题，其可以考察面试者的很多方面，比如基本功、代码能力、逻辑能力。

深拷贝看似简单，但要想实现一个完美的深拷贝却并不容易，通过笔者的面试考察经验来看 ，只有 50%的人能够实现基础版本，能实现完美版本的竟然不到1%，这是因为深拷贝存在很多坑，比如：

• 你知道使用JSON.stringify来实现深拷贝是有bug的吗？

• 你会使用循环实现深拷贝吗？

• 如果拷贝的对象存在循环引用该怎么破解？

如果你回答不上来上面的问题，那么继续往下阅读吧，本文将破解深拷贝的谜题，由浅入深，环环相扣，总共涉及4种深拷贝方式，每种方式都有自己的特点和个性。

深拷贝 VS 浅拷贝

开始之前先科普一下什么是深拷贝，和深拷贝有关系的另一个术语——浅拷贝又是什么意思呢？

其实深拷贝和浅拷贝都是针对引用类型来说的，JS中的变量类型分为值类型（基本类型）和引用类型；对值类型进行复制操作会对值进行一份拷贝，而对引用类型赋值，则会进行地址的拷贝，最终两个变量指向同一份数据。示例代码如下。

// 引用类型指向同一份数据
var a = {c: 1};
var b = a;
a.c = 2;
console.log(a.c, b.c); // 2, 2 全是2，a b指向同一份数据

引用类型会导致a和b指向同一份数据，此时如果对其中一个进行修改，就会影响到另外一个，有时这可能不是我们想要的结果，如果对这种现象不清楚的话，还可能造成不必要的bug。

最简单的深拷贝

深拷贝的问题其实可以分解成两个问题：浅拷贝+递归。什么意思呢？假设我们有如下数据：

var a1 = {b: {c: {d: 1}};

使用递归实现深拷贝的示例代码如下：

function clone(source) {
    var target = {};
    for(var i in source) {
        if (source.hasOwnProperty(i)) {
            if (typeof source[i] === 'object') {
                target[i] = clone(source[i]); // 注意这里
            } else {
                target[i] = source[i];
            }
        }
    }

    return target;
}

大部分人都能写出上面的代码，但如果问上面的代码有什么问题的话，就很少有人答得上来了。聪明的你能找到问题吗？

其实上面的代码问题太多了，比如：

• 没有对参数做检验

• 判断是否对象的逻辑不够严谨

• 没有考虑数组的兼容

其实这三个都是小问题，递归方法最大的问题在于爆栈，当数据的层次很深时就会栈溢出。

下面的代码可以生成指定深度和每层广度的代码，这段代码我们后面还会再次用到。

function createData(deep, breadth) {
    var data = {};
    var temp = data;
    for (var i = 0; i < deep; i++) {
        temp = temp['data'] = {};
        for (var j = 0; j < breadth; j++) {
            temp[j] = j;
        }
    }
    return data;
}
createData(1, 3); // 1层深度，每层有3个数据 {data: {0: 0, 1: 1, 2: 2}}
createData(3, 0); // 3层深度，每层有0个数据 {data: {data: {data: {}}}}

当clone层级很深的时候就会出现栈溢出，但数据的广度不会造成溢出。

clone(createData(1000)); // ok
clone(createData(10000)); // Maximum call stack size exceeded
clone(createData(10, 100000)); // ok 广度不会溢出

其实大部分情况下不会出现这么深层级的数据，但这种方式还有一个致命的问题，就是循环引用。比如：

var a = {};
a.a = a;
clone(a) // Maximum call stack size exceeded 直接死循环了有没有，/(ㄒoㄒ)/~~

关于循环引用的问题，有两种解决思路：一种是循环检测，一种是暴力破解。

关于循环检测大家可以自己思考下；关于暴力破解，我们会在下面的内容中进行详细讲解。

一行代码的深拷贝

有些同学可能见过用系统自带的JSON来做深拷贝的例子，下面来看一下代码实现：

function cloneJSON(source) {
    return JSON.parse(JSON.stringify(source));
}

其实我第一次见到这个方法的时候由衷表示佩服，利用工具达到目的是非常聪明的做法！

下面来测试一下cloneJSON有没有溢出的问题，看起来cloneJSON内部也是使用递归的方式：

cloneJSON(createData(10000)); // Maximum call stack size exceeded

既然使用了递归，那么为什么存在循环引用时，并没有因为死循环而导致栈溢出呢？原来是JSON.stringify内部做了循环引用的检测，正是我们上面提到破解循环引用的第一种方法：循环检测。

var a = {};
a.a = a;
cloneJSON(a) // Uncaught TypeError: Converting circular structure to JSON

破解递归爆栈

其实破解递归爆栈的方法有两条路：第一种方法是消除尾递归，但在这个例子中行不通；第二种方法就是干脆不用递归，改用循环。当我提出用循环来实现时，基本上90%的前端都是写不出来代码的，下面来介绍一下实现思路。

举个例子，假设有如下的数据结构：

var a = {
    a1: 1,
    a2: {
        b1: 1,
        b2: {
            c1: 1
        }
    }
}

其实只要把数据横过来看，就非常明显地发现这就是树！

    a
  /   \
 a1   a2        
 |    / \         
 1   b1 b2     
     |   |        
     1  c1
         |
         1

用循环遍历一棵树需要借助一个栈，当栈为空时就遍历完了，栈里面会存储下一个需要拷贝的节点。

首先我们往栈里放入种子数据，key用来存储一个父元素的子元素拷贝对象。

然后遍历当前节点下的子元素，如果是对象，就放到栈里，否则直接拷贝。

function cloneLoop(x) {
    const root = {};
    const loopList = [{ parent: root, key: undefined, data: x }];
    while(loopList.length) {
        // 深度优先
        const node = loopList.pop();
        const parent = node.parent;
        const key = node.key;
        const data = node.data;
        // 初始化赋值目标，key为undefined则拷贝到父元素，否则拷贝到子元素
        let res = parent;
        if (typeof key !== 'undefined') {
            res = parent[key] = {};
        }
        for(let k in data) {
            if (data.hasOwnProperty(k)) {
                if (typeof data[k] === 'object') {
                    // 下一次循环
                    loopList.push({ parent: res, key: k, data: data[k] });
                } else {
                    res[k] = data[k];
                }
            }
        }
    }
    return root;
}

改用循环后，再也不会出现爆栈的问题了，但是对于循环引用依然无力应对！

破解循环引用

有没有一种办法可以破解循环引用呢？别着急，我们先来看另一个问题，上面的三种方法都存在的一个问题就是引用丢失，这在某些情况下也许是不能接受的。

举个例子，假如一个对象a下面的两个键值都引用同一个对象b，经过深拷贝后，a的两个键值会丢失引用关系，从而变成两个不同的对象o(╯□╰)o：

var b = {};
var a = {a1: b, a2: b};
a.a1 === a.a2 // true

var c = clone(a);
c.a1 === c.a2 // false

如果我们发现一个新对象就把这个对象和它的拷贝存下来，每次拷贝对象前，都先看一下这个对象是不是已经拷贝过了，如果拷贝过了，就不需要拷贝了，直接用原来的，这样我们就能够保留引用关系了✧(≖ ◡ ≖✿)嘿嘿~~

但是代码怎么写呢？o(╯□╰)o

别急，往下看！

其实和循环的代码大体一样，不一样的地方我用// ==========标注出来了。

引入一个数组uniqueList用来存储已经拷贝的数组，每次循环遍历时，先判断对象是否在uniqueList中了，如果在的话就不执行拷贝逻辑了。

find是一个抽象的函数，其实就是遍历uniqueList

// 保持引用关系
function cloneForce(x) {
    while(loopList.length) {
        // =============
        // 数据已经存在
        let uniqueData = find(uniqueList, data);
        if (uniqueData) {
            parent[key] = uniqueData.target;
            continue; // 中断本次循环
        }
        // 数据不存在
        // 保存源数据，在拷贝数据中对应的引用
        uniqueList.push({ source: data, target: res });
        // =============
        for(let k in data) {
            // 省略代码
        }
    }
    return root;
}

function find(arr, item) {
    for(let i = 0; i < arr.length; i++) {
        if (arr[i].source === item) {
            return arr[i];
        }
    }
    return null;
}

下面来验证一下效果：

var b = {};
var a = {a1: b, a2: b};
a.a1 === a.a2 // true

var c = cloneForce(a);
c.a1 === c.a2 // true

接下来再说一下如何破解循环引用。

等一下，上面的代码好像可以破解循环引用，赶紧验证一下：

var a = {};
a.a = a;

cloneForce(a)

惊不惊喜，(*^__^*) 嘻嘻……

看起来完美的cloneForce是不是就没有问题呢？

cloneForce有两个问题：

性能对比

上面的内容还是有点难度的，下面我们来点更有难度的，对比一下不同方法的性能。

我们先来做实验。通过数据可以看出影响性能的原因有两个：一个是深度，一个是每层的广度。

我们采用固定一个变量，只让一个变量变化的方式来测试性能。

测试的方法是在指定的时间内计算深拷贝执行的次数，次数越多，证明性能越好。

下面的runTime是测试代码的核心片段。在下面的例子中，我们可以测试在2秒内运行clone(createData(500, 1)的次数。

function runTime(fn, time) {
    var stime = Date.now();
    var count = 0;
    while(Date.now() - stime < time) {
        fn();
        count++;
    }
    return count;
}
runTime(function () { clone(createData(500, 1)) }, 2000);

下面来做第一个测试，将广度固定在100，深度由小到大变化，记录1秒内执行的次数。

将上面的数据做成表格可以发现一些规律：

• 随着深度变小，相互之间的差异在变小

• clone和cloneLoop的差别并不大

• cloneLoop > cloneForce > cloneJSON

我们先来分析一下各个方法的时间复杂度问题，对于各个方法要做的相同的事情，这里就不计算了，比如循环判断是否为对象等。

• clone时间 = 创建递归函数 + 每个对象处理时间

• cloneJSON时间 = 循环检测 + 每个对象处理时间 * 2 （递归转字符串 + 递归解析）

• cloneLoop时间 = 每个对象处理时间

• cloneForce时间 = 判断对象是否在缓存中 + 每个对象处理时间

cloneJSON的速度只有clone的50%。这很容易理解，因为其会多进行一次递归时间。

由于cloneForce要判断对象是否在缓存中，因此会导致速度变慢。我们来计算一下判断逻辑的时间复杂度，假设对象的个数是n，则其时间复杂度为O(n2)，对象的个数越多，cloneForce的速度会越慢。

1 + 2 + 3 ... + n = n^2/2 - 1

关于clone和cloneLoop这里有一点问题，看起来实验结果和推理结果不一致，其中必有蹊跷。

接下来做第二个测试，将深度固定在10000，广度固定为0，记录2秒内执行的次数。

排除宽度的干扰，来看看深度对各个方法的影响：

• 随着对象的增多，cloneForce的性能低下凸显

• cloneJSON的性能也大打折扣，这是因为循环检测占用了很多时间

• cloneLoop的性能高于clone，可以看出递归新建函数的时间和循环对象比起来可以忽略不计

下面我们来测试一下cloneForce的性能极限，这次我们测试运行指定次数需要的时间：

var data1 = createData(2000, 0);
var data2 = createData(4000, 0);
var data3 = createData(6000, 0);
var data4 = createData(8000, 0);
var data5 = createData(10000, 0);

cloneForce(data1)
cloneForce(data2)
cloneForce(data3)
cloneForce(data4)
cloneForce(data5)

通过测试发现，其时间成指数级增长，当对象个数大于万级别，就会有300ms以上的延迟。

总结

尺有所短，寸有所长，无关乎好坏优劣，其实每种方法都有自己的优缺点和适用场景，人尽其才，物尽其用，方是真理！

下面对各种方法进行对比，希望给大家提供一些帮助。

如今，本书已全面上线，如果你也想开发属于自己的JavaScript库，提升开发技能，精进自身开发技术，一定不可以错过本书哦~~

粉丝专享五折优惠，快快扫码抢购吧！

发布：刘恩惠
审核：陈歆懿
如果喜欢本文
欢迎 在看丨留言丨分享至朋友圈 三连

 热文推荐  

书单 | TIOBE 2022 年度编程语言，Java不行了吗？
C++ 夺冠！成为 TIOBE 2022 年度编程语言（附C&C++书单）
我们真的需要碳中和吗？
这本入门指南可以解答你做播客的所有疑问


▼点击阅读原文，了解本书详情~