如何寫出一個驚艷面試官的深拷貝
- 2019 年 10 月 10 日
- 筆記
這是ConardLi的第66篇原創，謝謝你的支援！
導讀
最近經常看到很多 JavaScript手寫程式碼的文章總結，裡面提供了很多 JavaScriptApi的手寫實現。
裡面的題目實現大多類似，而且說實話很多程式碼在我看來是非常簡陋的，如果我作為面試官，看到這樣的程式碼，在我心裡是不會合格的，本篇文章我拿最簡單的深拷貝來講一講。
看本文之前先問自己三個問題：
- 你真的理解什麼是深拷貝嗎？
- 在面試官眼裡，什麼樣的深拷貝才算合格？
- 什麼樣的深拷貝能讓面試官感到驚艷？
本文由淺入深，帶你一步一步實現一個驚艷面試官的深拷貝。
本文測試程式碼：https://github.com/ConardLi/ConardLi.github.io/tree/master/demo/deepClone
例如：程式碼clone到本地後，執行 node clone1.test.js查看測試結果。
建議結合測試程式碼一起閱讀效果更佳。
深拷貝和淺拷貝的定義
深拷貝已經是一個老生常談的話題了，也是現在前端面試的高頻題目，但是令我吃驚的是有很多同學還沒有搞懂深拷貝和淺拷貝的區別和定義。例如前幾天給我提 issue的同學：
很明顯這位同學把拷貝和賦值搞混了，如果你還對賦值、對象在記憶體中的存儲、變數和類型等等有什麼疑問，可以看看我這篇文章：
你只要少搞明白 拷貝和 賦值的區別。
我們來明確一下深拷貝和淺拷貝的定義：
淺拷貝：
創建一個新對象，這個對象有著原始對象屬性值的一份精確拷貝。如果屬性是基本類型，拷貝的就是基本類型的值，如果屬性是引用類型，拷貝的就是記憶體地址 ，所以如果其中一個對象改變了這個地址，就會影響到另一個對象。
深拷貝：
將一個對象從記憶體中完整的拷貝一份出來,從堆記憶體中開闢一個新的區域存放新對象,且修改新對象不會影響原對象
話不多說，淺拷貝就不再多說，下面我們直入正題：
乞丐版
在不使用第三方庫的情況下，我們想要深拷貝一個對象，用的最多的就是下面這個方法。
JSON.parse(JSON.stringify());
這種寫法非常簡單，而且可以應對大部分的應用場景，但是它還是有很大缺陷的，比如拷貝其他引用類型、拷貝函數、循環引用等情況。
顯然，面試時你只說出這樣的方法是一定不會合格的。
接下來，我們一起來手動實現一個深拷貝方法。
基礎版本
如果是淺拷貝的話，我們可以很容易寫出下面的程式碼：
function clone(target) { let cloneTarget = {}; for (const key in target) { cloneTarget[key] = target[key]; } return cloneTarget; };
創建一個新的對象，遍歷需要克隆的對象，將需要克隆對象的屬性依次添加到新對象上，返回。
如果是深拷貝的話，考慮到我們要拷貝的對象是不知道有多少層深度的，我們可以用遞歸來解決問題，稍微改寫上面的程式碼：
- 如果是原始類型，無需繼續拷貝，直接返回
- 如果是引用類型，創建一個新的對象，遍歷需要克隆的對象，將需要克隆對象的屬性執行深拷貝後依次添加到新對象上。
很容易理解，如果有更深層次的對象可以繼續遞歸直到屬性為原始類型，這樣我們就完成了一個最簡單的深拷貝：
function clone(target) { if (typeof target === 'object') { let cloneTarget = {}; for (const key in target) { cloneTarget[key] = clone(target[key]); } return cloneTarget; } else { return target; } };
我們可以打開測試程式碼中的clone1.test.js對下面的測試用例進行測試：
const target = { field1: 1, field2: undefined, field3: 'ConardLi', field4: { child: 'child', child2: { child2: 'child2' } } };
執行結果：
這是一個最基礎版本的深拷貝，這段程式碼可以讓你向面試官展示你可以用遞歸解決問題，但是顯然，他還有非常多的缺陷，比如，還沒有考慮數組。
考慮數組
在上面的版本中，我們的初始化結果只考慮了普通的 object，下面我們只需要把初始化程式碼稍微一變，就可以兼容數組了：
module.exports = function clone(target) { if (typeof target === 'object') { let cloneTarget = Array.isArray(target) ? [] : {}; for (const key in target) { cloneTarget[key] = clone(target[key]); } return cloneTarget; } else { return target; } };
在clone2.test.js中執行下面的測試用例：
const target = { field1: 1, field2: undefined, field3: { child: 'child' }, field4: [2, 4, 8] };
執行結果：
OK，沒有問題，你的程式碼又向合格邁進了一小步。
循環引用
我們執行下面這樣一個測試用例：
const target = { field1: 1, field2: undefined, field3: { child: 'child' }, field4: [2, 4, 8] }; target.target = target;
可以看到下面的結果：
很明顯，因為遞歸進入死循環導致棧記憶體溢出了。
原因就是上面的對象存在循環引用的情況，即對象的屬性間接或直接的引用了自身的情況：
解決循環引用問題，我們可以額外開闢一個存儲空間，來存儲當前對象和拷貝對象的對應關係，當需要拷貝當前對象時，先去存儲空間中找，有沒有拷貝過這個對象，如果有的話直接返回，如果沒有的話繼續拷貝，這樣就巧妙化解的循環引用的問題。
這個存儲空間，需要可以存儲 key-value形式的數據，且 key可以是一個引用類型，我們可以選擇 Map這種數據結構：
- 檢查
map中有無克隆過的對象 - 有 – 直接返回
- 沒有 – 將當前對象作為
key，克隆對象作為value進行存儲 - 繼續克隆
function clone(target, map = new Map()) { if (typeof target === 'object') { let cloneTarget = Array.isArray(target) ? [] : {}; if (map.get(target)) { return target; } map.set(target, cloneTarget); for (const key in target) { cloneTarget[key] = clone(target[key], map); } return cloneTarget; } else { return target; } };
再來執行上面的測試用例：
可以看到，執行沒有報錯，且 target屬性，變為了一個 Circular類型，即循環應用的意思。
接下來，我們可以使用， WeakMap提代 Map來使程式碼達到畫龍點睛的作用。
function clone(target, map = new WeakMap()) { // ... };
為什麼要這樣做呢？，先來看看 WeakMap的作用：
WeakMap 對象是一組鍵/值對的集合，其中的鍵是弱引用的。其鍵必須是對象，而值可以是任意的。
什麼是弱引用呢？
在電腦程式設計中，弱引用與強引用相對，是指不能確保其引用的對象不會被垃圾回收器回收的引用。一個對象若只被弱引用所引用，則被認為是不可訪問（或弱可訪問）的，並因此可能在任何時刻被回收。
我們默認創建一個對象：constobj={}，就默認創建了一個強引用的對象，我們只有手動將 obj=null，它才會被垃圾回收機制進行回收，如果是弱引用對象，垃圾回收機制會自動幫我們回收。
舉個例子：
如果我們使用 Map的話，那麼對象間是存在強引用關係的：
let obj = { name : 'ConardLi'} const target = { obj:'code秘密花園' } obj = null;
雖然我們手動將 obj，進行釋放，然是 target依然對 obj存在強引用關係，所以這部分記憶體依然無法被釋放。
再來看 WeakMap：
let obj = { name : 'ConardLi'} const target = new WeakMap(); target.set(obj,'code秘密花園'); obj = null;
如果是 WeakMap的話， target和 obj存在的就是弱引用關係，當下一次垃圾回收機制執行時，這塊記憶體就會被釋放掉。
設想一下，如果我們要拷貝的對象非常龐大時，使用 Map會對記憶體造成非常大的額外消耗，而且我們需要手動清除 Map的屬性才能釋放這塊記憶體，而 WeakMap會幫我們巧妙化解這個問題。
我也經常在某些程式碼中看到有人使用 WeakMap來解決循環引用問題，但是解釋都是模稜兩可的，當你不太了解 WeakMap的真正作用時。我建議你也不要在面試中寫這樣的程式碼，結果只能是給自己挖坑，即使是準備面試，你寫的每一行程式碼也都是需要經過深思熟慮並且非常明白的。
能考慮到循環引用的問題，你已經向面試官展示了你考慮問題的全面性，如果還能用 WeakMap解決問題，並很明確的向面試官解釋這樣做的目的，那麼你的程式碼在面試官眼裡應該算是合格了。
性能優化
在上面的程式碼中，我們遍曆數組和對象都使用了 forin這種方式，實際上 forin在遍歷時效率是非常低的，我們來對比下常見的三種循環 for、while、forin的執行效率：
可以看到， while的效率是最好的，所以，我們可以想辦法把 forin遍歷改變為 while遍歷。
我們先使用 while來實現一個通用的 forEach遍歷， iteratee是遍歷的回掉函數，他可以接收每次遍歷的 value和 index兩個參數：
function forEach(array, iteratee) { let index = -1; const length = array.length; while (++index < length) { iteratee(array[index], index); } return array; }
下面對我們的 cloen函數進行改寫：當遍曆數組時，直接使用 forEach進行遍歷，當遍歷對象時，使用 Object.keys取出所有的 key進行遍歷，然後在遍歷時把 forEach會調函數的 value當作 key使用：
function clone(target, map = new WeakMap()) { if (typeof target === 'object') { const isArray = Array.isArray(target); let cloneTarget = isArray ? [] : {}; if (map.get(target)) { return target; } map.set(target, cloneTarget); const keys = isArray ? undefined : Object.keys(target); forEach(keys || target, (value, key) => { if (keys) { key = value; } cloneTarget[key] = clone2(target[key], map); }); return cloneTarget; } else { return target; } }
下面，我們執行clone4.test.js分別對上一個克隆函數和改寫後的克隆函數進行測試：
const target = { field1: 1, field2: undefined, field3: { child: 'child' }, field4: [2, 4, 8], f: { f: { f: { f: { f: { f: { f: { f: { f: { f: { f: { f: {} } } } } } } } } } } }, }; target.target = target; console.time(); const result = clone1(target); console.timeEnd(); console.time(); const result2 = clone2(target); console.timeEnd();
執行結果：
很明顯，我們的性能優化是有效的。
到這裡，你已經向面試官展示了，在寫程式碼的時候你會考慮程式的運行效率，並且你具有通用函數的抽象能力。
其他數據類型
在上面的程式碼中，我們其實只考慮了普通的 object和 array兩種數據類型，實際上所有的引用類型遠遠不止這兩個，還有很多，下面我們先嘗試獲取對象準確的類型。
合理的判斷引用類型
首先，判斷是否為引用類型，我們還需要考慮 function和 null兩種特殊的數據類型：
function isObject(target) { const type = typeof target; return target !== null && (type === 'object' || type === 'function'); }
if (!isObject(target)) { return target; } // ...
獲取數據類型
我們可以使用 toString來獲取準確的引用類型：
每一個引用類型都有
toString方法，默認情況下，toString()方法被每個Object對象繼承。如果此方法在自定義對象中未被覆蓋，toString()返回"[object type]"，其中type是對象的類型。
注意，上面提到了如果此方法在自定義對象中未被覆蓋， toString才會達到預想的效果，事實上，大部分引用類型比如 Array、Date、RegExp等都重寫了 toString方法。
我們可以直接調用 Object原型上未被覆蓋的 toString()方法，使用 call來改變 this指向來達到我們想要的效果。
function getType(target) { return Object.prototype.toString.call(target); }
下面我們抽離出一些常用的數據類型以便後面使用：
const mapTag = '[object Map]'; const setTag = '[object Set]'; const arrayTag = '[object Array]'; const objectTag = '[object Object]'; const boolTag = '[object Boolean]'; const dateTag = '[object Date]'; const errorTag = '[object Error]'; const numberTag = '[object Number]'; const regexpTag = '[object RegExp]'; const stringTag = '[object String]'; const symbolTag = '[object Symbol]';
在上面的集中類型中，我們簡單將他們分為兩類：
- 可以繼續遍歷的類型
- 不可以繼續遍歷的類型
我們分別為它們做不同的拷貝。
可繼續遍歷的類型
上面我們已經考慮的 object、 array都屬於可以繼續遍歷的類型，因為它們記憶體都還可以存儲其他數據類型的數據，另外還有 Map， Set等都是可以繼續遍歷的類型，這裡我們只考慮這四種，如果你有興趣可以繼續探索其他類型。
有序這幾種類型還需要繼續進行遞歸，我們首先需要獲取它們的初始化數據，例如上面的 []和 {}，我們可以通過拿到 constructor的方式來通用的獲取。
例如：consttarget={}就是 consttarget=newObject()的語法糖。另外這種方法還有一個好處：因為我們還使用了原對象的構造方法，所以它可以保留對象原型上的數據，如果直接使用普通的 {}，那麼原型必然是丟失了的。
function getInit(target) { const Ctor = target.constructor; return new Ctor(); }
下面，我們改寫 clone函數，對可繼續遍歷的數據類型進行處理：
function clone(target, map = new WeakMap()) { // 克隆原始類型 if (!isObject(target)) { return target; } // 初始化 const type = getType(target); let cloneTarget; if (deepTag.includes(type)) { cloneTarget = getInit(target, type); } // 防止循環引用 if (map.get(target)) { return target; } map.set(target, cloneTarget); // 克隆set if (type === setTag) { target.forEach(value => { cloneTarget.add(clone(value)); }); return cloneTarget; } // 克隆map if (type === mapTag) { target.forEach((value, key) => { cloneTarget.set(key, clone(value)); }); return cloneTarget; } // 克隆對象和數組 const keys = type === arrayTag ? undefined : Object.keys(target); forEach(keys || target, (value, key) => { if (keys) { key = value; } cloneTarget[key] = clone(target[key], map); }); return cloneTarget; }
我們執行clone5.test.js對下面的測試用例進行測試：
const target = { field1: 1, field2: undefined, field3: { child: 'child' }, field4: [2, 4, 8], empty: null, map, set, };
執行結果：
沒有問題，里大功告成又進一步，下面我們繼續處理其他類型：
不可繼續遍歷的類型
其他剩餘的類型我們把它們統一歸類成不可處理的數據類型，我們依次進行處理：
Bool、 Number、 String、 String、 Date、 Error這幾種類型我們都可以直接用構造函數和原始數據創建一個新對象：
function cloneOtherType(targe, type) { const Ctor = targe.constructor; switch (type) { case boolTag: case numberTag: case stringTag: case errorTag: case dateTag: return new Ctor(targe); case regexpTag: return cloneReg(targe); case symbolTag: return cloneSymbol(targe); default: return null; } }
克隆 Symbol類型：
function cloneSymbol(targe) { return Object(Symbol.prototype.valueOf.call(targe)); } 克隆正則： function cloneReg(targe) { const reFlags = /w*$/; const result = new targe.constructor(targe.source, reFlags.exec(targe)); result.lastIndex = targe.lastIndex; return result; }
實際上還有很多數據類型我這裡沒有寫到，有興趣的話可以繼續探索實現一下。
能寫到這裡，面試官已經看到了你考慮問題的嚴謹性，你對變數和類型的理解，對 JS API的熟練程度，相信面試官已經開始對你刮目相看了。
克隆函數
最後，我把克隆函數單獨拎出來了，實際上克隆函數是沒有實際應用場景的，兩個對象使用一個在記憶體中處於同一個地址的函數也是沒有任何問題的，我特意看了下 lodash對函數的處理：
const isFunc = typeof value == 'function' if (isFunc || !cloneableTags[tag]) { return object ? value : {} }
可見這裡如果發現是函數的話就會直接返回了，沒有做特殊的處理，但是我發現不少面試官還是熱衷於問這個問題的，而且據我了解能寫出來的少之又少。。。
實際上這個方法並沒有什麼難度，主要就是考察你對基礎的掌握紮實不紮實。
首先，我們可以通過 prototype來區分下箭頭函數和普通函數，箭頭函數是沒有 prototype的。
我們可以直接使用 eval和函數字元串來重新生成一個箭頭函數，注意這種方法是不適用於普通函數的。
我們可以使用正則來處理普通函數：
分別使用正則取出函數體和函數參數，然後使用 newFunction([arg1[,arg2[,...argN]],]functionBody)構造函數重新構造一個新的函數：
function cloneFunction(func) { const bodyReg = /(?<={)(.|n)+(?=})/m; const paramReg = /(?<=().+(?=)s+{)/; const funcString = func.toString(); if (func.prototype) { console.log('普通函數'); const param = paramReg.exec(funcString); const body = bodyReg.exec(funcString); if (body) { console.log('匹配到函數體：', body[0]); if (param) { const paramArr = param[0].split(','); console.log('匹配到參數：', paramArr); return new Function(...paramArr, body[0]); } else { return new Function(body[0]); } } else { return null; } } else { return eval(funcString); } }
最後，我們再來執行clone6.test.js對下面的測試用例進行測試：
const map = new Map(); map.set('key', 'value'); map.set('ConardLi', 'code秘密花園'); const set = new Set(); set.add('ConardLi'); set.add('code秘密花園'); const target = { field1: 1, field2: undefined, field3: { child: 'child' }, field4: [2, 4, 8], empty: null, map, set, bool: new Boolean(true), num: new Number(2), str: new String(2), symbol: Object(Symbol(1)), date: new Date(), reg: /d+/, error: new Error(), func1: () => { console.log('code秘密花園'); }, func2: function (a, b) { return a + b; } };
執行結果：
最後
為了更好的閱讀，我們用一張圖來展示上面所有的程式碼：
完整程式碼：https://github.com/ConardLi/ConardLi.github.io/blob/master/demo/deepClone/src/clone_6.js
可見，一個小小的深拷貝還是隱藏了很多的知識點的。
千萬不要以最低的要求來要求自己，如果你只是為了應付面試中的一個題目，那麼你可能只會去準備上面最簡陋的深拷貝的方法。
但是面試官考察你的目的是全方位的考察你的思維能力，如果你寫出上面的程式碼，可以體現你多方位的能力：
- 基本實現
- 遞歸能力
- 循環引用
- 考慮問題的全面性
- 理解weakmap的真正意義
- 多種類型
- 考慮問題的嚴謹性
- 創建各種引用類型的方法，JS API的熟練程度
- 準確的判斷數據類型，對數據類型的理解程度
- 通用遍歷：
- 寫程式碼可以考慮性能優化
- 了解集中遍歷的效率
- 程式碼抽象能力
- 拷貝函數：
- 箭頭函數和普通函數的區別
- 正則表達式熟練程度
看吧，一個小小的深拷貝能考察你這麼多的能力，如果面試官看到這樣的程式碼，怎麼能夠不驚艷呢？
其實面試官出的所有題目你都可以用這樣的思路去考慮。不要為了應付面試而去背一些程式碼，這樣在有經驗的面試官面前會都會暴露出來。你寫的每一段程式碼都要經過深思熟慮，為什麼要這樣用，還能怎麼優化…這樣才能給面試官展現一個最好的你。
參考
- WeakMap
- lodash
小結
希望看完本篇文章能對你有如下幫助：
- 理解深淺拷貝的真正意義
- 能整我深拷貝的各個要點，對問題進行深入分析
- 可以手寫一個比較完整的深拷貝
文中如有錯誤，歡迎在評論區指正，如果這篇文章幫助到了你，歡迎點贊和關注。
完
