手写实现深度拷贝

请叫我大苏

发布于 2019-11-03 14:40:15

1K0

发布于 2019-11-03 14:40:15

文章被收录于专栏：AndroidTv

本文参考：面试题之如何实现一个深拷贝

基础理论

拷贝的基础是赋值，在 js 中，将一个变量赋值给另一个变量时，有两种场景：

基本类型数据的值拷贝
引用类型数据的引用拷贝

var a = 1;
var b = {a: 1};

var a1 = a;
var b1 = b;
var b2 = b;

a1 = 2;
a; // 1   原始类型的赋值是值拷贝，两不影响

b1 = null;
b; // {a: 1}  对象类型的赋值是引用拷贝，修改引用指向，对原变量无影响
b2.a = 2; 
b; // {a: 2}  对象类型的赋值是引用拷贝，指向同一份对象，修改对象属性，会对原变量指向的对象有所影响

那么，对一个对象进行拷贝，无非就是对对象的属性进行拷贝，按照拷贝处理的方式不同，可分为浅拷贝和深拷贝：

浅拷贝是只拷贝对象的第一层属性
深拷贝则是无限层次的拷贝对象的属性，只要属性值不是基本类型，就继续深度遍历进去

浅拷贝的双方仍旧有所关联，因为有些属性只是引用拷贝而已，都是指向同一份数据，一方修改就会影响到另一方；

深拷贝的双方则是相互独立，互不影响。

在 js 中，内置的各种复制、拷贝的 API，都是浅拷贝，比如：Object.assign()，{...a}，[].slice() 等等。

如果项目中有需要使用到深拷贝，那么就只能是自行实现，或者使用三方库。

实现深拷贝

有人可能会觉得自己实现个深拷贝很简单，毕竟都已经知道浅拷贝只拷贝一层，那深拷贝不就等效于浅拷贝 + 递归？

function cloneDeep(source) {
    let target = {};
    for (let key in source) {
        if (typeof source[key] === 'object') {
            target[key] = cloneDeep(source[key]);
        } else {
            target[key] = source[key];
        }
    }
    return target;
}

那么，上面的深拷贝实现有问题吗？

虽然从概念上，深拷贝就是需要层层遍历对象属性，只拷贝基本类型数据，对象类型再继续深入遍历，反应到代码上，的确也就是像上面的处理：基本类型值拷贝 + 对象类型递归处理。

但上例的代码，欠缺各种细节和场景的处理。

比如说：

参数 source 的校验
typeof null 也是 object 的过滤处理
属性 key 值类型是 Symbol 的场景
source 是数组时的兼容处理
循环引用的场景
引用关系丢失问题
递归栈溢出的场景
等等

所以，本篇想讲的深拷贝实现，就是希望能把这些细节和特殊场景考虑进去，同时，也会介绍一些不同的实现方案。

通用版

想要实现通用版，其实也就是要将上面列出来的细节和各自场景考虑进行，思考每个问题该如何解决：

参数 source 的校验 & null 的过滤处理

毕竟如果不是对象的话，也就没有什么拷贝的意义了，直接原值返回即可，所以这里需要对参数进行是否是对象的判断处理。

使用 typeof 的话，由于 null 也是 object，所以还需要将 null 的场景过滤掉；

function isObject(o) {
    return typeof o === 'object' && o !== null;
}

Symbol 的处理

symbol 是 ES6 中新增的特性，使用 for in 方式遍历不到，所以需要 ES6 中新增的遍历方式：

Object.getOwnPropertySymbols()
Reflect.ownKeys()

前者是单独遍历对象键值类型为 Symbol 的属性，使用这种方式的话，等于是分两次处理对象，先深拷贝一次 Symbol 属性，再深拷贝一次其他属性。

后者 Reflect.ownKeys() 可以遍历到对象所有的自有属性，包括 Symbol 属性，它相当于 Object.getOwnPropertyNames() 和 Object.getOwnPropertySymbols() 的并集。使用这种方式的话，等于替换掉 for in 的遍历方式。

数组的兼容处理

这个的意思是说，需要区分当前拷贝的对象是数组还是对象，毕竟总不能将数组的数据拷贝到对象里把，所以 target 的初始化需要处理一下，区分数组的场景：

let target = Array.isArray(source) ? [] : {};

循环引用 & 引用关系丢失问题

这种场景还是用代码来解释比较清晰：

var a = {};
var o = {
    a: a,
    b: a
}
o.c = o; 
o; // {a: {}, b: {}, c: {a: {}, b: {}, c:{...}}}
o.a === o.b; // true

var o1 = cloneDeep(o); // 栈溢出异常，Maximum call stack size
// 把 o.c = o 注释掉， o1.a === o1.b  输出 false，原本的引用关系丢失了

循环引用指的是，对象的某个属性又指向了对象本身，这样就造成了具有无限深层次的结构，递归时自然就会栈溢出了。

引用关系丢失指的是，对象的多个属性都指向同一个某对象，但经过深拷贝后，这多个属性却都指向了不同的对象，虽然被指向的这些对象的值是一致的。

造成这两个问题的根本原因，其实就是，对于对象数据，每次都会重新创建一个新对象来存储拷贝过来的值。

所以，解决这两个问题，其实也很简单，就是不要每次都重新创建新的对象，复用已创建的对象即可。

比如说，在遍历拷贝 o.a 时，先创建一个新对象拷贝了 o.a，之后再处理 o.b 时，发现 o.b 也指向 o.a，那么就不要重新创建对象来拷贝了，直接将引用指向之前拷贝 o.a 时创建的对象即可，这样引用关系就保留下来了。

这样即使遇到循环引用，就将引用指向拷贝生成的新对象即可，就不会有栈溢出的场景了。

代码上的话，可以利用 ES6 的 map 数据结构，因为可以直接让 source 对象作为 key 来存储。

否则就得自己用数组存储，但由于数组 key 值也只能是字符串和 Symbol，所以映射关系只能自己用对象存，这么一来，还得自己写寻找的逻辑。

function cloneDeep(source, hash = new WeakMap()) {
    // ... 省略
    if (hash.get(source)) {
        return hash.get(source)
    }
    let target = Array.isArray(source) ? [] : {};
    hash.set(source, target);
    
    // target[key] = cloneDeep(source[key], hash); // 对象类型递归调用时，将 hash 传递进去 
    // .., 省略
}

function cloneDeep(source, hash = []) {
    // ... 省略
    let cache = hash.find(v => v.source === source);
    if (cache) {
        return cache.target;
    }
    let target = Array.isArray(source) ? [] : {};
    hash.push({ source: source, target: target });
    
    // target[key] = cloneDeep(source[key], hash); // 对象类型递归调用时，将 hash 传递进去
    // ... 省略
}

栈溢出问题

递归的最大问题，就是怕遇到栈溢出，一旦递归层次多的话。

循环引用会导致递归层次过多而栈溢出，但可以通过已拷贝对象的缓存来解决这个问题。

但如果对象的结构层次过多时，这种现象就无法避免了，就必须来解决栈溢出问题了。

解决栈溢出两种思路：

尾递归优化
不用递归，改成循环实现

尾递归优化是指函数的最后一行代码都是调用自身函数，如果可以修改成这种模式，就可以达到尾递归优化。而这种方式之所以可以解决栈溢出，是因为，函数的最后一行都是调用自身函数，那其实就意味着当前函数执行上下文其实没必要保留了，之所以会栈溢出，就是执行上下文栈中存在过多函数执行上下文。

每次调用函数都会创建一个函数执行上下文（EC），并放入执行上下文栈（ECS）中，当函数执行结束时，就将函数执行上下文移出栈。

所以，函数内部嵌套调用函数时，就会造成 ECS 中有过多的 EC，递归是不断的在函数内调用自己，所以一旦层次过多，必然导致 ECS 爆表，栈溢出。

而尾递归，让递归函数的最后一行执行的代码都是调用自身，这就意味着，在递归调用自身时，当前函数的职责已结束，那么 EC 其实就可以从 ECS 中移出了，这样一来，不管递归层次多深，始终都只有一个递归函数的 EC 在 ECS 中，自然就不会造成栈溢出。

不过尾递归优化有个局限性，只在严格模式下才开启，因为非严格模式下，函数内部有 arguments 和 caller 两个变量会追踪调用栈，尾递归优化会导致这两变量失真报错，所以只在严格模式下才开启。

而且，正常递归函数改写成尾递归，基本操作都是将局部变量变成参数，保证最后执行的一行代码是调用自身。但由于深拷贝场景，是在遍历属性过程中递归调用自身，调用完自身后面肯定还需要遍历处理其他属性，所以无法做到最后一行调用自身的要求，也就无法改写成尾递归形式。

所以，尾递归优化这种方案放弃。

用循环替代递归是另外一种解决栈溢出方案，这种方式其实就是思考，原本需要使用递归的方式，有没有办法通过循环来实现。循环的话，也就不存在什么嵌套调用函数，也就不存在栈溢出的问题了。

对象的属性结构，其实就是一颗树结构，递归方案的深拷贝，其实也就是以深度优先来遍历对象的属性树。

但遍历树结构数据，除了使用递归方案外，也可以使用循环来遍历，但是需要借助相应的数据结构。

当使用循环来遍历树，且深度优先时，那么就需要借助栈；如果是广度优先时，则是需要借助队列。

具体做法则是，一次只处理一个节点，处理节点时遍历取出它所有子节点，代码上也就是双层循环，比如说：

从树根节点开始，遍历它的第一层子节点，把这些节点都放入栈或队列中，结束本次循环；
下次循环开始，取出栈顶或队头节点处理：若该节点还有子节点，那么遍历取出所有子节点，放入栈或队列中，结束本次循环；
重复第2步，直至栈或队列中无节点；
如果是用栈辅助，则对应深度优先遍历；如果是用队列辅助，则对应广度优先。

所以，这里用循环遍历对象属性树的方式来解决栈溢出问题。

代码

最后就看看实现的代码，这里给出两个版本，分别是未处理栈溢出场景（递归方案）、循环替代递归：

未处理栈溢出版（递归方案）：

// 递归遍历对象的属性树
function cloneDeep(source, hash = new WeakMap()) {
    // 1. 非对象类型数据，直接返回
    if (!(typeof source === 'object' && source !== null)) {
        return source;
    }
    // 2. 复用已拷贝的对象，解决引用关系丢失和循环引用问题
    if (hash.get(source)) {
        return hash.get(source);
    }
    
    // 3. 区分对象和数组
    let target = Array.isArray(source) ? [] : {};
    hash.set(source, target);  // 缓存已拷贝的对象
    
    // 4. 遍历对象所有自有属性，包括 Symbol
    Reflect.ownKeys(source).forEach(key => {
        // 跳过自有的不可枚举的属性
        if (!Object.getOwnPropertyDescriptor(source, key).enumerable) {
            return;
        }
        // 对象类型再继续递归遍历，其他类型直接赋值拷贝
        if (typeof source === 'object' && source !== null) {
            target[key] = cloneDeep(source[key], hash);
        } else {
            target[key] = source[key];
        }
    });
    
    return target;
}

循环替代递归版（循环方案）：

// 循环遍历对象的属性树，跟递归方案中相同代码用途是一样的，这里就不注释了
function cloneDeep(source) {
    if (!(typeof source === 'object' && source !== null)) {
        return source;
    }
    let target = Array.isArray(source) ? [] : {};
    let hash = new WeakMap();
    
    // 将根节点放入栈中，节点结构说明：data 存储当前属性值，key 存储属性名，target 含义：target[key] = data
    let stack = [{
        data: source,
        key: undefined,
        target: target
    }];
    
    // 因为是借助 stack 栈辅助，所以是深度优先遍历，每次循环只处理一个节点
    while(stack.length > 0) {
        let node = stack.pop();
        if (typeof node.data === 'object' && node.data !== null) {
            // 当前对象有已拷贝过的缓存，则直接用缓存，解决引用关系丢失问题
            if (hash.get(node.data)) {
                node.target[node.key] = hash.get(node.data);
            } else {
                let target;
                // 构建拷贝对象的属性层次结构
                if (node.key !== undefined) {
                    target = Array.isArray(node.data) ? [] : {};
                    node.target[node.key] = target;
                } else {
                    target = node.target;
                }
                hash.set(node.data, target);
                Reflect.ownKeys(node.data).forEach(v =>{
                    if (!Object.getOwnPropertyDescriptor(node.data, v).enumerable) {
                        return;
                    }
                    stack.push({
                        data: node.data[v],
                        key: v,
                        target: target
                    }) 
                });
            }
        } else {
            // 当前节点是非对象类型，直接拷贝
            node.target[node.key] = node.data;
        }
    }
    return target;
}

测试用例：

// 测试用例
var a = {};
var o = {
    a: a,
    b: a,
    c: Symbol(),
    [Symbol()]: 1,
    d: function() {},
    e(){},
    f: () => {},
    get g(){},
    h: 1,
    i: 'sdff',
    j: null,
    k: undefined,
    o: /sdfdf/,
    p: new Date()
}

var o1 = cloneDeep(o);
o1;
/**
{
    a: {}
    b: {}
    c: Symbol()
    d: ƒ ()
    e: ƒ e()
    f: () => {}
    g: undefined
    h: 1
    i: "sdff"
    j: null
    k: undefined
    l: {l: {…}, p: {…}, o: {…}, k: undefined, j: null, …}
    o: {}
    p: {}
    Symbol(): 1
}
*/
// 正则的数据和 Date 数据都丢失了，这是因为判断对象的逻辑导致，typeof xx === 'object' 无法区别内置对象，想要解决，可以修改判断对象的逻辑，比如使用 Object.prototype.toString.call(xxx) 结合 Array.isArray 来只筛选出基本对象和数组类型
// get 存取器也只能拷贝到读取的时，无法拷贝 get 方法


// 测试栈溢出场景可借助该方法
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;
}

var a = createData(10000);

cloneDeep(a); // 是否会栈溢出

其实，这通用版也不是100%通用，它仍旧有一些局限性，比如：

没有考虑 ES6 的 set，Map 等新的数据结构类型
拷贝后的对象的原型链结构，继承关系丢失问题
get，set 存取器逻辑无法拷贝
没有考虑属性值是内置对象的场景，比如 /sfds/ 正则，或 new Date() 日期这些类型的数据
等等

虽然如此，但这种方案已经大体上适用于绝大多数的场景了，如有问题，或者有新的需求，再根据需要进行扩展就可以了，欢迎指点一下。

JSON.parse/stringify 版

这是实现深拷贝最简单的一种方案，但是有很大局限性，只适用于部分场景：

var o = {
    a: 1,
    b: [1, 2, {a: 1}]
}

var o1 = JSON.parse(JSON.stringify(o));

它的原理很简单，就是借助现有工具 JSON，先将对象序列化，再反序列化得到一个新对象，这样一来，新对象跟原对象就是两个相互独立，互不影响的对象了，以此来实现深拷贝。

但它有很大的局限性，因为需要依赖于 JSON 的序列化和反序列化基础，比如说：

不能序列化函数，属性值是函数的会丢失掉
不能处理 Symbol 数据，不管是属性名还是属性值是 Symbol 的，都会丢失掉
不能识别属性值手动设置为 undefined 的场景，会被认为是访问一个不存在的属性，从而导致丢失
不能解决循环引用问题
不能处理正则
等等

使用这种方案，还是有很多局限性，看个代码就清楚了：

var o = {
    a: 1,
    [Symbol()]: 1,
    c: Symbol(),
    d: null,
    e: undefined,
    f: function() {},
    g() {},
    h: /sdfd/
}
var o1 = JSON.parse(JSON.stringify(o));
o1; // {a: 1, d: null, h: {}}
// 属性 c, e, f, g 都丢失掉了，h 属性值为正则表达式，也无法正常处理

那么，这种方案的深拷贝就没有什么用处吗？

也不是，它有它适用的场景，想想 JSON 是什么，是处理 json 对象的工具啊，而 json 对象通常是用来跟服务端交互的数据结构，在这种场景里，你一个 json 对象里，会有那些 Symbol、正则、函数奇奇怪怪的属性吗？显然不会。

所以，对于规范的 json 对象来说，如果需要进行深拷贝，那么就可以使用这种方案。

通俗点说，在项目中的使用场景也就是对后端接口返回的 json 数据需要深拷贝时，就可以使用这种方案。

（以上个人理解，有误的话，欢迎指点一下）

Object.assign 版

上面的深拷贝方案只是将一个对象完完整整拷贝一份出来，新对象数据和原对象数据都是一模一样的，算是副本。

但如果，需求是要类似 Object.assign 这种，将一个原对象完完整整拷贝到另一个已存在的目标对象上面呢？这种场景，拷贝后的新对象就跟原对象不是一样的了，而是两者的交集，冲突的拷贝的原对象为主。

这种场景上面的深拷贝方案就不适用了，这里参考 Object.assign 原理扩展实现 assignDeep，实现可将指定的原对象们，拷贝到已存在的目标对象上：

// 递归版
function assignDeep(target, ...sources) {
    // 1. 参数校验
    if (target == null) {
        throw new TypeError('Cannot convert undefined or null to object');
    }

    // 2. 如果是基本类型数据转为包装对象
    let result = Object(target);
    
    // 3. 缓存已拷贝过的对象，解决引用关系丢失问题
    if (!result['__hash__']) {
        result['__hash__'] = new WeakMap();
    }
    let hash  = result['__hash__'];

    sources.forEach(v => {
        // 4. 如果是基本类型数据转为对象类型
        let source = Object(v);
        // 5. 遍历原对象属性，基本类型则值拷贝，对象类型则递归遍历
        Reflect.ownKeys(source).forEach(key => {
            // 6. 跳过自有的不可枚举的属性
            if (!Object.getOwnPropertyDescriptor(source, key).enumerable) {
                return;
            }
            if (typeof source[key] === 'object' && source[key] !== null) {
                // 7. 属性的冲突处理和拷贝处理
                let isPropertyDone = false;
                if (!result[key] || !(typeof result[key] === 'object') 
                    || Array.isArray(result[key]) !== Array.isArray(source[key])) {
                    // 当 target 没有该属性，或者属性类型和 source 不一致时，直接整个覆盖
                    if (hash.get(source[key])) {
                        result[key] = hash.get(source[key]);
                        isPropertyDone = true;
                    } else {
                        result[key] = Array.isArray(source[key]) ? [] : {};
                        hash.set(source[key], result[key]);
                    }
                }
                if (!isPropertyDone) {
                    result[key]['__hash__'] = hash;
                    assignDeep(result[key], source[key]);
                }
            } else {
                Object.assign(result, {[key]: source[key]});
            }
        });
    });

    delete result['__hash__'];
    return result;
}

上面只给了递归版，存在栈溢出可能性，但基本没这种对象层次太深的场景，想了解其他实现如循环版以及详细内容的，可以去我另一篇文章查阅：扩展 Object.assign 实现深拷贝

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

javascript