《简单算法》之深拷贝

[foreverwang]

深拷贝

深拷贝即赋值属性的值而非引用，如果属性值是引用类型的我们就得进行生层级的拷贝直到属性值是基本类型值。
我们很容易能想到用递归实现：

递归实现 [object Object] 类型数据的深拷贝

function clone(target) {
	let cloneObj = {};
	if (target && typeof target === 'object') {
		for (let key in target) {
			if (typeof target[key] !== 'object') {
				console.log('not object')
				cloneObj[key] = target[key];
			} else { //object
				console.log('is object')
				cloneObj[key] = clone(target[key]);
			}
		}
	}
	return cloneObj;
}

我们测试一下：

let obj1 = {a:1,b:{bb:2}}
let clonedObj1 = clone(obj1) //{a:1,b:{bb:2}}
obj1.b === clonedObj1.b //false

看上去好像能到到我们的目的，然而却经不住推敲，这个方法只能处理[object Object]类型值，[object Array]类型就没处理。那么下面我们加上对数组的处理：

处理数组

function clone(target) {
	let cloneObj = {};
	if (target && typeof target === 'object') {
		if (Array.isArray(target)) {
			cloneObj = target.map((item) => {
				if (typeof item !== 'object') {
					return item
				} else {
					return clone(item);
				}
			})
		} else {
			for (let key in target) {
				if (typeof target[key] !== 'object') {
					console.log('not object')
					cloneObj[key] = target[key];
				} else { //object
					console.log('is object')
					cloneObj[key] = clone(target[key]);
				}
			}
		}
	}
	return cloneObj;
}

测试一下：

let arr = [1,{a:1},[2,3]]
let clonedArr = clone(arr) //[1,{a:1},[2,3]]
clonedArr[1] === arr[1] //false

数组处理完了，那么其他数据类型呢，比如Date,正则，Set,Map等等，我们这里没有处理自然不能正确拷贝这行类型的值，这里就先不试了。但是要想处理这些特殊类型的值也简单，因为他们不会有内层嵌套结构了，通过Object.prototype.toString.call() 判断具体类型，然后再分别创建对应类型的新值就行了。

但是即便我们处理了数据类型的问题，这个clone的方法还是不完美的，因为没有处理循环引用的问题：

let	 obj2 = {a:{aa:1}};
obj2.a.b = obj2.a;
clone(obj2)// Uncaught RangeError: Maximum call stack size exceeded

由于循环引用结构导致我们在递归拷贝的时候栈溢出了。

处理递归爆栈

递归改循环，深层对象结构其实就是个树结构，这个问题就变成遍历一棵树，我们可以借助栈结构来实现。
链接：https://juejin.im/post/5bc1ae9be51d450e8b140b0c

function cloneLoop(x) {
    const root = {};

    // 栈
    const loopList = [
        {
            parent: root,
            key: undefined,
            data: x,
        }
    ];

    while(loopList.length) {
        // 深度优先
        const node = loopList.pop();
        const parent = node.parent;
        const key = node.key;
        const data = node.data;

        // 初始化赋值目标，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') {
                    // 下一次循环
                    loopList.push({
                        parent: res,
                        key: k,
                        data: data[k],
                    });
                } else {
                    res[k] = data[k];
                }
            }
        }
    }

    return root;
}

处理循环引用

循环引用检测

现在我们思考下如何检测一个数据是否有循环引用结构呢？下面是一种检测方法，思路就是利用深度优先遍历：

function cycleDetector(obj, test) {
	console.log(test);
	let hasCircle = false;
	let cache = [];
	function cycle(obj) {
		let keys = Object.keys(obj);
		for (var i = 0; i < keys.length; i++) {
			let value = obj[keys[i]];
			if (typeof value === 'object' && value !== null) {
				if (cache.indexOf(value) !== -1) {
					return (hasCircle = true)
					// hasCircle = true
					// break;
				} else {
					cache.push(value);
					if (cycle(value, 1)) {
						return hasCircle;
					}
					cache.pop();//  注意：⭐️这里要推出数据，因为递归返回，后面遍历的属性不是这个数据的子属性
				}
			}
		}
		// return hasCircle;
	}
	return cycle(obj);
}	   	

处理循环引用和引用中断

上面我们只是实现了检测循环引用的方法，我们只能检测到，但还是不能深拷贝循环引用的数据。除了循环引用还有个问题，就是子数据有相同引用的， 用以上方法clone后引用关系会中断，举个例子：

let ojb1 = {x:1}
let obj = {a:obj1,b:obj1}
let clonedObj = clone(obj);
obj.a === obj.b //true
clonedObj.a === clonedObj.b //false

在上面循环改递归的基础上稍加改造：引入一个数组uniqueList用来存储已经拷贝的数组，每次循环遍历时，先判断对象是否在uniqueList中了，如果在的话就不执行拷贝逻辑了。

// 保持引用关系
function cloneForce(x) {
    // =============
    const uniqueList = []; // 用来去重
    // =============

    let root = {};

    // 循环数组
    const loopList = [
        {
            parent: root,
            key: undefined,
            data: x,
        }
    ];

    while(loopList.length) {
        // 深度优先
        const node = loopList.pop();
        const parent = node.parent;
        const key = node.key;
        const data = node.data;

        // 初始化赋值目标，key为undefined则拷贝到父元素，否则拷贝到子元素
        let res = parent;
        if (typeof key !== 'undefined') {
            res = parent[key] = {};
        }
        
        // =============
        // 数据已经存在
        let uniqueData = find(uniqueList, data);
        if (uniqueData) {
            parent[key] = uniqueData.target;
            continue; // 中断本次循环
        }

        // 数据不存在
        // 保存源数据，在拷贝数据中对应的引用
        uniqueList.push({
            source: data,
            target: res,
        });
        // =============
    
        for(let k in data) {
            if (data.hasOwnProperty(k)) {
                if (typeof data[k] === 'object') {
                    // 下一次循环
                    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;
}

实际应用

上面我们主要是从学习的角度实现了支持常见数据类型及循环引用结构的数据的沈拷贝，在实际的生产环境中我们很少自己去实现这样一个深拷贝方法。根据我们不同的场景我们选择不同的方法；

JSON数据

JSON.parse(JSON.stringify(json))

需要处理循环引用，及其他数据类型

引用lodash库的方法，比较成熟稳定

_.cloneDeep(obj) // clone(obj, true)

总结

• 实现基本的深拷贝，最简单就是用递归，
• 但是递归会遇到调用栈溢出--要拷贝的数据层级特别深；有循环引用结构的数据。
• 相同引用的子数据拷贝后引用中断问题
• 特定的数据类型要单独处理，比如Set等
• 生产环境根据业务场景通常选择的方案：
  • JON.parse(JSON.stringify(json)) （简单直接，受限）
  • Loadsh的cloneDeep方法 （成熟稳定，放心）