不用递归也能实现深拷贝
前言
在现代化的 Web 开发中，深拷贝是一个常见的数据处理需求，它允许我们复制并操作数据，而不影响原始数据。然而，使用递归实现深拷贝的方法可能对性能产生负面影响，特别是在处理大规模数据时。因此，越来越多的前端开发者开始关注另一种不用递归的方式实现深拷贝。
深拷贝的实现方式
我们先来看看常用的深拷贝的实现方式
JSON.parse(JSON.stringify())
利用 JSON.stringify 将对象转成 JSON 字符串，再用 JSON.parse 把字符串解析成新的对象实现深拷贝。
这种方式代码简单，常用于深拷贝简单类型的对象。
在复杂类型的对象上会有问题：
- undefined、function、symbol 会被忽略或者转为 null（数组中）
- 时间对象变成了字符串
- RegExp、Error 对象序列化的结果将只得到空对象
- NaN、Infinity 和-Infinity，则序列化的结果会变成 null
- 对象中存在循环引用的情况也无法正确实现深拷贝
函数库 lodash 的 cloneDeep 方法
这种方式使用简单，而且 cloneDeep 内部是使用递归方式实现深拷贝，因此不会有 JSON 转换方式的问题；但是需要引入函数库 js，为了一个函数而引入一个库总感觉不划算。
递归方法
声明一个函数，函数中变量对象或数组，值为基本数据类型赋值到新对象中，值为对象或数组就调用自身函数。
// 手写深拷贝
function deepCopy(data) {
const map = {
"[object Number]": "number",
"[object Boolean]": "boolean",
"[object String]": "string",
"[object Function]": "function",
"[object Array]": "array",
"[object Object]": "object",
"[object Null]": "null",
"[object Undefined]": "undefined",
"[object Date]": "date",
"[object RegExp]": "regexp",
};
var copyData;
var type = map[Object.prototype.toString.call(data)];
if (type === "array") {
copyData = [];
data.forEach((item) => copyData.push(deepCopy(item)));
} else if (type === "object") {
copyData = {};
for (var key in data) {
copyData[key] = deepCopy(data[key]);
}
} else {
copyData = data;
}
return copyData;
}
递归方式结构清晰将任务拆分成多个简单的小任务执行，可读性强，但是效率低，调用栈可能会溢出，函数每次调用都会在内存栈中分配空间，而每个进程的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致溢出。
深拷贝其实是对树的遍历过程
嵌套对象很像下面图中的树。
递归的思路是遍历 1 对象的属性判断是否是对象，发现属性 2 是一个对象在调用函数本身来遍历 2 对象的属性是否是对象如此反复知道变量 9 对象。
9 对象的属性中没有对象然后返回 5 对象去遍历其他属性是否是对象，没有再返回 2 对象，最后返回到 1 对象发现其 3 属性是一个对象。
最后在找 4 对象。
可以看到递归其实是对树的深度优先遍历。
那么不用递归可以实现树的深度优先遍历么？
答案是肯定的。
不用递归实现深度优先遍历深拷贝
观察递归算法可以发现实现深度优先遍历主要是两个点
- 利用栈来实现深度优先遍历的节点顺序
- 记录哪些节点已经走过了
第一点可以用数组来实现栈
const stack = [source]
while (stack.length) {
const data = stack.pop()
for (let key in data) {
if (typeof source[key] === "object") {
stack.push(data[key])
}
}
}
这样就能把所有的嵌套对象都放入栈中，就可以遍历所有的嵌套子对象。
第二点因为发现对象属性值是对象时会中断当前对象的属性遍历改去遍历子对象，因此要记录对象的遍历的状态。由于 for in 的遍历是无序的即使用一个变量存 key 也没办法知道哪些 key 已经遍历过了，需要一个数组记录所有遍历过的属性。
这里还有另一种简单的方法就是用 Object.keys 来获取对象的 key 数组放到 stack 栈中。
const stack = [...Object.keys(source).map(key => ({ key, source: source }))]
while (stack.length) {
const { key, data } = stack.pop()
if (typeof data[key] === "object") {
stack.push(...Object.keys(data[key]).map(k => ({ key: k, data: data[key] })))
}
}
这样 stack 中深度优先遍历的遍历的对象顺序也记录其中。
这里将代码优化下, 把 Object.keys 换成 Object.entries 更为精简
const stack = [...Object.entries(source)]
while (stack.length) {
const [ key, value ] = stack.pop()
if (typeof value === "object") {
stack.push(...Object.entries(value))
}
}
遍历完成下一步就是创建一个新的对象进行赋值。
const stack = [...Object.entries(source)]
const result = {}
const cacheMap = {}
let id = 0
let cache
while (stack.length) {
const [key, value, id] = stack.pop()
if (id != undefined && cacheMap[id]) {
cache = cacheMap[id]
} else {
cache = result
}
if (typeof value === "object") {
cacheMap[id] = cache[key] = {}
stack.push(...Object.entries(value).map(item => [...item, id++]))
} else {
cache[key] = value
}
}
return result
因为对象时引用类型，因此可以通过 cacheMap[id] 来快速访问 result 的嵌套对象。
代码还可以优化：
cacheMap 可以用 WeakMap 来声明减少 id 的声明：
const stack = [...Object.entries(source)]
const result = {}
const cacheMap = new WeakMap()
let cache
while (stack.length) {
const [key, value, parent] = stack.pop()
if (cacheMap.has(parent)) {
cache = cacheMap.get(parent)
} else {
cache = result
}
if (typeof value === "object") {
cache[key] = {}
cacheMap.set(value, cache[key])
stack.push(...Object.entries(value).map(item => [...item, value]))
} else {
cache[key] = value
}
}
return result
stack 中的数组项中的 parent 可以换成目标对象：
const result = {}
const stack = [...Object.entries(source).map(item => [...item, result])]
while (stack.length) {
const [key, value, target] = stack.pop()
if (typeof value === "object") {
target[key] = {}
stack.push(...Object.entries(value).map(item => [...item, target[key]]))
} else {
target[key] = value
}
}
return result
加上数组的判断最终代码为：
function cloneDeep(source) {
const map = {
"[object Number]": "number",
"[object Boolean]": "boolean",
"[object String]": "string",
"[object Function]": "function",
"[object Array]": "array",
"[object Object]": "object",
"[object Null]": "null",
"[object Undefined]": "undefined",
"[object Date]": "date",
"[object RegExp]": "regexp"
}
const result = Array.isArray(source) ? [] : {}
const stack = [...Object.entries(source).map(item => [...item, result])]
const toString = Object.prototype.toString
while (stack.length) {
const [key, value, target] = stack.pop()
if (map[toString.call(value)] === 'object' || map[toString.call(value)] === 'array') {
target[key] = Array.isArray(value) ? [] : {}
stack.push(...Object.entries(value).map(item => [...item, target[key]]))
} else {
target[key] = value
}
}
return result
}
console.log(cloneDeep({ a: 1, b: '12' }))
//{ a: 1, b: '12' }
console.log(cloneDeep([{ a: 1, b: '12' }, { a: 2, b: '12' }, { a: 3, b: '12' }]))
//[{ a: 1, b: '12' }, { a: 2, b: '12' }, { a: 3, b: '12' }]
广度优先遍历实现深拷贝
同样的思路，实现深拷贝的最终代码为：
function cloneDeep(source) {
const map = {
"[object Number]": "number",
"[object Boolean]": "boolean",
"[object String]": "string",
"[object Function]": "function",
"[object Array]": "array",
"[object Object]": "object",
"[object Null]": "null",
"[object Undefined]": "undefined",
"[object Date]": "date",
"[object RegExp]": "regexp"
}
const result = {}
const stack = [{ data: source, target: result }]
const toString = Object.prototype.toString
while (stack.length) {
let { target, data } = stack.unshift()
for (let key in data) {
if (map[toString.call(data[key])] === 'object' || map[toString.call(data[key])] === 'array') {
target[key] = Array.isArray(data[key]) ? [] : {}
stack.push({ data: data[key], target: target[key] })
} else {
target[key] = data[key]
}
}
}
return result
}
来源：juejin.cn/post/7238978371689136185
