建站
咨詢
售后
建站咨詢
新聞中心
劃重點(diǎn)，這是一道面試必考題，我靠這道題刷掉了多少面試者(? ? ?)嘿嘿
首先這是一道非常棒的面試題，可以考察面試者的很多方面，比如基本功，代碼能力，邏輯能力，而且進(jìn)可攻，退可守，針對(duì)不同級(jí)別的人可以考察不同難度，比如漂亮妹子就出1題，要是個(gè)帥哥那就得上5了，(*^__^*) 嘻嘻……
無論面試者多么優(yōu)秀，漂亮的回答出問題，我總能夠?yàn)t灑的再拋出一個(gè)問題，看著面試者露出驚異的眼神，默默一轉(zhuǎn)身，深藏功與名。
本文我將給大家破解深拷貝的謎題，由淺入深，環(huán)環(huán)相扣，總共涉及4種深拷貝方式，每種方式都有自己的特點(diǎn)和個(gè)性。
深拷貝 VS 淺拷貝
再開始之前需要先給同學(xué)科普下什么是深拷貝，和深拷貝有關(guān)系的另個(gè)一術(shù)語是淺拷貝又是什么意思呢?如果對(duì)這部分部分內(nèi)容了解的同學(xué)可以跳過
其實(shí)深拷貝和淺拷貝都是針對(duì)的引用類型，JS中的變量類型分為值類型(基本類型)和引用類型;對(duì)值類型進(jìn)行復(fù)制操作會(huì)對(duì)值進(jìn)行一份拷貝，而對(duì)引用類型賦值，則會(huì)進(jìn)行地址的拷貝，最終兩個(gè)變量指向同一份數(shù)據(jù)
- // 基本類型
- var a = 1;
- var b = a;
- a = 2;
- console.log(a, b); // 2, 1 ，a b指向不同的數(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ù)
對(duì)于引用類型，會(huì)導(dǎo)致a b指向同一份數(shù)據(jù)，此時(shí)如果對(duì)其中一個(gè)進(jìn)行修改，就會(huì)影響到另外一個(gè)，有時(shí)候這可能不是我們想要的結(jié)果，如果對(duì)這種現(xiàn)象不清楚的話，還可能造成不必要的bug
那么如何切斷a和b之間的關(guān)系呢，可以拷貝一份a的數(shù)據(jù)，根據(jù)拷貝的層級(jí)不同可以分為淺拷貝和深拷貝，淺拷貝就是只進(jìn)行一層拷貝，深拷貝就是無限層級(jí)拷貝
- var a1 = {b: {c: {}};
- var a2 = shallowClone(a1); // 淺拷貝
- a2.b.c === a1.b.c // true
- var a3 = clone(a3); // 深拷貝
- a3.b.c === a1.b.c // false
淺拷貝的實(shí)現(xiàn)非常簡(jiǎn)單，而且還有多種方法，其實(shí)就是遍歷對(duì)象屬性的問題，這里只給出一種，如果看不懂下面的方法，或?qū)ζ渌椒ǜ信d趣，可以看我的這篇文章
- function shallowClone(source) {
- var target = {};
- for(var i in source) {
- if (source.hasOwnProperty(i)) {
- target[i] = source[i];
- }
- }
- return target;
- }
最簡(jiǎn)單的深拷貝
深拷貝的問題其實(shí)可以分解成兩個(gè)問題，淺拷貝+遞歸，什么意思呢?假設(shè)我們有如下數(shù)據(jù)
- var a1 = {b: {c: {d: 1}};
只需稍加改動(dòng)上面淺拷貝的代碼即可，注意區(qū)別
- 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;
- }
大部分人都能寫出上面的代碼，但當(dāng)我問上面的代碼有什么問題嗎?就很少有人答得上來了，聰明的你能找到問題嗎?
其實(shí)上面的代碼問題太多了，先來舉幾個(gè)例子吧
- 沒有對(duì)參數(shù)做檢驗(yàn)
- 判斷是否對(duì)象的邏輯不夠嚴(yán)謹(jǐn)
- 沒有考慮數(shù)組的兼容
(⊙o⊙)，下面我們來看看各個(gè)問題的解決辦法，首先我們需要抽象一個(gè)判斷對(duì)象的方法，其實(shí)比較常用的判斷對(duì)象的方法如下，其實(shí)下面的方法也有問題，但如果能夠回答上來那就非常不錯(cuò)了，如果完美的解決辦法感興趣，不妨看看這里吧
- function isObject(x) {
- return Object.prototype.toString.call(x) === '[object Object]';
- }
函數(shù)需要校驗(yàn)參數(shù)，如果不是對(duì)象的話直接返回
- function clone(source) {
- if (!isObject(source)) return source;
- // xxx
- }
關(guān)于第三個(gè)問題，嗯，就留給大家自己思考吧，本文為了減輕大家的負(fù)擔(dān)，就不考慮數(shù)組的情況了，其實(shí)ES6之后還要考慮set, map, weakset, weakmap，/(ㄒoㄒ)/~~
其實(shí)吧這三個(gè)都是小問題，其實(shí)遞歸方法最大的問題在于爆棧，當(dāng)數(shù)據(jù)的層次很深是就會(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í)很深的話就會(huì)棧溢出，但數(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)引用，舉個(gè)例子
- 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)容中詳細(xì)講解
一行代碼的深拷貝
有些同學(xué)可能見過用系統(tǒng)自帶的JSON來做深拷貝的例子，下面來看下代碼實(shí)現(xiàn)
- function cloneJSON(source) {
- return JSON.parse(JSON.stringify(source));
- }
其實(shí)我第一次簡(jiǎn)單這個(gè)方法的時(shí)候，由衷的表示佩服，其實(shí)利用工具，達(dá)到目的，是非常聰明的做法
下面來測(cè)試下cloneJSON有沒有溢出的問題，看起來cloneJSON內(nèi)部也是使用遞歸的方式
- cloneJSON(createData(10000)); // Maximum call stack size exceeded
既然是用了遞歸，那循環(huán)引用呢?并沒有因?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í)讓我很震驚
舉個(gè)例子，假設(shè)有如下的數(shù)據(jù)結(jié)構(gòu)
- var a = {
- a1: 1,
- a2: {
- b1: 1,
- b2: {
- c1: 1
- }
- }
- }
這不就是一個(gè)樹嗎，其實(shí)只要把數(shù)據(jù)橫過來看就非常明顯了
- a
- / \
- a1 a2
- | / \
- 1 b1 b2
- | |
- 1 c1
- |
- 1
用循環(huán)遍歷一棵樹，需要借助一個(gè)棧，當(dāng)棧為空時(shí)就遍歷完了，棧里面存儲(chǔ)下一個(gè)需要拷貝的節(jié)點(diǎn)
首先我們往棧里放入種子數(shù)據(jù)，key用來存儲(chǔ)放哪一個(gè)父元素的那一個(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)應(yīng)用呢?別著急，我們先來看另一個(gè)問題，上面的三種方法都存在的一個(gè)問題就是引用丟失，這在某些情況下也許是不能接受的
舉個(gè)例子，假如一個(gè)對(duì)象a，a下面的兩個(gè)鍵值都引用同一個(gè)對(duì)象b，經(jīng)過深拷貝后，a的兩個(gè)鍵值會(huì)丟失引用關(guān)系，從而變成兩個(gè)不同的對(duì)象，o(╯□╰)o
- var b = 1;
- 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) {
- // =============
- const uniqueList = []; // 用來去重
- // =============
- let root = {};
- // 循環(huán)數(shù)組
- 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] = {};
- }
- // =============
- // 數(shù)據(jù)已經(jīng)存在
- let uniqueData = find(uniqueList, data);
- if (uniqueData) {
- parent[key] = uniqueData.target;
- break; // 中斷本次循環(huán)
- }
- // 數(shù)據(jù)不存在
- // 保存源數(shù)據(jù)，在拷貝數(shù)據(jù)中對(duì)應(yīng)的引用
- uniqueList.push({
- source: data,
- target: res,
- });
- // =============
- 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;
- }
- function find(arr, item) {
- for(let i = 0; i < arr.length; i++) {
- if (arr[i].source === item) {
- return arr[i];
- }
- }
- return null;
- }
下面來驗(yàn)證一下效果，amazing
- var b = 1;
- 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è)問題
第一個(gè)問題，所謂成也蕭何，敗也蕭何，如果保持引用不是你想要的，那就不能用cloneForce了;
第二個(gè)問題，cloneForce在對(duì)象數(shù)量很多時(shí)會(huì)出現(xiàn)很大的問題，如果數(shù)據(jù)量很大不適合使用cloneForce
性能對(duì)比
上邊的內(nèi)容還是有點(diǎn)難度，下面我們來點(diǎn)更有難度的，對(duì)比一下不同方法的性能
我們先來做實(shí)驗(yàn)，看數(shù)據(jù)，影響性能的原因有兩個(gè)，一個(gè)是深度，一個(gè)是每層的廣度，我們采用固定一個(gè)變量，只讓一個(gè)變量變化的方式來測(cè)試性能
測(cè)試的方法是在指定的時(shí)間內(nèi)，深拷貝執(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ù)
| 深度 | clone | cloneJSON | cloneLoop | cloneForce |
|---|---|---|---|---|
| 500 | 351 | 212 | 338 | 372 |
| 1000 | 174 | 104 | 175 | 143 |
| 1500 | 116 | 67 | 112 | 82 |
| 2000 | 92 | 50 | 88 | 69 |
將上面的數(shù)據(jù)做成表格可以發(fā)現(xiàn)，一些規(guī)律
- 隨著深度變小，相互之間的差異在變小
- clone和cloneLoop的差別并不大
- cloneLoop > cloneForce > cloneJSON
我們先來分析下各個(gè)方法的時(shí)間復(fù)雜度問題，各個(gè)方法要做的相同事情，這里就不計(jì)算，比如循環(huán)對(duì)象，判斷是否為對(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ì)象是否在緩存中，而導(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ù)
| 寬度 | clone | cloneJSON | cloneLoop | cloneForce |
|---|---|---|---|---|
| 0 | 13400 | 3272 | 14292 | 989 |
排除寬度的干擾，來看看深度對(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ì)比，希望給大家提供一些幫助
| clone | cloneJSON | cloneLoop | cloneForce | |
|---|---|---|---|---|
| 難度 | ||||
| 兼容性 | ie6 | ie8 | ie6 | ie6 |
| 循環(huán)引用 | 一層 | 不支持 | 一層 | 支持 |
| 棧溢出 | 會(huì) | 會(huì) | 不會(huì) | 不會(huì) |
| 保持引用 | 否 | 否 | 否 | 是 |
| 適合場(chǎng)景 | 一般數(shù)據(jù)拷貝 | 一般數(shù)據(jù)拷貝 | 層級(jí)很多 | 保持引用關(guān)系 |
本文的靈感都來自于@jsmini/clone，如果大家想使用文中的4種深拷貝方式，可以直接使用@jsmini/clone這個(gè)庫(kù)
- // npm install --save @jsmini/clone
- import { clone, cloneJSON, cloneLoop, cloneForce } from '@jsmini/clone';
本文為了簡(jiǎn)單和易讀，示例代碼中忽略了一些邊界情況，如果想學(xué)習(xí)生產(chǎn)中的代碼，請(qǐng)閱讀@jsmini/clone的源碼
文章名稱：面試|深拷貝的終極探索（99%的人都不知道）
地址分享：http://www.dlmjj.cn/article/cdhjoep.html
