实现一个深拷贝

[swiftwind0405]

1. 初级版

深拷贝可以拆分成两步：浅拷贝+递归，浅拷贝时判断属性值是否是对象，如果是对象就进行递归操作，两个一结合就实现了深拷贝。

// 写法一
function cloneDeep1(source) {
    var target = {};
    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (typeof source[key] === 'object') {
				// 如果当前结果是一个对象，那我们就继续递归这个结果
                target[key] = cloneDeep1(source[key]);
            } else {
                target[key] = source[key];
            }
        }
    }
    return target;
}
// 写法二
function cloneDeep1(obj) {
    const keys = Object.keys(obj);
    return keys.reduce((memo, current) => {
        const value = obj[current];
        if (typeof value === 'object') {
            // 如果当前结果是一个对象，那我们就继续递归这个结果
            return {
                ...memo,
                [current]: cloneDeep1(value),
            };
        }
        return {
            ...memo,
            [current]: value,
        };
    }, {});
}

存在的问题：

1. 只能处理 Plain Object，比如 null、数组、Symbol、key 里面 getter，setter 以及原型链上的内容无法处理
2. 无法处理内部有循环引用的情况

拷贝数组

兼容数组的写法如下：

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

function cloneDeep2(source) {
    if (!isObject(source)) return source; // 非对象返回自身
      
    var target = Array.isArray(source) ? [] : {};
    for(var key in source) {
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (isObject(source[key])) {
                target[key] = cloneDeep2(source[key]); // 注意这里
            } else {
                target[key] = source[key];
            }
        }
    }
    return 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;
    }
};

接下来，可以使用，WeakMap 替代 Map来使代码达到画龙点睛的作用。

function clone(target, map = new WeakMap()) {
    // ...
};

原因是：如果我们要拷贝的对象非常庞大时，使用 Map 会对内存造成非常大的额外消耗，而且我们需要手动清除 Map 的属性才能释放这块内存，而 WeakMap 会帮我们巧妙化解这个问题。

拷贝 Symbol

• 第四步：拷贝 Symbol

破解递归爆栈

上面四步使用的都是递归方法，但是有一个问题在于会爆栈，错误提示如下。

// RangeError: Maximum call stack size exceeded

那应该如何解决呢？其实我们使用循环就可以了，代码如下：

function cloneDeep5(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;
}

实现一个通用的 deepClone 函数

1. 如果是基本数据类型，直接返回
2. 如果是 RegExp 或者 Date 类型，返回对应类型
3. 如果是复杂数据类型，递归。
4. 考虑循环引用的问题

    function deepClone(obj, hash = new WeakMap()) { //递归拷贝
        if (obj instanceof RegExp) return new RegExp(obj);
        if (obj instanceof Date) return new Date(obj);
        if (obj === null || typeof obj !== 'object') {
            //如果不是复杂数据类型，直接返回
            return obj;
        }
        if (hash.has(obj)) {
            return hash.get(obj);
        }
        /**
         * 如果obj是数组，那么 obj.constructor 是 [Function: Array]
         * 如果obj是对象，那么 obj.constructor 是 [Function: Object]
         */
        let t = new obj.constructor();
        hash.set(obj, t);
        for (let key in obj) {
            //递归
            if (obj.hasOwnProperty(key)) {//是否是自身的属性
                t[key] = deepClone(obj[key], hash);
            }
        }
        return t;
    }

参考资料

• 深拷贝的终极探索
• 面试题之如何实现一个深拷贝
• 如何写出一个惊艳面试官的深拷贝

[swiftwind0405]

待读文章：

• 如何写出一个惊艳面试官的深拷贝?

• 一文搞懂JS中的赋值·浅拷贝·深拷贝

• JavaScript 深拷贝性能分析 | justjavac(迷渡)

[swiftwind0405]

递归实现一个深拷贝

const target = {
  field1: 1,
  field2: undefined,
  field3: {
    child: "child",
  },

  field4: [2, 4, 8],
};

target.target = target;

实现：

function clone(target, map = new WeakMap()) {
  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;
  }
}

深拷贝也是递归常考的例子

每次拷贝发生的事:

• 检查 map 中有无克隆过的对象
• 有,直接返回
• 没有, 将当前对象作为 key，克隆对象作为 value 进行存储
• 继续克隆

在这段代码中我们使用了 weakMap ，用来防止因循环引用而出现的爆栈。