【進階4-3期】面試題之如何實現(xiàn)一個深拷貝

longmon 發(fā)布于2019-08-23 18:05 / 2784人閱讀

摘要：今天這篇文章我們來看看一道必會面試題，即如何實現(xiàn)一個深拷貝。木易楊注意這里使用上面測試用例測試一下一個簡單的深拷貝就完成了，但是這個實現(xiàn)還存在很多問題。

引言

上篇文章詳細介紹了淺拷貝 Object.assign，并對其進行了模擬實現(xiàn)，在實現(xiàn)的過程中，介紹了很多基礎(chǔ)知識。今天這篇文章我們來看看一道必會面試題，即如何實現(xiàn)一個深拷貝。本文會詳細介紹對象、數(shù)組、循環(huán)引用、引用丟失、Symbol 和遞歸爆棧等情況下的深拷貝實踐，歡迎閱讀。

第一步：簡單實現(xiàn)

其實深拷貝可以拆分成 2 步，淺拷貝 + 遞歸，淺拷貝時判斷屬性值是否是對象，如果是對象就進行遞歸操作，兩個一結(jié)合就實現(xiàn)了深拷貝。

根據(jù)上篇文章內(nèi)容，我們可以寫出簡單淺拷貝代碼如下。

// 木易楊
function cloneShallow(source) {
    var target = {};
    for (var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            target[key] = source[key];
        }
    }
    return target;
}

// 測試用例
var a = {
    name: "muyiy",
    book: {
        title: "You Don"t Know JS",
        price: "45"
    },
    a1: undefined,
    a2: null,
    a3: 123
}
var b = cloneShallow(a);

a.name = "高級前端進階";
a.book.price = "55";

console.log(b);
// { 
//   name: "muyiy", 
//   book: { title: "You Don"t Know JS", price: "55" },
//   a1: undefined,
//   a2: null,
//   a3: 123
// }

上面代碼是淺拷貝實現(xiàn)，只要稍微改動下，加上是否是對象的判斷并在相應(yīng)的位置使用遞歸就可以實現(xiàn)簡單深拷貝。

// 木易楊
function cloneDeep1(source) {
    var target = {};
    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (typeof source[key] === "object") {
                target[key] = cloneDeep1(source[key]); // 注意這里
            } else {
                target[key] = source[key];
            }
        }
    }
    return target;
}

// 使用上面測試用例測試一下
var b = cloneDeep1(a);
console.log(b);
// { 
//   name: "muyiy", 
//   book: { title: "You Don"t Know JS", price: "45" }, 
//   a1: undefined,
//   a2: {},
//   a3: 123
// }

一個簡單的深拷貝就完成了，但是這個實現(xiàn)還存在很多問題。

1、沒有對傳入?yún)?shù)進行校驗，傳入 null 時應(yīng)該返回 null 而不是 {}

2、對于對象的判斷邏輯不嚴(yán)謹(jǐn)，因為 typeof null === "object"

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

第二步：拷貝數(shù)組

我們來看下對于對象的判斷，之前在【進階3-3期】有過介紹，判斷方案如下。

// 木易楊
function isObject(obj) {
    return Object.prototype.toString.call(obj) === "[object Object]";
}

但是用在這里并不合適，因為我們要保留數(shù)組這種情況，所以這里使用 typeof 來處理。

// 木易楊
typeof null //"object"
typeof {} //"object"
typeof [] //"object"
typeof function foo(){} //"function" (特殊情況)

改動過后的 isObject 判斷邏輯如下。

// 木易楊
function isObject(obj) {
    return typeof obj === "object" && obj != null;
}

所以兼容數(shù)組的寫法如下。

// 木易楊
function cloneDeep2(source) {

    if (!isObject(source)) return source; // 非對象返回自身
      
    var target = Array.isArray(source) ? [] : {};
    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = cloneDeep2(source[key]); // 注意這里
            } else {
                target[key] = source[key];
            }
        }
    }
    return target;
}

// 使用上面測試用例測試一下
var b = cloneDeep2(a);
console.log(b);
// { 
//   name: "muyiy", 
//   book: { title: "You Don"t Know JS", price: "45" },
//   a1: undefined,
//   a2: null,
//   a3: 123
// }

第三步：循環(huán)引用

我們知道 JSON 無法深拷貝循環(huán)引用，遇到這種情況會拋出異常。

// 木易楊
// 此處 a 是文章開始的測試用例
a.circleRef = a;

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

1、使用哈希表

解決方案很簡單，其實就是循環(huán)檢測，我們設(shè)置一個數(shù)組或者哈希表存儲已拷貝過的對象，當(dāng)檢測到當(dāng)前對象已存在于哈希表中時，取出該值并返回即可。

// 木易楊
function cloneDeep3(source, hash = new WeakMap()) {

    if (!isObject(source)) return source; 
    if (hash.has(source)) return hash.get(source); // 新增代碼，查哈希表
      
    var target = Array.isArray(source) ? [] : {};
    hash.set(source, target); // 新增代碼，哈希表設(shè)值
    
    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = cloneDeep3(source[key], hash); // 新增代碼，傳入哈希表
            } else {
                target[key] = source[key];
            }
        }
    }
    return target;
}

測試一下，看看效果如何。

// 木易楊
// 此處 a 是文章開始的測試用例
a.circleRef = a;

var b = cloneDeep3(a);
console.log(b);
// {
//     name: "muyiy",
//     a1: undefined,
//    a2: null,
//     a3: 123,
//     book: {title: "You Don"t Know JS", price: "45"},
//     circleRef: {name: "muyiy", book: {…}, a1: undefined, a2: null, a3: 123, …}
// }

完美！

2、使用數(shù)組

這里使用了 ES6 中的 WeakMap 來處理，那在 ES5 下應(yīng)該如何處理呢？

也很簡單，使用數(shù)組來處理就好啦，代碼如下。

// 木易楊
function cloneDeep3(source, uniqueList) {

    if (!isObject(source)) return source; 
    if (!uniqueList) uniqueList = []; // 新增代碼，初始化數(shù)組
      
    var target = Array.isArray(source) ? [] : {};
    
    // ============= 新增代碼
    // 數(shù)據(jù)已經(jīng)存在，返回保存的數(shù)據(jù)
    var uniqueData = find(uniqueList, source);
    if (uniqueData) {
        return uniqueData.target;
    };
        
    // 數(shù)據(jù)不存在，保存源數(shù)據(jù)，以及對應(yīng)的引用
    uniqueList.push({
        source: source,
        target: target
    });
    // =============

    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = cloneDeep3(source[key], uniqueList); // 新增代碼，傳入數(shù)組
            } else {
                target[key] = source[key];
            }
        }
    }
    return target;
}

// 新增方法，用于查找
function find(arr, item) {
    for(var i = 0; i < arr.length; i++) {
        if (arr[i].source === item) {
            return arr[i];
        }
    }
    return null;
}

// 用上面測試用例已測試通過

現(xiàn)在已經(jīng)很完美的解決了循環(huán)引用這種情況，那其實還是一種情況是引用丟失，我們看下面的例子。

// 木易楊
var obj1 = {};
var obj2 = {a: obj1, b: obj1};

obj2.a === obj2.b; 
// true

var obj3 = cloneDeep2(obj2);
obj3.a === obj3.b; 
// false

引用丟失在某些情況下是有問題的，比如上面的對象 obj2，obj2 的鍵值 a 和 b 同時引用了同一個對象 obj1，使用 cloneDeep2 進行深拷貝后就丟失了引用關(guān)系變成了兩個不同的對象，那如何處理呢。

其實你有沒有發(fā)現(xiàn)，我們的 cloneDeep3 已經(jīng)解決了這個問題，因為只要存儲已拷貝過的對象就可以了。

// 木易楊
var obj3 = cloneDeep3(obj2);
obj3.a === obj3.b; 
// true

完美！

第四步：拷貝 Symbol

這個時候可能要搞事情了，那我們能不能拷貝 Symol 類型呢？

當(dāng)然可以，不過 Symbol 在 ES6 下才有，我們需要一些方法來檢測出 Symble 類型。

方法一：Object.getOwnPropertySymbols(...)

方法二：Reflect.ownKeys(...)

對于方法一可以查找一個給定對象的符號屬性時返回一個 ?symbol 類型的數(shù)組。注意，每個初始化的對象都是沒有自己的 symbol 屬性的，因此這個數(shù)組可能為空，除非你已經(jīng)在對象上設(shè)置了 symbol 屬性。（來自MDN）

var obj = {};
var a = Symbol("a"); // 創(chuàng)建新的symbol類型
var b = Symbol.for("b"); // 從全局的symbol注冊?表設(shè)置和取得symbol

obj[a] = "localSymbol";
obj[b] = "globalSymbol";

var objectSymbols = Object.getOwnPropertySymbols(obj);

console.log(objectSymbols.length); // 2
console.log(objectSymbols)         // [Symbol(a), Symbol(b)]
console.log(objectSymbols[0])      // Symbol(a)

對于方法二返回一個由目標(biāo)對象自身的屬性鍵組成的數(shù)組。它的返回值等同于Object.getOwnPropertyNames(target).concat(Object.getOwnPropertySymbols(target))。(來自MDN)

Reflect.ownKeys({z: 3, y: 2, x: 1}); // [ "z", "y", "x" ]
Reflect.ownKeys([]); // ["length"]

var sym = Symbol.for("comet");
var sym2 = Symbol.for("meteor");
var obj = {[sym]: 0, "str": 0, "773": 0, "0": 0,
           [sym2]: 0, "-1": 0, "8": 0, "second str": 0};
Reflect.ownKeys(obj);
// [ "0", "8", "773", "str", "-1", "second str", Symbol(comet), Symbol(meteor) ]
// 注意順序
// Indexes in numeric order, 
// strings in insertion order, 
// symbols in insertion order

方法一

思路就是先查找有沒有 Symbol 屬性，如果查找到則先遍歷處理 Symbol 情況，然后再處理正常情況，多出來的邏輯就是下面的新增代碼。

// 木易楊
function cloneDeep4(source, hash = new WeakMap()) {

    if (!isObject(source)) return source; 
    if (hash.has(source)) return hash.get(source); 
      
    let target = Array.isArray(source) ? [] : {};
    hash.set(source, target);
    
    // ============= 新增代碼
    let symKeys = Object.getOwnPropertySymbols(source); // 查找
    if (symKeys.length) { // 查找成功    
        symKeys.forEach(symKey => {
            if (isObject(source[symKey])) {
                target[symKey] = cloneDeep4(source[symKey], hash); 
            } else {
                target[symKey] = source[symKey];
            }    
        });
    }
    // =============
    
    for(let key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = cloneDeep4(source[key], hash); 
            } else {
                target[key] = source[key];
            }
        }
    }
    return target;
}

測試下效果

// 木易楊
// 此處 a 是文章開始的測試用例
var sym1 = Symbol("a"); // 創(chuàng)建新的symbol類型
var sym2 = Symbol.for("b"); // 從全局的symbol注冊?表設(shè)置和取得symbol

a[sym1] = "localSymbol";
a[sym2] = "globalSymbol";

var b = cloneDeep4(a);
console.log(b);
// {
//     name: "muyiy",
//     a1: undefined,
//    a2: null,
//     a3: 123,
//     book: {title: "You Don"t Know JS", price: "45"},
//     circleRef: {name: "muyiy", book: {…}, a1: undefined, a2: null, a3: 123, …},
//  [Symbol(a)]: "localSymbol",
//  [Symbol(b)]: "globalSymbol"
// }

完美！

方法二

// 木易楊
function cloneDeep4(source, hash = new WeakMap()) {

    if (!isObject(source)) return source; 
    if (hash.has(source)) return hash.get(source); 
      
    let target = Array.isArray(source) ? [] : {};
    hash.set(source, target);
    
      Reflect.ownKeys(source).forEach(key => { // 改動
        if (isObject(source[key])) {
            target[key] = cloneDeep4(source[key], hash); 
        } else {
            target[key] = source[key];
        }  
      });
    return target;
}

// 測試已通過

這里使用了 Reflect.ownKeys() 獲取所有的鍵值，同時包括 Symbol，對 source 遍歷賦值即可。

寫到這里已經(jīng)差不多了，我們再延伸下，對于 target 換一種寫法，改動如下。

// 木易楊
function cloneDeep4(source, hash = new WeakMap()) {

    if (!isObject(source)) return source; 
    if (hash.has(source)) return hash.get(source); 
      
    let target = Array.isArray(source) ? [...source] : { ...source }; // 改動 1
    hash.set(source, target);
    
      Reflect.ownKeys(target).forEach(key => { // 改動 2
        if (isObject(source[key])) {
            target[key] = cloneDeep4(source[key], hash); 
        } else {
            target[key] = source[key];
        }  
      });
    return target;
}

// 測試已通過

在改動 1 中，返回一個新數(shù)組或者新對象，獲取到源對象之后就可以如改動 2 所示傳入 target 遍歷賦值即可。

Reflect.ownKeys() 這種方式的問題在于不能深拷貝原型鏈上的數(shù)據(jù)，因為返回的是目標(biāo)對象自身的屬性鍵組成的數(shù)組。如果想深拷貝原型鏈上的數(shù)據(jù)怎么辦，那用 for..in 就可以了。

我們再介紹下兩個知識點，分別是構(gòu)造字面量數(shù)組時使用展開語法和構(gòu)造字面量對象時使用展開語法。（以下代碼示例來源于 MDN）

1、展開語法之字面量數(shù)組

這是 ES2015 （ES6） 才有的語法，可以通過字面量方式, 構(gòu)造新數(shù)組，而不再需要組合使用 push, splice, concat 等方法。

var parts = ["shoulders", "knees"]; 
var lyrics = ["head", ...parts, "and", "toes"]; 
// ["head", "shoulders", "knees", "and", "toes"]

這里的使用方法和參數(shù)列表的展開有點類似。

function myFunction(v, w, x, y, z) { }
var args = [0, 1];
myFunction(-1, ...args, 2, ...[3]);

返回的是新數(shù)組，對新數(shù)組修改之后不會影響到舊數(shù)組，類似于 arr.slice()。

var arr = [1, 2, 3];
var arr2 = [...arr]; // like arr.slice()
arr2.push(4); 

// arr2 此時變成 [1, 2, 3, 4]
// arr 不受影響

展開語法和 Object.assign() 行為一致, 執(zhí)行的都是淺拷貝（即只遍歷一層）。

var a = [[1], [2], [3]];
var b = [...a];
b.shift().shift(); // 1
// [[], [2], [3]]

這里 a 是多層數(shù)組，b 只拷貝了第一層，對于第二層依舊和 a 持有同一個地址，所以對 b 的修改會影響到 a。

2、展開語法之字面量對象

這是 ES2018 才有的語法，將已有對象的所有可枚舉屬性拷貝到新構(gòu)造的對象中，類似于 Object.assign() 方法。

var obj1 = { foo: "bar", x: 42 };
var obj2 = { foo: "baz", y: 13 };

var clonedObj = { ...obj1 };
// { foo: "bar", x: 42 }

var mergedObj = { ...obj1, ...obj2 };
// { foo: "baz", x: 42, y: 13 }

Object.assign() 函數(shù)會觸發(fā) setters，而展開語法不會。有時候不能替換或者模擬 Object.assign() 函數(shù)，因為會得到意想不到的結(jié)果，如下所示。

var obj1 = { foo: "bar", x: 42 };
var obj2 = { foo: "baz", y: 13 };
const merge = ( ...objects ) => ( { ...objects } );

var mergedObj = merge ( obj1, obj2);
// { 0: { foo: "bar", x: 42 }, 1: { foo: "baz", y: 13 } }

var mergedObj = merge ( {}, obj1, obj2);
// { 0: {}, 1: { foo: "bar", x: 42 }, 2: { foo: "baz", y: 13 } }

這里實際上是將多個解構(gòu)變?yōu)槭Ｓ鄥?shù)（ rest ），然后再將剩余參數(shù)展開為字面量對象.

第五步：破解遞歸爆棧

上面四步使用的都是遞歸方法，但是有一個問題在于會爆棧，錯誤提示如下。

// RangeError: Maximum call stack size exceeded

那應(yīng)該如何解決呢？其實我們使用循環(huán)就可以了，代碼如下。

function cloneDeep5(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;
}

由于篇幅問題就不過多介紹了，詳情請參考下面這篇文章。

深拷貝的終極探索（99%的人都不知道）

本期思考題

如何用 JS 實現(xiàn) JSON.parse?

參考

深入剖析 JavaScript 的深復(fù)制

深拷貝的終極探索（99%的人都不知道）

深入 js 深拷貝對象

MDN 之展開語法

MDN 之 Symbol

進階系列目錄

【進階1期】調(diào)用堆棧

【進階2期】作用域閉包

【進階3期】 this全面解析

【進階4期】深淺拷貝原理

【進階5期】原型Prototype

【進階6期】高階函數(shù)

【進階7期】事件機制

【進階8期】 Event Loop原理

【進階9期】 Promise原理

【進階10期】Async/Await原理

【進階11期】防抖/節(jié)流原理

【進階12期】模塊化詳解

【進階13期】ES6重難點

【進階14期】計算機網(wǎng)絡(luò)概述

【進階15期】瀏覽器渲染原理

【進階16期】webpack配置

【進階17期】webpack原理

【進階18期】前端監(jiān)控

【進階19期】跨域和安全

【進階20期】性能優(yōu)化

【進階21期】VirtualDom原理

【進階22期】Diff算法

【進階23期】MVVM雙向綁定

【進階24期】Vuex原理

【進階25期】Redux原理

【進階26期】路由原理

【進階27期】VueRouter源碼解析

【進階28期】ReactRouter源碼解析

交流

進階系列文章匯總?cè)缦?，?nèi)有優(yōu)質(zhì)前端資料，覺得不錯點個star。

https://github.com/yygmind/blog

我是木易楊，公眾號「高級前端進階」作者，跟著我每周重點攻克一個前端面試重難點。接下來讓我?guī)阕哌M高級前端的世界，在進階的路上，共勉！

云服務(wù)器 GPU云服務(wù)器深拷貝深拷貝和淺拷貝 javascript深拷貝 java實現(xiàn)文件拷貝

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/104666.html

發(fā)表評論

登陸后可評論

0條評論

longmon

男|高級講師

我要關(guān)注我要私信

TA的文章

stm32mini開發(fā)板lora模塊例程中中文字庫更新失敗的解決方案

閱讀 3669·2021-11-15 11:37
思維導(dǎo)圖整理大廠面試高頻數(shù)組補充1: 最接近的三數(shù)之和和三數(shù)之和的兩個不同之處, 力扣16

閱讀 2993·2021-11-12 10:36
手機主機名是什么-蘋果手機主機名是什么？

閱讀 4469·2021-09-22 15:51
Go 1.17 發(fā)布，主要更新了工具鏈、運行時和庫的實現(xiàn)

閱讀 2395·2021-08-27 16:18
h5文字超出，兩行顯示，超出顯示省略號

閱讀 902·2019-08-30 15:44
css單位

閱讀 2177·2019-08-30 10:58
Image Load Error Handler

閱讀 1794·2019-08-29 17:18
前端開發(fā)面試問題及答案整理

閱讀 3290·2019-08-28 18:25

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

【進階4-3期】面試題之如何實現(xiàn)一個深拷貝

相關(guān)文章

【進階4-1期】詳細解析賦值、淺拷貝和深拷貝的區(qū)別

【進階4-2期】Object.assign 原理及其實現(xiàn)

前端 100 問：能搞懂80%的請把簡歷給我

2019前端面試題（持續(xù)更新）

2019前端面試題（持續(xù)更新）

發(fā)表評論

0條評論

longmon

男|高級講師

TA的文章

stm32mini開發(fā)板lora模塊例程中中文字庫更新失敗的解決方案

思維導(dǎo)圖整理大廠面試高頻數(shù)組補充1: 最接近的三數(shù)之和和三數(shù)之和的兩個不同之處, 力扣16

手機主機名是什么-蘋果手機主機名是什么？

Go 1.17 發(fā)布，主要更新了工具鏈、運行時和庫的實現(xiàn)

h5文字超出，兩行顯示，超出顯示省略號

css單位

Image Load Error Handler

前端開發(fā)面試問題及答案整理

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

【進階4-3期】面試題之如何實現(xiàn)一個深拷貝

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！