深拷贝系列 ———— 自己通过递归实现一个深拷贝

简介

在上篇文章中我们深入了解了JSON.parse/JSON.stringify，并且自己实现了一个JSON.parse/JSON.stringify，在这篇文章中我们要自己实现一个深拷贝，并且解决JSON.parse/JSON.stringify中出现的问题。

递归实现

实现目标

我们通过递归实现一个简单的深拷贝
判断Object和Array

实现步骤

提前声明一个判断类型函数getType
声明函数cloneDeep，首先判断原对象是否为object类型，如果不是直接返回原值
声明一个新的目标对象newTarget，它的类型根据入参决定（Array、Object）
通过for...in循环原对象，并且通过hasOwnProperty判断属性是否为本身属性
如果是本身属性递归调用cloneDeep
最后返回新对象newTarget

    // 获取当前类型
    function getType(attr) {
        let type = Object.prototype.toString.call(attr);
        let newType = type.substr(8, type.length - 9);
        return newType;
    }
    // 声明一个函数
    function cloneDeep (target) {
        // 判断是否传入类型为Object
        if (typeof target !== 'object') {
            return target;
        }
        // 声明新对象
        let newTarget = getType(target) === 'Array' ? [] : {};
        // 循环对象 递归复制给新对象
        for (let key in target) {
            // 判断属性是否在对象本身上
            if (target.hasOwnProperty(key)) {
                // 递归调用
                newTarget[key] = cloneDeep(target[key]);
            }
        }
        // 返回新对象
        return newTarget;
    }

    // 测试代码
    const target = {
        val1: 1,
        val2: undefined,
        val4: 'target',
        val5: {
            name: 'target',
            age: function () {},
            sym: Symbol('setter')
        }
    };
    const targetArray = [1, 2, 3, {name: '123', age: 789}];
    console.log(cloneDeep(target));
    console.log(cloneDeep(targetArray));

测试效果图如下：

在上面的代码中，已经解决了JSON.stringify/JSON.parse中的忽略undefined/function的问题，下面会逐渐解决问题，并且优化到类似与lodash库中的问题。

循环引用

实现目标

解决循环引用对象问题
解决引用丢失问题

实现步骤

首先了解Map、WeakMap是什么
通过Map、WeakMap、Array储存属性对象
如果再次使用，直接从Map、WeakMap中取出(这样既解决了循环引用，又解决了引用丢失)

测试循环引用代码：

    const target = {
        val1: 1,
        val2: undefined,
        val4: "target",
        val5: {
            name: "target",
            age: function() {},
            sym: Symbol("setter")
        }
    };
    target.target = target;
    console.log(cloneDeep(target));

执行效果如下图所示：深拷贝/浅拷贝

Map/weakMap

Map和WeakMap都是ES6中的新出的数据类型。如果有兴趣可以去WeakMap mdn和Map mdn，或者Set 和 Map 数据结构去了解它们的api和使用场景等。

Map

Map对象保存键值对。任何值(对象或者原始值) 都可以作为一个键或一个值。

语法

new Map([iterable])

iterable: Iterable 可以是一个数组或者其他 iterable 对象，其元素为键值对(两个元素的数组，例如: [[ 1, 'one' ],[ 2, 'two' ]])。每个键值对都会添加到新的Map。null 会被当做 undefined。

常用方法

Map.prototype.get(key): 返回键对应的值，如果不存在，则返回undefined。
Map.prototype.set(key, value): 设置Map对象中键的值。返回该Map对象。
Map.prototype.has(key): 返回一个布尔值，表示Map实例是否包含键对应的值。
Map.prototype.delete(key): 如果 Map对象中存在该元素，则移除它并返回 true；否则如果该元素不存在则返回 false。

这里只介绍了常用的操作方法，Map还有循环方法、其他方法等等。

实例

    var oneMap = new Map();
    var keyObj = {
        name: 'keyObj'
    };
    oneMap.set('name', 'test'); // {"name" => "test"}
    oneMap.set(keyObj, 'keyObj'); // {"name" => "test", keyObj => "keyObj"} 这里的keyObj是上面声明的对象

    oneMap.get('name'); // "test"
    oneMap.get(keyObj); // "keyObj"

    oneMap.has('name'); // true
    oneMap.has(keyObj); // true
    oneMap.has('age'); // false

    oneMap.delete('name'); // true

WeakMap

WeakMap 对象是一组键/值对的集合，其中的键是弱引用的。其键必须是对象，而值可以是任意的。

它的语法、参数与Map是一至的，只有两点区别：

WeakMap只接受对象作为键名（null除外），不接受其他类型的值作为键名。
WeakMap 弱引用的只是键名，而不是键值。键值依然是正常引用。

同时WeakMap只有上面get/set/has/delete四种方法，其它的方法它都是没有的。

实例

    const map = new WeakMap();
    map.set(1, 2)
    // TypeError: 1 is not an object!
    map.set(Symbol(), 2)
    // TypeError: Invalid value used as weak map key
    map.set(null, 2)
    // TypeError: Invalid value used as weak map key

    const wm = new WeakMap();
    let key = {};
    let obj = {foo: 1};

    wm.set(key, obj);
    obj = null;
    wm.get(key)
    // Object {foo: 1}

这里就不测试它的操作方法了，它的操作方法与Map一至。

通过Map解决

在这里我们通过Map来解决循环引用，修改代码如下：

    // 声明一个函数
    function cloneDeep (target, map = new Map()) {
        // 判断是否传入类型为Object
        if (typeof target !== 'object') {
            return target;
        }
        // 声明新对象
        let newTarget = getType(target) === 'Array' ? [] : {};

        // <!------新增代码开始------!>
        // 查询map中是否有存在原对象（target），如果存在直接返回
        if (map.get(target)) {
            return target;
        }
        // 如果map中不存在原对象（target），则储存进map中
        map.set(target, newTarget);
        // <!------新增代码结束------!>

        // 循环对象 递归复制给新对象
        for (let key in target) {
            // 判断属性是否在对象本身上
            if (target.hasOwnProperty(key)) {
                // 递归调用
                newTarget[key] = cloneDeep(target[key], map);
            }
        }
        // 返回新对象
        return newTarget;
    }

执行测试代码如下：

我们可以看到target变为一个Circular类型的对象，这个是在node环境中运行的，如果在浏览器对还是会报错（爆栈）。到这里我们只做到了让他没有报错，但是也并没有完美的解决循环引用的问题，下面就要到WeakMap登场了。

WeakMap解决

上面我们已经讲解过Map和WeakMap的不同点和相同点，为什么说WeakMap在解决循环引用会比Map好很多呢，就是因为WeakMap它的键值是弱引用的。什么是弱引用，即垃圾回收机制不考虑 WeakMap 对该对象的引用，也就是说，如果其他对象都不再引用该对象，那么垃圾回收机制会自动回收该对象所占用的内存，不考虑该对象还存在于 WeakMap 之中。要深入理解弱引用这个又会涉及到Node和JavaScript底层垃圾回收机制，因为它们的垃圾回收机制都是使用的标记法，又分为新生代和老生代，所以这里就不多做赘述了。后面会有一系列文章来讲述Node和JavaScript中的相同和异同点。

修改代码如下：

    // 只是把Map修改为WeakMap
    map = new WeakMap()

这样无论是在浏览器端还是node中都可以正常的运行。

类型问题

我们在上面只考虑了Array/Object其实就是Object类型的数据处理，其他的数据都是走的直接返回。

改写Object的判断，并且分别处理Array/Object方法
处理Function
处理Symbol
处理不可循环类型（Number/String/Date/Boolean）
处理RegExp/Map/Set

我们就按上面的步骤一步一步分拆不同类型走不同的处理，已解决在JSON.stringify遇到的问题。

Object类型判断

在上面的代码中我们只是简单的判断了Object，如果不是Object直接返回，其实是没有考虑到null这个特殊情况的。我们现在就要加上null的怕判断并且后面也要独立处理Function类型的copy。

实现目标：

null的判断
function的判断
Array/Object的分别处理

代码实现：

    // 新增判断属性
    function isObject(value) {
        // 储存传入值的类型
        const type = typeof value
        // 过滤null
        return value != null && (type === 'object' || type === 'function')
    }

    // 声明一个函数
    function cloneDeep (target, map = new Map()) {
        // 判断是否传入类型为Object
        if (!isObject) {
            return target;
        }
        // 。。。省略代码
        // 其实还可以通过Array.isArray()来检测是否为数组
    }

Function

function处理：

其实即使function指向同一个内存地址，他也是没有任何问题的，所以可以直接可以返回return value。

const isFunc = typeof value === 'function';
if (isFunc) {
    return value;
}

Symbol

数据类型 “symbol” 是一种原始数据类型，该类型的性质在于这个类型的值可以用来创建匿名的对象属性。我们可以拷贝symbol类型的属性名？

首先我们可以通过typeof、Object.prototype.toString.call()来检测symbol的类型，但是我们怎么获取到symbol.

示例代码

    var test = Symbol('name');
    typeof test; // symbol
    Object.prototype.toString.call(test); // [object Symbol]

我们可以通过两种方法获取的到symbol.

Object.getOwnPropertySymbols(...): Object.getOwnPropertySymbols(...)可以查找一个给定对象的符号属性时返回一个 symbol 类型的数组。
Reflect.ownKeys(...): 返回一个由目标对象自身的属性键组成的数组。

注意：每个初始化的对象都是没有自己的 symbol 属性的，因此这个数组可能为空，除非你已经在对象上设置了 symbol 属性。 Reflect.ownKeys(...)的返回值等同于Object.getOwnPropertyNames(target).concat(Object.getOwnPropertySymbols(target))。

示例代码

    var sName = Symbol('name');
    var age = Symbol('age');

    var testObj = {
        firstSex: 'man'
    };
    testObj[sName] = 'name';
    testObj[age] = 19;
    testObj.lastSex = 'girl'

    objectSymbols = Object.getOwnPropertySymbols(testObj);
    console.log(objectSymbols.length); // 2
    console.log(objectSymbols)         // [Symbol('name'), Symbol('age')]
    console.log(objectSymbols[0])      // Symbol('name')


    Reflect.ownKeys(testObj); // ["firstSex", "lastSex", Symbol(name), Symbol(age)]
    // 注意顺序

这个只能获取到当前的值，但是我们怎么拷贝这个属性呢？

我们可以通过valueOf来获取symbol的原始值，然后再复制当前的属性和值。 valueOf()方法返回当前 symbol 对象所包含的 symbol 原始值。

    function cloneSymbol (symbol) {
        // 保存方法
        const symbolValueOf = Symbol.prototype.valueOf;
        return Object(symbolValueOf.call(symbol))
    }

不可循环类型

我们常用的不可循环的类型，比如Number/String/Date/Boolean，如果是一些字面量直接赋值给新的对象也是没有问题，但是我们通过创建一个新的对象自然更好。

    function cloneStatic (target) {
        // 获取构造函数
        const Ctor = targe.constructor;
        // 实例化一个同类型的属性
        return new Ctor(target);
    }

RegExp/Map/Set

首先处理RegExp正则，我们这里直接使用lodash中的，其实和静态的方法类似，都是生成一个新的RegExp对象。

    function cloneRegExp(regexp) {
        const reFlags = /\w*$/;
        const result = new regexp.constructor(regexp.source, reFlags.exec(regexp));
        result.lastIndex = regexp.lastIndex;
        return result;
    }

Map/Set

我们要考虑Map/Set类型的处理，因为它们也是可以循环的，并且他们可以的key-value也可以为可循环的值。

    function cloneMap (target) {
        // 声明一个新的Map
        let newMap = new Map();
        // 循环复制到新Map
        target.forEach((value, key) => {
            // 因为值有可能是一个对象、数组，所以要递归调用
            newMap.set(key, cloneDeep);
        });
        return newMap();
    }
    function cloneSet (target) {
        // 声明一个新的Set
        let newSet = new Set();
        // 循环复制到新Set
        target.forEach((value, key) => {
            // 因为值有可能是一个对象、数组，所以要递归调用
            newSet.add(key, cloneDeep);
        });
        return newSet();
    }

总结

我们考虑了大部分类型的实现，下面是完整的代码：

   // <!------------工具函数开始----------------------------!>
// 创建数据
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;
}
// 获取类型
function getType(attr) {
  let type = Object.prototype.toString.call(attr);
  let newType = type.substr(8, type.length - 9);
  return newType;
}
// 判断是否为引用类型
function isObject(value) {
  // 储存传入值的类型
  const type = typeof value;
  // 过滤null
  return value != null && (type === "object" || type === "function");
}
// 克隆function
function cloneFunc(value) {
  const isFunc = typeof value === "function";
  if (isFunc) {
    return value;
  }
}

// 克隆symbol
function cloneSymbol(symbol) {
  // 保存方法
  const symbolValueOf = Symbol.prototype.valueOf;
  // 返回key
  return Object(symbolValueOf.call(symbol));
}

// 克隆RegExp
function cloneRegExp(regexp) {
  const reFlags = /\w*$/;
  const result = new regexp.constructor(regexp.source, reFlags.exec(regexp));
  result.lastIndex = regexp.lastIndex;
  return result;
}

// 不可循环的类型 Number/String/Date/Boolean
function cloneStatic(target) {
  // 获取构造函数
  const Ctor = target.constructor;
  // 实例化一个同类型的属性
  return new Ctor(target);
}
// <!------------工具函数结束----------------------------!>
// <!------------克隆逻辑开始----------------------------!>
// 声明一个函数
function cloneDeep(target, map = new WeakMap()) {
  // 判断类型
  // console.log(isObject(target));
  if (!isObject(target)) {
    return target;
  }
  // console.log(111);
  let newTarget = {};
  switch (getType(target)) {
    case "Number":
    case "String":
    case "Boolean":
    case "Date":
      return cloneStatic(target);
    case "RegExp":
      return cloneRegExp(target);
    case "Function":
      return cloneFunc(target);
    case "Array":
      newTarget = [];
      break;
    case "Map":
      newTarget = new Map();
      break;
    case "Set":
      newTarget = new Set();
      break;
  }

  // 查询map中是否有存在原对象（target），如果存在直接返回
  if (map.has(target)) {
    return target;
  }
  // 如果map中不存在原对象（target），则储存进map中
  map.set(target, newTarget);

  // 拷贝Map
  if (getType(target) === "Map") {
    // 循环复制到新Map
    target.forEach((value, key) => {
      // 因为值有可能是一个对象、数组，所以要递归调用
      newTarget.set(key, cloneDeep(value, map));
    });
    return newTarget;
  }
  // 拷贝Set
  if (getType(target) === "Set") {
    // 循环复制到新Map
    target.forEach((value, key) => {
      // 因为值有可能是一个对象、数组，所以要递归调用
      newTarget.add(key, cloneDeep(value, map));
    });
    return newTarget;
  }

  // 循环对象 递归复制给新对象
  for (let key in target) {
    // 判断属性是否在对象本身上
    if (target.hasOwnProperty(key)) {
      // 递归调用
      newTarget[key] = cloneDeep(target[key], map); // <!------新增代码 参数map------!>
    }
  }
  // 返回新对象
  return newTarget;
}
// <!------------克隆逻辑结束----------------------------!>

// 测试代码

// 实例化symbol
let oneSymbol = Symbol("name");
// 实例化Map
let newMap = new Map();
newMap.set("name", { name: "everybody" });
// 实例化Set
let newSet = new Set();
newSet.add("age", { age: 18 });
const target = {
  val1: 1,
  val2: undefined,
  val4: "target",
  val5: {
    name: "target",
    age: function() {
      console.log("永远18岁");
    },
    sym: Symbol("setter")
  },
  val32: new Boolean(true),
  val23: new String(true),
  val443: new Number(true),
  date: new Date(),
  reg: /\d+/,
  empty: null,
  newMap,
  newSet,
  arrowFunc: () => {
    console.log("test111");
  },
  deepObj: createData(10, 100)
};
target[oneSymbol] = "name";
console.time();
const ss = cloneDeep(target);
console.timeEnd();

console.log(ss);

执行结果：

性能问题

在上面我们使用的循环是for...in，但是他的性能并不是最高的，我们现在来对比一下for...in、for、while、forEach三个循环谁的速度更快。我们可以通过每个循环100000次，在浏览器端通过console.time()、console.timeend()统计当前执行的循环效率。代码如下：

    // 生成数据
    let initData = [];
    var len = 100000;
    for (let i = 0; i < len; i++) {
        let item = {
            name: 'name',
            age: 18,
            sex: 'man',
            class: 'first'
        };
        initData.push(item);
    }
    var sum = 0;

    // 记录for循环时间
    console.time();
    for (let i = 0; i < len; i++) {
        sum += initData[i].age;
    }
    console.timeEnd();

    // 记录for...in循环时间
    console.time();
    for (let item in initData) {
        sum += initData[item];
    }
    console.timeEnd();

    // 记录while循环时间
    let i = 0;
    console.time();
    while (i < len) {
        sum += initData[i].age;
        i++;
    }
    console.timeEnd();
    // 记录forEach循环时间
    console.time();
    initData.forEach((item, index, soruce) => {
        sum += item;
    })
    console.timeEnd();

多次执行效果相差不多，执行效果如下：

图上的四个时间分别对应的顺序是：

for: 2.8ms
for...in: 17.7ms
while: 4.4ms
forEach: 45.2ms

这个测试环境是在mac pro i7 16G、Chrome 78.0.3904.87这个进行的只是简单测试，大致结果for > while > for...in > forEach。

但是我看到lodash中是用的while，并且别人测试的是和我测试相反的。这里就不再多做追究了，免的喧宾夺主后面会独立一篇文章好好探讨一下谁的速度更快。我们也通过while改写代码吧。

    function arrayEach(array, iteratee) {
        let index = -1;
        // 获取数组长度
        const length = array.length;
        // 循环体
        while (++index < length) {
            // 执行回调
            if (iteratee(array[index], index, array) === false) {
                break
            }
        }
        return array
    }

修改循环逻辑的代码如下

// 原代码如下
// 循环对象 递归复制给新对象
for (let key in target) {
    // 判断属性是否在对象本身上
    if (target.hasOwnProperty(key)) {
        // 递归调用
        newTarget[key] = cloneDeep(target[key], map); // <!------新增代码 参数map------!>
    }
}

// 修改为

const keys = getType(target) === "Array" ? undefined : Object.keys(target);
let i = 0;
arrayEach(keys || target, (value, key) => {
    if (keys) {
        key = value;
    }
    if (target.hasOwnProperty(key)) {
        newTarget[key] = cloneDeep(target[key], map); // <!------新增代码 参数map------!>
    }
});

测试代码

    // 实例化symbol
    let oneSymbol = Symbol("name");
    // 实例化Map
    let newMap = new Map();
    newMap.set("name", { name: "everybody" });
    // 实例化Set
    let newSet = new Set();
    newSet.add("age", { age: 18 });
    const target = {
        val1: 1,
        val2: undefined,
        val4: "target",
        val5: {
            name: "target",
            age: function() {
                console.log("永远18岁");
            },
            sym: Symbol("setter")
        },
        val32: new Boolean(true),
        val23: new String(true),
        val443: new Number(true),
        date: new Date(),
        reg: /\d+/,
        empty: null,
        newMap,
        newSet,
        arrowFunc: () => {
            console.log("test111");
        },
        deepObj: createData(100, 1000)
    };
    target[oneSymbol] = "name";


    // console.log('');

    console.time();
    const ss1 = cloneDeepTwo(target)
    console.timeEnd();

    console.time();
    const ss = clone(target)
    console.timeEnd();

分开测试执行时间相差是1ms-2ms，其实并不相差太大，不能一起测试，因为一起测试的话，第一次执行的一些变量会被储存在内存中，第二次执行的速度自然会很快，所以一起测试的时间并不准确。

递归爆栈

我们测试使用的数据深度为100，广度为1000，这样还是不会造成递归爆栈，但是当我们把深度广度都提升到10000次就会造成递归爆栈。解决递归爆栈的方法有三种：

加大阈值
循环改写
尾递归优化

因为JavaScript是会运行在浏览器端的，我们不能加大它的内存占用。

以前在V8中是已经是实现了尾递归的，但是它会影响JavaScript的栈的调用顺序，所以最后又删除掉了。如果有兴趣可以去看我另一篇文章尾递归

我们这里只用循环实现防止递归爆栈。

当我们的对象层级特别深事，我们通过递归循环时，会造成递归爆栈，因为一些临时变量会储存在堆栈中，通多深层递归调用，它们的不会被回收，当调用的层级越深自然储存的就越多，最后会导致栈储存不下，也就会造成递归爆栈。

我们可通过自己创建一个栈，栈中储存当前要拷贝的节点，一层一层往下拷贝，所以是一个深度优先的优化。

    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;
    }

详细内容见深拷贝的终极探索

到此就一个深拷贝就结束了

全文总结

我们是在原来的基础上一步一步优化我们自己的深拷贝实现，但是最后的递归爆栈如果在当前文章书写的话，会让当前文章很乱，所以会独立出来一篇文章来记录什么是斐波拉契数列相关的。

我们的大致实现步骤是：

用递归实现一个简单的深拷贝
考虑循环引用问题，通过WeakMap解决
考虑类型问题，处理Function、Map、Set等等
考虑性能问题，递归爆栈问题

到此基本上就实现一个可以使用的深拷贝。

参考

lodash cloneDeep

深浅拷贝原理

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

深拷贝的终极探索