前言:js如何实现一个深拷贝
这是一个老生常谈的问题,也是在求职过程中的高频面试题,考察的知识点十分丰富,本文将对浅拷贝和深拷贝的区别、实现等做一个由浅入深的梳理。
赋值、浅拷贝与深拷贝的区别
在js中,变量类型分为基本类型和引用类型。对变量直接进行赋值拷贝:
- 对于基本类型,拷贝的是存储在栈中的值
- 对于引用类型,拷贝的是存储在栈中的指针,指向堆中该引用类型数据的真实地址
直接拷贝引用类型变量,只是复制了变量的指针地址,二者指向的是同一个引用类型数据,对其中一个执行操作都会引起另一个的改变。
关于浅拷贝和深拷贝:
- 浅拷贝是对于原数据的准确拷贝,假如子数据为基本类型,则拷贝值;假如为引用类型,则拷贝地址,二者共享内存空间,对其中一个修改也会影响另一个
- 深拷贝则是开拓新的内存空间,对原数据的完全复制
因而,浅拷贝与深拷贝根本上的区别是 能否共享内存空间 。简单来讲,深拷贝就是对原数据递归进行浅拷贝。
三者的简单比较如下:
| 能否指向原数据 | 子数据为基本类型 | 子数据包含引用类型 | |
|---|---|---|---|
| 赋值 | 是 | 改变时原数据改变 | 改变时原数据改变 |
| 浅拷贝 | 否 | 改变时原数据 不改变 | 改变时原数据改变 |
| 深拷贝 | 否 | 改变时原数据 不改变 | 改变时原数据 不改变 |
原生浅拷贝方法
数组和对象中常见的浅拷贝方法有以下几种:
- Array.prototype.slice
- Array.prototype.concat
- Array.from
- Object.assign
- ES6解构
使用下面的 用例 1.test.js 进行测试:
const arr = ['test', { foo: 'test' }]const obj = { str: 'test', obj: { foo: 'test' }}const arr1 = arr.slice()const arr2 = arr.concat()const arr3 = Array.from(arr)const arr4 = [...arr]const obj1 = Object.assign({}, obj)const obj2 = {...obj}//修改arrarr[0] = 'test1'arr[1].foo = 'test1'// 修改objobj.str = 'test1'obj.obj.foo = 'test1'结果如下:
image
可以看到经过浅拷贝以后,我们去修改原对象或者数组中的基本类型数据,拷贝后的相应数据未发生改变;而修改原对象或者数组中的引用类型数据,拷贝后的数据会发生相应变化,它们共享同一内存空间
深拷贝实现
这里我们列举常见的深拷贝方法并尝试自己手动实现,最后对它们做一个总结、比较
1. JSON序列化快速实现
使用 JSON.parse(JSON.stringify(data)) 来实现深拷贝,这种方法基本可以涵盖90%的使用场景,但它也有其不足之处,涉及到下面这几种情况下时则需要考虑使用其余方法来实现深拷贝:
JSON.parse只能序列化能够被解决为JSON格式的数据,因而无法解决以下数据- 特殊数据例如
undefined、NaN、Infinity等 - 特殊对象如时间对象、正则表达式、函数、Set、Map等
- 对于循环引用(例如环)等无法解决,会直接报错
- 特殊数据例如
JSON.parse只能序列化对象可枚举的自身属性,因而会丢弃构造函数的constructor
使用下面的 用例 2.test.js 来对基本类型进行验证:
const data = { a: 1, b: 'str', c: true, d: null, e: undefined, f: NaN, g: Infinity,}const dataCopy = JSON.parse(JSON.stringify(data))可以看到 NaN 、 Infinity 在序列化的过程中被转化为了 null ,而 undefined 则丢失了:
image
再使用 用例 3.test.js 对引用类型进行测试:
const data = { a: [1, 2, 3], b: {foo: 'obj'}, c: new Date('2019-08-28'), d: /^abc$/g, e: function() {}, f: new Set([1, 2, 3]), g: new Map([['foo', 'map']]),}const dataCopy = JSON.parse(JSON.stringify(data))对于引用类型数据,在序列化与反序列化过程中,只有数组和对象被正常拷贝,其中时间对象被转化为了字符串,函数会丢失,其余的都被转化为了空对象:
image
利用 用例 4.test.js 对构造函数进行验证:
function Person(name) { // 构造函数实例属性name this.name = name // 构造函数实例方法getName this.getName = function () { return this.name }}// 构造函数原型属性agePerson.prototype.age = 18const person = new Person('xxx')const personCopy = JSON.parse(JSON.stringify(person))在拷贝过程中只会序列化对象可枚举的自身属性,因而无法拷贝 Person 上的原型属性 age ;因为序列化的过程中构造函数会丢失,所以 personCopy 的 constructor 会指向顶层的原生构造函数 Object 而不是自己设置构造函数Person
image
2. 手动实现深拷贝方法
简单版
我们先来实现一个简单版的深拷贝,思路是,判断data类型,若不是引用类型,直接返回;假如是引用类型,而后判断data是数组还是对象,并对data进行递归遍历,如下:
function cloneDeep(data) { if(typeof data !== 'object') return data const retVal = Array.isArray(data) ? [] : {} for(let key in data) { retVal[key] = deepClone(data[key]) } return retVal}执行 用例 clone1.test.js :
const data = { str: 'test', obj: { foo: 'test' }, arr: ['test', {foo: 'test'}]}const dataCopy = cloneDeep(data)可以看到对于对象和数组能够实现正确的拷贝
image
首先是只考虑了对象和数组这两种类型,其余引用类型数据仍然与原数据共享同一内存空间,有待完善;其次,对于自己设置的构造函数而言,在拷贝的过程中会丢失实例对象的 constructor ,因而其构造函数会变为默认的 Object
解决其余数据类型
在上一步我们实现的简单深拷贝,只考虑了对象和数组这两种引用类型数据,接下来将对其余常用数据结构进行相应的解决
定义通用方法
我们首先定义一个方法来正确获取数据的类型,这里利用了 Object 原型对象上的 toString 方法,它返回的值为 [object type] ,我们截取其中的type就可。而后定义了数据类型集合的常量,如下:
const getType = (data) => { return Object.prototype.toString.call(data).slice(8, -1)}const TYPE = { Object: 'Object', Array: 'Array', Date: 'Date', RegExp: 'RegExp', Set: 'Set', Map: 'Map',}接着我们完善对于其余类型的解决,这里可以将深拷贝划分为两步,首先是对数据的初始化,而后是对可遍历对象的遍历操作
初始化
根据不同的data类型,对拷贝后的值进行了相应的初始化解决:
function dataInit(data, type) { const reFlags = /\w*$/ const Constructor = data.constructor switch(type) { case TYPE.Object: // 获取原对象的原型 return Object.create(Object.getPrototypeOf(data)) case TYPE.Array: return [] case TYPE.Date: // 特殊解决Date return new Constructor(data.getTime()) case TYPE.RegExp: // 特殊解决regexp,拷贝过程中lastIndex属性会丢失 const reg = new Constructor(data.source, reFlags.exec(data)) reg.lastIndex = data.lastIndex return reg case TYPE.Set: case TYPE.Map: return new Constructor() default: return data }}遍历数据
在主函数中,对于可遍历数据类型进行了递归遍历。其中, Symbol 类型在赋值语句中被当做标识符时(例如对象的键名),此时该属性是匿名且不可枚举的,因此不会在 for...in 循环中被捕获,也不会被 Object.getOwnPropertyNames 返回,只能通过原始symbol值或者 Object.getOwnPropertySymbols 方法获取
function cloneDeep(data) { const dataType = getType(data) // 假如是其余类型,直接返回 if(!TYPE[dataType]) return data // 初始化data const retVal = dataInit(data, dataType) // 遍历可遍历类型 switch (dataType) { case TYPE.Array: data.forEach(value => retVal.push(cloneDeep(value))) break case TYPE.Object: for (let key in data) { // 不考虑继承的属性 if (data.hasOwnProperty(key)) { retVal[key] = cloneDeep(data[key]) } } // 解决Object中Symbol类型的键名 Object.getOwnPropertySymbols(data).forEach(symbol => { retVal[symbol] = cloneDeep(data[symbol]) }) break case TYPE.Set: data.forEach(value => retVal.add(cloneDeep(value))) break case TYPE.Map: for (let [mapKey, mapValue] of data) { // Map的键、值都可以是引用类型,因而都需要拷贝 retVal.set(cloneDeep(mapKey), cloneDeep(mapValue)) } break } return retVal}上面的代码完整版可以参考 clone2.js ,接下来使用 用例 clone2.test.js 进行验证:
const symbol = Symbol('sym')const data = { obj: {}, arr: [], reg: /reg/g, date: new Date('2019'), person: new Person('lixx'), [symbol]: 'symbol', set: new Set([{test: 'set'}]), map: new Map([[{key: 'map'}, {value: 'map'}]])}function Person(name) { this.name = name}const dataClone = cloneDeep(data)可以看到对于不同类型的引用数据都能够实现正确拷贝,结果如下:
image
关于函数
函数的拷贝我这里没有实现,两个对象中的函数使用同一个内存空间并没有什么问题。实际上,查看了 lodash/cloneDeep 的相关实现后,对于函数它是直接返回的:
image
到这一步,我们的深拷贝方法已经初具雏形,实际上需要特殊解决的数据类型远不止这些,还有 Error 、 Buffer 、 Element 等,有兴趣的小伙伴可以继续探究实现一下~
解决循环引用
目前为止深拷贝能够解决绝大部分常用的数据结构,但是当数据中出现了循环引用时它就束手无策了
const a = {}a.a = acloneDeep(a)可以看到,对于循环引用,在进行递归调用的时候会变成死循环而导致栈溢出:
image
那么如何破解呢?
抛开循环引用不谈,我们先来看看基本的 引用 问题,前文所实现的深拷贝方法以及 JSON 序列化拷贝都会解除原引用类型对于其余数据的引用,来看下面这个例子:
const temp = {}const data = { a: temp, b: temp,}const dataJson = JSON.parse(JSON.stringify(data))const dataClone = deepClone(data)验证一下引用关系:
image
假如解除这种引用关系是你想要的,那完全ok。假如你想保持数据之间的引用关系,那么该如何去实现呢?
一种做法是可以用一个数据结构将已经拷贝过的内容存储起来,而后在每次拷贝之前进行查询,假如发现已经拷贝过了,直接返回存储的拷贝值就可保持原有的引用关系。
由于能够被正确拷贝的数据均为引用类型,所以我们需要一个 key-value 且 key 可以是引用类型的数据结构,自然想到可以利用 Map/WeakMap 来实现。
这里我们利用一个 WeakMap 的数据结构来保存已经拷贝过的结构, WeakMap 与 Map 最大的不同,就是它的键是弱引用的,它对于值的引用不计入垃圾回收机制,也就是说,当其余引用都解除时,垃圾回收机制会释放该对象的内存;如果使用强引用的 Map ,除非手动解除引用,否则这部分内存不会得到释放,容易造成内存泄漏。
具体的实现如下:
function cloneDeep(data, hash = new WeakMap()) { const dataType = getType(data) // 假如是其余类型,直接返回 if(!TYPE[dataType]) return data // 查询能否已拷贝 if(hash.has(data)) return hash.get(data) const retVal = dataInit(data, dataType) // 对于循环引用,需要在递归循环之前写入hash,否则栈仍旧会溢出 hash.set(data, retVal) switch (dataType) { case TYPE.Array: data.forEach(value => retVal.push(cloneDeep(value, hash))) break case TYPE.Object: for (let key in data) { // 不考虑继承的属性 if (data.hasOwnProperty(key)) { retVal[key] = cloneDeep(data[key], hash) } } // 解决Object中Symbol类型的键名 Object.getOwnPropertySymbols(data).forEach(symbol => { retVal[symbol] = cloneDeep(data[symbol], hash) }) break case TYPE.Set: data.forEach(value => retVal.add(cloneDeep(value, hash))) break case TYPE.Map: for (let [mapKey, mapValue] of data) { // Map的键、值都可以是引用类型,因而都需要拷贝 retVal.set(cloneDeep(mapKey, hash), cloneDeep(mapValue, hash)) } break } return retVal}经过改造后的深拷贝函数能够保留原数据的引用关系,也可以正确解决不同引用类型的循环引用,利用下面的用例 clone3.test.js 来进行验证:
const temp = {}const data = { a: temp, b: temp,}const dataClone = deepClone(data)const obj = {}obj.obj = objconst arr = []arr[0] = arrconst set = new Set()set.add(set)const map = new Map()map.set(map, map)结果如下:
image
思考:使用非递归
在前面的深拷贝实现方法中,均是通过递归的方式来进行遍历,当递归的层级过深时,也会出现栈溢出的情况,我们使用下面的 create 方法创立深度为10000,广度为100的示例数据:
function create(depth, breadth) { const data = {} let temp = data let i = j = 0 while(i < depth) { temp = temp['data'] = {} while(j < breadth) { temp[j] = j j++ } i++ } return data}const data = create(10000, 100)cloneDeep(data)结果如下:
image
那么如果不使用递归,我们应该如何实现呢?
以对象为例,存在下面这样一个数据结构:
const data = { left: 1, right: { left: 1, right: 2, }}那么换个角度看,其实它就是一个类树形结构:
image<br />我们对该对象进行遍历实际上相当于模拟对树的遍历。树的遍历主要分为深度优先遍历和广度优先遍历,前者一般借助栈来实现,后者一般借助队列来实现。
这里模拟了树的深度优先遍历,仅考虑对象和非对象,利用栈来实现一个不使用递归的简单深拷贝方法:
function cloneDeep(data) { const retVal = {} const stack = [{ target: retVal, source: data, }] // 循环整个stack while(stack.length > 0) { // 栈顶节点出栈 const node = stack.pop() const { target, source } = node // 遍历当前节点 for(let item in source) { if (source.hasOwnProperty(item)) { if (Object.prototype.toString.call(source[item]) === '[object Object]') { target[item] = {} // 子节点假如是对象,将该节点入栈 stack.push({ target: target[item], source: source[item], }) } else { // 子节点假如不是对象,直接拷贝 target[item] = source[item] } } } } return retVal}关于完整的深拷贝非递归实现,可以参考 clone4.js ,对应的测试用例为 用例 clone4.test.js ,这里就不给出了
3. 深拷贝方法比较
这里列举了常见的几种深拷贝方法,并进行简单比较
- JSON.parse(JSON.stringify(data))
- jQuery中的$.extend
- 我们这里自己实现的clone3.js中的cloneDeep
- loadsh中的_.cloneDeep
关于耗时比较,采用前文的 create 方法创立了一个广度、深度均为1000的数据,在 node v10.14.2 环境下循环执行以下方法各10000次,这里的耗时取值为运行十次测试用例的平均值,如下:
| 基本类型 | 数组、对象 | 特殊引用类型 | 循环引用 | 耗时 | |
|---|---|---|---|---|---|
| JSON | 无法解决 NaN 、 Infinity 、 Undefined | 丢失对象原型 | ? | ? | 7280.6ms |
| $.extend | 无法解决 Undefined | 丢失对象原型、拷贝原型属性 | ?<br />(使用同一引用) | ? | 5550.6ms |
| cloneDeep | ?? | ?? | ??(待完善) | ?? | 5035.3ms |
| _.cloneDeep | ?? | ?? | ?? | ?? | 5854.5ms |
在日常的使用过程中,假如你确定你的数据中只有数组、对象等常见类型,你大可以放心使用JSON序列化的方式来进行深拷贝,其它情况下还是推荐引入 loadsh/cloneDeep 来实现
小结
深拷贝的水很“深”,浅拷贝也不“浅”,小小的深拷贝里面蕴含的知识点十分丰富:
- 考虑问题能否全面、严谨
- 基础知识、api熟练程度
- 对数据类型的了解
- 递归/非递归(循环)
- 树的遍历(港真,能扯到这里,可问的点就很多了)
- Symbol、Set、Map/WeakMap等
我相信,要是面试官愿意挖掘的话,能考查的知识点远不止这么多,这个时候就要考验你的基本功和知识面的深度了,总而言之,面试是一个双向选择的过程,也是一个展现自己的机会,能多bb就不写代码好吧(逃
本文如有错误,还请各位批评指正~
参考
- MDN – Symbol
- MDN – WeakMap
- loadsh/deepClone
- 完整的示例和测试代码:github/lvqq/cloneDeep
原文链接:深拷贝实践