lhajh

如何实现一个深拷贝

2019/01/08

引言

上篇文章详细介绍了浅拷贝和浅拷贝，并对其进行了模拟实现，在实现的过程中，介绍了很多基础知识。今天这篇文章我们来看看一道必会面试题，即如何实现一个深拷贝。本文会详细介绍对象、数组、循环引用和引用丢失等情况下的深拷贝实践。

第一步：简单实现

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

根据上篇文章内容，我们可以写出简单浅拷贝代码如下。

function cloneShallow(source) {
  var target = {};
  for (var key in source) {
    if (Object.prototype.hasOwnProperty.call(source, key)) {
      target[key] = source[key];
    }
  }
  return target;
}

// 测试用例
var a = {
  name: "lhajh",
  book: {
      title: "You Don't Know JS",
      price: "45"
  },
  a1: undefined,
  a2: null,
  a3: 123
}
var b = cloneShallow(a);

a.name = "高级前端进阶";
a.book.price = "55";

console.log(b);
// {
//   name: 'lhajh',
//   book: { title: 'You Don\'t Know JS', price: '55' },
//   a1: undefined,
//   a2: null,
//   a3: 123
// }

上面代码是浅拷贝实现，只要稍微改动下，加上是否是对象的判断并在相应的位置使用递归就可以实现简单深拷贝。

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

// 使用上面测试用例测试一下
var b = cloneDeep1(a);
console.log(b);
// {
//   name: 'lhajh',
//   book: { title: 'You Don\'t Know JS', price: '45' },
//   a1: undefined,
//   a2: {},
//   a3: 123
// }

一个简单的深拷贝就完成了，但是这个实现还存在很多问题。

  • 1、没有对传入参数进行校验，传入 null 时应该返回 null 而不是 {}

  • 2、对于对象的判断逻辑不严谨，因为 typeof null === 'object'

  • 3、没有考虑数组的兼容

第二步：拷贝数组

我们来看下对于对象的判断。

function isObject(obj) {
  return Object.prototype.toString.call(obj) === '[object Object]';
}

但是用在这里并不合适，因为我们要保留数组这种情况，所以这里使用 typeof 来处理。

typeof null //"object"
typeof {} //"object"
typeof [] //"object"
typeof function foo(){} //"function" (特殊情况)

改动过后的isObject 判断逻辑如下。

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

// 使用上面测试用例测试一下
var b = cloneDeep2(a);
console.log(b);
// {
//   name: 'lhajh',
//   book: { title: 'You Don\'t Know JS', price: '45' },
//   a1: undefined,
//   a2: null,
//   a3: 123
// }

第三步：循环引用

我们知道 JSON 无法深拷贝循环引用，遇到这种情况会抛出异常。

// 此处 a 是文章开始的测试用例
a.circleRef = a;

JSON.parse(JSON.stringify(a));
// TypeError: Converting circular structure to JSON

1、使用哈希表

解决方案很简单，其实就是循环检测，我们设置一个数组或者哈希表存储已拷贝过的对象，当检测到当前对象已存在于哈希表中时，取出该值并返回即可。

function cloneDeep3(source, hash = new WeakMap()) {
  if (!isObject(source)) return source;
  if (hash.has(source)) return hash.get(source); // 新增代码，查哈希表
  var target = Array.isArray(source) ? [] : {};
  hash.set(source, target); // 新增代码，哈希表设值
  for(var key in source) {
    if (Object.prototype.hasOwnProperty.call(source, key)) {
      if (isObject(source[key])) {
        target[key] = cloneDeep3(source[key], hash); // 新增代码，传入哈希表
      } else {
        target[key] = source[key];
      }
    }
  }
  return target;
}

测试一下，看看效果如何。

// 此处 a 是文章开始的测试用例
a.circleRef = a;

var b = cloneDeep3(a);
console.log(b);
// {
// 	name: "lhajh",
// 	a1: undefined,
//	a2: null,
// 	a3: 123,
// 	book: {title: "You Don't Know JS", price: "45"},
// 	circleRef: {name: "lhajh", book: {…}, a1: undefined, a2: null, a3: 123, …}
// }

完美！

2、使用数组

这里使用了 ES6 中的 WeakMap 来处理，那在 ES5 下应该如何处理呢？

也很简单，使用数组来处理就好啦，代码如下。

function cloneDeep3(source, uniqueList) {
  if (!isObject(source)) return source;
  if (!uniqueList) uniqueList = []; // 新增代码，初始化数组
  var target = Array.isArray(source) ? [] : {};
  // ============= 新增代码
  // 数据已经存在，返回保存的数据
  var uniqueData = find(uniqueList, source);
  if (uniqueData) {
    return uniqueData.target;
  };
  // 数据不存在，保存源数据，以及对应的引用
  uniqueList.push({
    source: source,
    target: target
  });
  // =============
  for(var key in source) {
    if (Object.prototype.hasOwnProperty.call(source, key)) {
      if (isObject(source[key])) {
        target[key] = cloneDeep3(source[key], uniqueList); // 新增代码，传入数组
      } else {
        target[key] = source[key];
      }
    }
  }
  return target;
}

// 新增方法，用于查找
function find(arr, item) {
  for(var i = 0; i < arr.length; i++) {
    if (arr[i].source === item) {
      return arr[i];
    }
  }
  return null;
}

// 用上面测试用例已测试通过

现在已经很完美的解决了循环引用这种情况，那其实还是一种情况是引用丢失，我们看下面的例子。

var obj1 = {};
var obj2 = {a: obj1, b: obj1};

obj2.a === obj2.b;
// true

var obj3 = cloneDeep2(obj2);
obj3.a === obj3.b;
// false

引用丢失在某些情况下是有问题的，比如上面的对象 obj2，obj2 的键值 a 和 b 同时引用了同一个对象 obj1，使用cloneDeep2 进行深拷贝后就丢失了引用关系变成了两个不同的对象，那如何处理呢。

其实你有没有发现，我们的 cloneDeep3 已经解决了这个问题，因为只要存储已拷贝过的对象就可以了。

var obj3 = cloneDeep3(obj2);
obj3.a === obj3.b;
// true

完美！

Search

    Post Directory