如何寫出一個驚豔面試官的深拷貝?

NO IMAGE

導讀

最近經常看到很多JavaScript手寫代碼的文章總結,裡面提供了很多JavaScript Api的手寫實現。

裡面的題目實現大多類似,而且說實話很多代碼在我看來是非常簡陋的,如果我作為面試官,看到這樣的代碼,在我心裡是不會合格的,本篇文章我拿最簡單的深拷貝來講一講。

看本文之前先問自己三個問題:

  • 你真的理解什麼是深拷貝嗎?

  • 在面試官眼裡,什麼樣的深拷貝才算合格?

  • 什麼樣的深拷貝能讓面試官感到驚豔?

本文由淺入深,帶你一步一步實現一個驚豔面試官的深拷貝。

本文測試代碼:github.com/ConardLi/Co…

例如:代碼clone到本地後,執行 node clone1.test.js查看測試結果。

建議結合測試代碼一起閱讀效果更佳。

深拷貝和淺拷貝的定義

深拷貝已經是一個老生常談的話題了,也是現在前端面試的高頻題目,但是令我吃驚的是有很多同學還沒有搞懂深拷貝和淺拷貝的區別和定義。例如前幾天給我提issue的同學:

如何寫出一個驚豔面試官的深拷貝?

很明顯這位同學把拷貝和賦值搞混了,如果你還對賦值、對象在內存中的存儲、變量和類型等等有什麼疑問,可以看看我這篇文章:juejin.im/post/5cec1b…

你只要少搞明白拷貝賦值的區別。

我們來明確一下深拷貝和淺拷貝的定義:

淺拷貝:

如何寫出一個驚豔面試官的深拷貝?

創建一個新對象,這個對象有著原始對象屬性值的一份精確拷貝。如果屬性是基本類型,拷貝的就是基本類型的值,如果屬性是引用類型,拷貝的就是內存地址 ,所以如果其中一個對象改變了這個地址,就會影響到另一個對象。

深拷貝:

如何寫出一個驚豔面試官的深拷貝?

將一個對象從內存中完整的拷貝一份出來,從堆內存中開闢一個新的區域存放新對象,且修改新對象不會影響原對象

話不多說,淺拷貝就不再多說,下面我們直入正題:

乞丐版

在不使用第三方庫的情況下,我們想要深拷貝一個對象,用的最多的就是下面這個方法。

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 map.get(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 對象是一組鍵/值對的集合,其中的鍵是弱引用的。其鍵必須是對象,而值可以是任意的。

什麼是弱引用呢?

在計算機程序設計中,弱引用與強引用相對,是指不能確保其引用的對象不會被垃圾回收器回收的引用。 一個對象若只被弱引用所引用,則被認為是不可訪問(或弱可訪問)的,並因此可能在任何時刻被回收。

我們默認創建一個對象:const obj = {},就默認創建了一個強引用的對象,我們只有手動將obj = null,它才會被垃圾回收機制進行回收,如果是弱引用對象,垃圾回收機制會自動幫我們回收。

舉個例子:

如果我們使用Map的話,那麼對象間是存在強引用關係的:

let obj = { name : 'ConardLi'}
const target = new Map();
target.set(obj,'code祕密花園');
obj = null;

雖然我們手動將obj,進行釋放,然是target依然對obj存在強引用關係,所以這部分內存依然無法被釋放。

再來看WeakMap

let obj = { name : 'ConardLi'}
const target = new WeakMap();
target.set(obj,'code祕密花園');
obj = null;

如果是WeakMap的話,targetobj存在的就是弱引用關係,當下一次垃圾回收機制執行時,這塊內存就會被釋放掉。

設想一下,如果我們要拷貝的對象非常龐大時,使用Map會對內存造成非常大的額外消耗,而且我們需要手動清除Map的屬性才能釋放這塊內存,而WeakMap會幫我們巧妙化解這個問題。

我也經常在某些代碼中看到有人使用WeakMap來解決循環引用問題,但是解釋都是模稜兩可的,當你不太瞭解WeakMap的真正作用時。我建議你也不要在面試中寫這樣的代碼,結果只能是給自己挖坑,即使是準備面試,你寫的每一行代碼也都是需要經過深思熟慮並且非常明白的。

能考慮到循環引用的問題,你已經向面試官展示了你考慮問題的全面性,如果還能用WeakMap解決問題,並很明確的向面試官解釋這樣做的目的,那麼你的代碼在面試官眼裡應該算是合格了。

性能優化

在上面的代碼中,我們遍歷數組和對象都使用了for in這種方式,實際上for in在遍歷時效率是非常低的,我們來對比下常見的三種循環for、while、for in的執行效率:

如何寫出一個驚豔面試官的深拷貝?

可以看到,while的效率是最好的,所以,我們可以想辦法把for in遍歷改變為while遍歷。

我們先使用while來實現一個通用的forEach遍歷,iteratee是遍歷的回掉函數,他可以接收每次遍歷的valueindex兩個參數:

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 map.get(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();

執行結果:

如何寫出一個驚豔面試官的深拷貝?

很明顯,我們的性能優化是有效的。

到這裡,你已經向面試官展示了,在寫代碼的時候你會考慮程序的運行效率,並且你具有通用函數的抽象能力。

其他數據類型

在上面的代碼中,我們其實只考慮了普通的objectarray兩種數據類型,實際上所有的引用類型遠遠不止這兩個,還有很多,下面我們先嚐試獲取對象準確的類型。

合理的判斷引用類型

首先,判斷是否為引用類型,我們還需要考慮functionnull兩種特殊的數據類型:

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]';

在上面的集中類型中,我們簡單將他們分為兩類:

  • 可以繼續遍歷的類型
  • 不可以繼續遍歷的類型

我們分別為它們做不同的拷貝。

可繼續遍歷的類型

上面我們已經考慮的objectarray都屬於可以繼續遍歷的類型,因為它們內存都還可以存儲其他數據類型的數據,另外還有MapSet等都是可以繼續遍歷的類型,這裡我們只考慮這四種,如果你有興趣可以繼續探索其他類型。

有序這幾種類型還需要繼續進行遞歸,我們首先需要獲取它們的初始化數據,例如上面的[]{},我們可以通過拿到constructor的方式來通用的獲取。

例如:const target = {}就是const target = new Object()的語法糖。另外這種方法還有一個好處:因為我們還使用了原對象的構造方法,所以它可以保留對象原型上的數據,如果直接使用普通的{},那麼原型必然是丟失了的。

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 map.get(target);
}
map.set(target, cloneTarget);
// 克隆set
if (type === setTag) {
target.forEach(value => {
cloneTarget.add(clone(value,map));
});
return cloneTarget;
}
// 克隆map
if (type === mapTag) {
target.forEach((value, key) => {
cloneTarget.set(key, clone(value,map));
});
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,
};

執行結果:

如何寫出一個驚豔面試官的深拷貝?

沒有問題,裡大功告成又進一步,下面我們繼續處理其他類型:

不可繼續遍歷的類型

其他剩餘的類型我們把它們統一歸類成不可處理的數據類型,我們依次進行處理:

BoolNumberStringStringDateError這幾種類型我們都可以直接用構造函數和原始數據創建一個新對象:

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和函數字符串來重新生成一個箭頭函數,注意這種方法是不適用於普通函數的。

我們可以使用正則來處理普通函數:

分別使用正則取出函數體和函數參數,然後使用new Function ([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;
}
};

執行結果:

如何寫出一個驚豔面試官的深拷貝?

最後

為了更好的閱讀,我們用一張圖來展示上面所有的代碼:

如何寫出一個驚豔面試官的深拷貝?

完整代碼:github.com/ConardLi/Co…

可見,一個小小的深拷貝還是隱藏了很多的知識點的。

千萬不要以最低的要求來要求自己,如果你只是為了應付面試中的一個題目,那麼你可能只會去準備上面最簡陋的深拷貝的方法。

但是面試官考察你的目的是全方位的考察你的思維能力,如果你寫出上面的代碼,可以體現你多方位的能力:

  • 基本實現
    • 遞歸能力
  • 循環引用
    • 考慮問題的全面性
    • 理解weakmap的真正意義
  • 多種類型
    • 考慮問題的嚴謹性
    • 創建各種引用類型的方法,JS API的熟練程度
    • 準確的判斷數據類型,對數據類型的理解程度
  • 通用遍歷:
    • 寫代碼可以考慮性能優化
    • 瞭解集中遍歷的效率
    • 代碼抽象能力
  • 拷貝函數:
    • 箭頭函數和普通函數的區別
    • 正則表達式熟練程度

看吧,一個小小的深拷貝能考察你這麼多的能力,如果面試官看到這樣的代碼,怎麼能夠不驚豔呢?

其實面試官出的所有題目你都可以用這樣的思路去考慮。不要為了應付面試而去背一些代碼,這樣在有經驗的面試官面前會都會暴露出來。你寫的每一段代碼都要經過深思熟慮,為什麼要這樣用,還能怎麼優化…這樣才能給面試官展現一個最好的你。

參考

小結

希望看完本篇文章能對你有如下幫助:

  • 理解深淺拷貝的真正意義
  • 能整我深拷貝的各個要點,對問題進行深入分析
  • 可以手寫一個比較完整的深拷貝

文中如有錯誤,歡迎在評論區指正,如果這篇文章幫助到了你,歡迎點贊和關注。

想閱讀更多優質文章、可關注我的github博客,你的star✨、點贊和關注是我持續創作的動力!

推薦關注我的微信公眾號【code祕密花園】,每天推送高質量文章,我們一起交流成長。

如何寫出一個驚豔面試官的深拷貝?

我們是字節跳動互娛研發團隊,包含抖音短視頻、抖音火山版、TikTok、Faceu、輕顏、剪映等,截止2020年1月,抖音日活(DAU)已經突破4億,並繼續保持高速增長。你會支持產品研發和相關架構工作,每一行代碼都能影響億萬用戶。

2021 屆校招內推碼:DRZUM5Z

官網投遞:job.toutiao.com/s/JR8SthH

相關文章

前端安全—你必須要注意的依賴安全漏洞

ConardLi的2019—尾聲和開始|年度徵文

前端工程化剖析npm的包管理機制

前端代碼質量圈複雜度原理和實踐