如何實(shí)現(xiàn)一個(gè)完美的深拷貝庫？

??點(diǎn)擊“博文視點(diǎn)Broadview”，獲取更多書訊

lodash里的cloneDeep函數(shù)可以用來解決深拷貝的場(chǎng)景，但你有沒有思考過lodash里的cloneDeep函數(shù)是如何實(shí)現(xiàn)的呢？

雖然我們可以直接使用lodash，但是學(xué)習(xí)深拷貝函數(shù)的實(shí)現(xiàn)原理仍然是非常有意義的，深拷貝也是一道非常經(jīng)典的前端面試題，其可以考察面試者的很多方面，比如基本功、代碼能力、邏輯能力。

深拷貝看似簡(jiǎn)單，但要想實(shí)現(xiàn)一個(gè)完美的深拷貝卻并不容易，通過筆者的面試考察經(jīng)驗(yàn)來看 ，只有 50%的人能夠?qū)崿F(xiàn)基礎(chǔ)版本，能實(shí)現(xiàn)完美版本的竟然不到1%，這是因?yàn)樯羁截惔嬖诤芏嗫?，比如?/span>

• 你知道使用JSON.stringify來實(shí)現(xiàn)深拷貝是有bug的嗎？

• 你會(huì)使用循環(huán)實(shí)現(xiàn)深拷貝嗎？

• 如果拷貝的對(duì)象存在循環(huán)引用該怎么破解？

如果你回答不上來上面的問題，那么繼續(xù)往下閱讀吧，本文將破解深拷貝的謎題，由淺入深，環(huán)環(huán)相扣，總共涉及4種深拷貝方式，每種方式都有自己的特點(diǎn)和個(gè)性。

深拷貝 VS 淺拷貝

開始之前先科普一下什么是深拷貝，和深拷貝有關(guān)系的另一個(gè)術(shù)語——淺拷貝又是什么意思呢？

其實(shí)深拷貝和淺拷貝都是針對(duì)引用類型來說的，JS中的變量類型分為值類型（基本類型）和引用類型；對(duì)值類型進(jìn)行復(fù)制操作會(huì)對(duì)值進(jìn)行一份拷貝，而對(duì)引用類型賦值，則會(huì)進(jìn)行地址的拷貝，最終兩個(gè)變量指向同一份數(shù)據(jù)。示例代碼如下。

// 引用類型指向同一份數(shù)據(jù)
var a = {c: 1};
var b = a;
a.c = 2;
console.log(a.c, b.c); // 2, 2 全是2，a b指向同一份數(shù)據(jù)

引用類型會(huì)導(dǎo)致a和b指向同一份數(shù)據(jù)，此時(shí)如果對(duì)其中一個(gè)進(jìn)行修改，就會(huì)影響到另外一個(gè)，有時(shí)這可能不是我們想要的結(jié)果，如果對(duì)這種現(xiàn)象不清楚的話，還可能造成不必要的bug。

最簡(jiǎn)單的深拷貝

深拷貝的問題其實(shí)可以分解成兩個(gè)問題：淺拷貝+遞歸。什么意思呢？假設(shè)我們有如下數(shù)據(jù)：

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

使用遞歸實(shí)現(xiàn)深拷貝的示例代碼如下：

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;
}

大部分人都能寫出上面的代碼，但如果問上面的代碼有什么問題的話，就很少有人答得上來了。聰明的你能找到問題嗎？

其實(shí)上面的代碼問題太多了，比如：

• 沒有對(duì)參數(shù)做檢驗(yàn)

• 判斷是否對(duì)象的邏輯不夠嚴(yán)謹(jǐn)

• 沒有考慮數(shù)組的兼容

其實(shí)這三個(gè)都是小問題，遞歸方法最大的問題在于爆棧，當(dāng)數(shù)據(jù)的層次很深時(shí)就會(huì)棧溢出。

下面的代碼可以生成指定深度和每層廣度的代碼，這段代碼我們后面還會(huì)再次用到。

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個(gè)數(shù)據(jù) {data: {0: 0, 1: 1, 2: 2}}
createData(3, 0); // 3層深度，每層有0個(gè)數(shù)據(jù) {data: {data: {data: {}}}}

當(dāng)clone層級(jí)很深的時(shí)候就會(huì)出現(xiàn)棧溢出，但數(shù)據(jù)的廣度不會(huì)造成溢出。

clone(createData(1000)); // ok
clone(createData(10000)); // Maximum call stack size exceeded
clone(createData(10, 100000)); // ok 廣度不會(huì)溢出

其實(shí)大部分情況下不會(huì)出現(xiàn)這么深層級(jí)的數(shù)據(jù)，但這種方式還有一個(gè)致命的問題，就是循環(huán)引用。比如：

var a = {};
a.a = a;
clone(a) // Maximum call stack size exceeded 直接死循環(huán)了有沒有，/(ㄒoㄒ)/~~

關(guān)于循環(huán)引用的問題，有兩種解決思路：一種是循環(huán)檢測(cè)，一種是暴力破解。

關(guān)于循環(huán)檢測(cè)大家可以自己思考下；關(guān)于暴力破解，我們會(huì)在下面的內(nèi)容中進(jìn)行詳細(xì)講解。

一行代碼的深拷貝

有些同學(xué)可能見過用系統(tǒng)自帶的JSON來做深拷貝的例子，下面來看一下代碼實(shí)現(xiàn)：

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

其實(shí)我第一次見到這個(gè)方法的時(shí)候由衷表示佩服，利用工具達(dá)到目的是非常聰明的做法！

下面來測(cè)試一下cloneJSON有沒有溢出的問題，看起來cloneJSON內(nèi)部也是使用遞歸的方式：

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

既然使用了遞歸，那么為什么存在循環(huán)引用時(shí)，并沒有因?yàn)樗姥h(huán)而導(dǎo)致棧溢出呢？原來是JSON.stringify內(nèi)部做了循環(huán)引用的檢測(cè)，正是我們上面提到破解循環(huán)引用的第一種方法：循環(huán)檢測(cè)。

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

破解遞歸爆棧

其實(shí)破解遞歸爆棧的方法有兩條路：第一種方法是消除尾遞歸，但在這個(gè)例子中行不通；第二種方法就是干脆不用遞歸，改用循環(huán)。當(dāng)我提出用循環(huán)來實(shí)現(xiàn)時(shí)，基本上90%的前端都是寫不出來代碼的，下面來介紹一下實(shí)現(xiàn)思路。

舉個(gè)例子，假設(shè)有如下的數(shù)據(jù)結(jié)構(gòu)：

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

其實(shí)只要把數(shù)據(jù)橫過來看，就非常明顯地發(fā)現(xiàn)這就是樹！

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

用循環(huán)遍歷一棵樹需要借助一個(gè)棧，當(dāng)棧為空時(shí)就遍歷完了，棧里面會(huì)存儲(chǔ)下一個(gè)需要拷貝的節(jié)點(diǎn)。

首先我們往棧里放入種子數(shù)據(jù)，key用來存儲(chǔ)一個(gè)父元素的子元素拷貝對(duì)象。

然后遍歷當(dāng)前節(jié)點(diǎn)下的子元素，如果是對(duì)象，就放到棧里，否則直接拷貝。

function cloneLoop(x) {
    const root = {};
    const loopList = [{ parent: root, key: undefined, data: x }];
    while(loopList.length) {
        // 深度優(yōu)先
        const node = loopList.pop();
        const parent = node.parent;
        const key = node.key;
        const data = node.data;
        // 初始化賦值目標(biāo)，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') {
                    // 下一次循環(huán)
                    loopList.push({ parent: res, key: k, data: data[k] });
                } else {
                    res[k] = data[k];
                }
            }
        }
    }
    return root;
}

改用循環(huán)后，再也不會(huì)出現(xiàn)爆棧的問題了，但是對(duì)于循環(huán)引用依然無力應(yīng)對(duì)！

破解循環(huán)引用

有沒有一種辦法可以破解循環(huán)引用呢？別著急，我們先來看另一個(gè)問題，上面的三種方法都存在的一個(gè)問題就是引用丟失，這在某些情況下也許是不能接受的。

舉個(gè)例子，假如一個(gè)對(duì)象a下面的兩個(gè)鍵值都引用同一個(gè)對(duì)象b，經(jīng)過深拷貝后，a的兩個(gè)鍵值會(huì)丟失引用關(guān)系，從而變成兩個(gè)不同的對(duì)象o(╯□╰)o：

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

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

如果我們發(fā)現(xiàn)一個(gè)新對(duì)象就把這個(gè)對(duì)象和它的拷貝存下來，每次拷貝對(duì)象前，都先看一下這個(gè)對(duì)象是不是已經(jīng)拷貝過了，如果拷貝過了，就不需要拷貝了，直接用原來的，這樣我們就能夠保留引用關(guān)系了?(? ? ??)嘿嘿~~

但是代碼怎么寫呢？o(╯□╰)o

別急，往下看！

其實(shí)和循環(huán)的代碼大體一樣，不一樣的地方我用// ==========標(biāo)注出來了。

引入一個(gè)數(shù)組uniqueList用來存儲(chǔ)已經(jīng)拷貝的數(shù)組，每次循環(huán)遍歷時(shí)，先判斷對(duì)象是否在uniqueList中了，如果在的話就不執(zhí)行拷貝邏輯了。

find是一個(gè)抽象的函數(shù)，其實(shí)就是遍歷uniqueList

// 保持引用關(guān)系
function cloneForce(x) {
    while(loopList.length) {
        // =============
        // 數(shù)據(jù)已經(jīng)存在
        let uniqueData = find(uniqueList, data);
        if (uniqueData) {
            parent[key] = uniqueData.target;
            continue; // 中斷本次循環(huán)
        }
        // 數(shù)據(jù)不存在
        // 保存源數(shù)據(jù)，在拷貝數(shù)據(jù)中對(duì)應(yīng)的引用
        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;
}

下面來驗(yàn)證一下效果：

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

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

接下來再說一下如何破解循環(huán)引用。

等一下，上面的代碼好像可以破解循環(huán)引用，趕緊驗(yàn)證一下：

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

cloneForce(a)

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

看起來完美的cloneForce是不是就沒有問題呢？

cloneForce有兩個(gè)問題：

性能對(duì)比

上面的內(nèi)容還是有點(diǎn)難度的，下面我們來點(diǎn)更有難度的，對(duì)比一下不同方法的性能。

我們先來做實(shí)驗(yàn)。通過數(shù)據(jù)可以看出影響性能的原因有兩個(gè)：一個(gè)是深度，一個(gè)是每層的廣度。

我們采用固定一個(gè)變量，只讓一個(gè)變量變化的方式來測(cè)試性能。

測(cè)試的方法是在指定的時(shí)間內(nèi)計(jì)算深拷貝執(zhí)行的次數(shù)，次數(shù)越多，證明性能越好。

下面的runTime是測(cè)試代碼的核心片段。在下面的例子中，我們可以測(cè)試在2秒內(nèi)運(yùn)行clone(createData(500, 1)的次數(shù)。

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);

下面來做第一個(gè)測(cè)試，將廣度固定在100，深度由小到大變化，記錄1秒內(nèi)執(zhí)行的次數(shù)。

將上面的數(shù)據(jù)做成表格可以發(fā)現(xiàn)一些規(guī)律：

• 隨著深度變小，相互之間的差異在變小

• clone和cloneLoop的差別并不大

• cloneLoop > cloneForce > cloneJSON

我們先來分析一下各個(gè)方法的時(shí)間復(fù)雜度問題，對(duì)于各個(gè)方法要做的相同的事情，這里就不計(jì)算了，比如循環(huán)判斷是否為對(duì)象等。

• clone時(shí)間 = 創(chuàng)建遞歸函數(shù) + 每個(gè)對(duì)象處理時(shí)間

• cloneJSON時(shí)間 = 循環(huán)檢測(cè) + 每個(gè)對(duì)象處理時(shí)間 * 2 （遞歸轉(zhuǎn)字符串 + 遞歸解析）

• cloneLoop時(shí)間 = 每個(gè)對(duì)象處理時(shí)間

• cloneForce時(shí)間 = 判斷對(duì)象是否在緩存中 + 每個(gè)對(duì)象處理時(shí)間

cloneJSON的速度只有clone的50%。這很容易理解，因?yàn)槠鋾?huì)多進(jìn)行一次遞歸時(shí)間。

由于cloneForce要判斷對(duì)象是否在緩存中，因此會(huì)導(dǎo)致速度變慢。我們來計(jì)算一下判斷邏輯的時(shí)間復(fù)雜度，假設(shè)對(duì)象的個(gè)數(shù)是n，則其時(shí)間復(fù)雜度為O(n2)，對(duì)象的個(gè)數(shù)越多，cloneForce的速度會(huì)越慢。

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

關(guān)于clone和cloneLoop這里有一點(diǎn)問題，看起來實(shí)驗(yàn)結(jié)果和推理結(jié)果不一致，其中必有蹊蹺。

接下來做第二個(gè)測(cè)試，將深度固定在10000，廣度固定為0，記錄2秒內(nèi)執(zhí)行的次數(shù)。

排除寬度的干擾，來看看深度對(duì)各個(gè)方法的影響：

• 隨著對(duì)象的增多，cloneForce的性能低下凸顯

• cloneJSON的性能也大打折扣，這是因?yàn)檠h(huán)檢測(cè)占用了很多時(shí)間

• cloneLoop的性能高于clone，可以看出遞歸新建函數(shù)的時(shí)間和循環(huán)對(duì)象比起來可以忽略不計(jì)

下面我們來測(cè)試一下cloneForce的性能極限，這次我們測(cè)試運(yùn)行指定次數(shù)需要的時(shí)間：

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)

通過測(cè)試發(fā)現(xiàn)，其時(shí)間成指數(shù)級(jí)增長(zhǎng)，當(dāng)對(duì)象個(gè)數(shù)大于萬級(jí)別，就會(huì)有300ms以上的延遲。

總結(jié)

尺有所短，寸有所長(zhǎng)，無關(guān)乎好壞優(yōu)劣，其實(shí)每種方法都有自己的優(yōu)缺點(diǎn)和適用場(chǎng)景，人盡其才，物盡其用，方是真理！

下面對(duì)各種方法進(jìn)行對(duì)比，希望給大家提供一些幫助。

如今，本書已全面上線，如果你也想開發(fā)屬于自己的JavaScript庫，提升開發(fā)技能，精進(jìn)自身開發(fā)技術(shù)，一定不可以錯(cuò)過本書哦~~

粉絲專享五折優(yōu)惠，快快掃碼搶購吧！

發(fā)布：劉恩惠
審核：陳歆懿
如果喜歡本文
歡迎 在看丨留言丨分享至朋友圈 三連

 熱文推薦  

書單 | TIOBE 2022 年度編程語言，Java不行了嗎？
C++ 奪冠！成為 TIOBE 2022 年度編程語言（附C&C++書單）
我們真的需要碳中和嗎？
這本入門指南可以解答你做播客的所有疑問


▼點(diǎn)擊閱讀原文，了解本書詳情~