专栏首页flytam之深入前端技术栈如何实现一个惊艳面试官的非递归版本的 js 对象深拷贝方法

如何实现一个惊艳面试官的非递归版本的 js 对象深拷贝方法

众所周知,js 语言本身是不提供对象的深拷贝的功能,无论是直接赋值、Object.assign、展开运算符...都只是浅拷贝,关于 js 的深浅拷贝的一些概念可以参考我比较久以前写过的一篇文章

关于如何实现深拷贝,网上有很多相关的文章和实现都非常完美,本文主要讲述的是用一种非常规的使用非递归方法实现深拷贝

本文的深拷贝只考虑数组对象简单值三种数据类型

要实现判断数据类型,先来实现这 3 个判断类型的工具方法。最通用的就是利用Object.prototype.toString的特性

const getType = v => {
    switch (Object.prototype.toString.call(v)) {
        case "[object Object]":
            return "Object";
        case "[object Array]":
            return "Array";
        default:
            // 只考虑数组和对象,其余都是简单值
            return false;
    }
};

递归实现

在讲述非递归实现之前,先看看递归版本的深拷贝实现,很简单,直接上代码

const copy = source => {
    const _cp = source => {
        let dest;
        const type = getType(source);
        if (type === "Array") {
            dest = [];
            source.forEach((item, index) => {
                dest[index] = _cp(item);
            });
            return dest;
        } else if (type === "Object") {
            dest = {};
            for (let [k, v] of Object.entries(source)) {
                dest[k] = _cp(v);
            }
            return dest;
        } else {
            return source;
        }
    };

    return _cp(source);
};

当然,这种是处理不了循环引用的。处理循环引用也很简单,用个Set记录遍历过的值,每次拷贝前查出Set中存在这个值,就直接返回。所以加上处理循环引用后的代码如下

const copy = source => {
    const set = new Set();
    const _cp = source => {
        let dest;
        if (set.has(source)) {
            return source;
        }
        set.add(source);
        const type = getType(source);
        if (type === "Array") {
            // 数组
            dest = [];
            source.forEach((item, index) => {
                dest[index] = _cp(item);
            });
            return dest;
        } else if (type === "Object") {
            // obj
            dest = {};
            for (let [k, v] of Object.entries(source)) {
                dest[k] = _cp(v);
            }
            return dest;
        } else {
            return source;
        }
    };

    return _cp(source);
};

非递归实现

其实几乎所有的函数递归,都可以使用非递归的方法实现。如果大家有使用 javascript 刷 leetcode 的经历,很多时候如果我们的代码使用递归去解决问题,没有进行尾调用优化(很多时候有的题目确实写不出尾调用优化的写法,也可能我太菜)的时候,是很容易出现 js 调用栈过深出错的情形,这个时候切回成非递归写法就可以,而且很简单

我们简单先了解下 j s 递归的本质。j s 全局是有一个函数调用栈,当我们调用一个函数 a 时,这个函数 a 入栈,函数 a 内再次调用 a 时,一个新的函数 a 再次入栈。执行完毕依次弹出栈。多个函数的话也是类似的流程。用非递归解法的本质就是使用队列或者栈的数据结构来模拟 js 调用栈的执行过程

伪代码如下,百分之 99 的递归都可以用如下的思想实现非递归

  • 声明一个stack变量模拟调用栈 const stack = [];
  • 初始参数入栈 stack.push({ param1, param2 });
  • 栈非空,就一直取栈元素执行 while (stack.length) { const item = stack.pop(); //....... }
  • 如果需要继续下一次递归,将下一次递归调用的参数重新入栈 while(stack.length) { const item = stack.pop() //继续下一次递归 // 每次递归的执行流程 ..... if (condition) { stack.push({{param1:nextParam1,param2:nextParam2}}) } else { .... } }
  • 当前递归终止条件,不入栈即可 while(stack.length) { const item = stack.pop() //继续下一次递归 // 每次递归的执行流程 ..... if (condition) { //... } else { // 递归终止条件。不入栈了 } }

看完这里可能会有疑问,如果每次的递归调用,本次的结果需要是下一次递归的返回值怎么办呢。例如我们上面递归实现的深拷贝

dest[index] = _cp(item);

其实很好理解,递归的时候,当我们的下一级递归返回的时候,我们还能赋值说明在递归场景下,下一级返回后,我们当前级的执行变量还都在我们直接执行就可以,但是非递归情形下当前迭代执行完,是没有上一级的变量的了。这里就需要在每次迭代下一次的时候多传递一个指向当前迭代中需要获取下级结果的变量。(其实就是在递归场景中,下一级递归返回值的设置是在上一级中;非递归场景中,下一级的返回值,是在下一级中调用处理,很类似我们平时传递了一个回调函数的形式)

while(stack.length) {
	const item = stack.pop()
  //继续下一次递归
  //  每次递归的执行流程
  .....
  // 上一级传递的dest
  //
  dest[xx] = xxx
  if (condition) {
    // 注意dest
    stack.push({{param1:nextParam1,param2:nextParam2,dest: {}}})
  } else {
    ....
  }
}

理解到这里,相信大家都知道将类似递归深拷贝转化成非递归实现的大致思路了,其实就是将一个对象,一级一级往下拆分keyvalue的形式进行处理。下面是详细分析

  • 首先,深拷贝是接收一个value然后返回一个拷贝值,所以需要一开始建立一个拷贝值的引用。在迭代的过程中,我们每一级都是对这个引用的子部分进行处理 const copy = source => { // 简单值直接返回 if (!getType(source)) { return source; } // 建立这个最终返回的深拷贝值的本体 let dest = Array.isArray(source) ? [] : {}; //..... };
  • 进行上面提到的模拟调用栈的过程。在递归版本中,我们知道递归函数的入参其实就是这次访问的子节点的值,返回值是当前子节点的拷贝值。前面分析过,迭代调用我们需要传递上一级的创建的引用值进来设置。所以我们迭代调用,每次也有两个值,一个是当前访问节点的原值(和递归调用一样)、用于存储拷贝的引用值(在上一级迭代中创建的) // 调用栈初始状态 const queue = [{ source, dest }]; while (queue.length) { // source 当前访问的节点 // dest 用于存储拷贝的引用值 const { dest, source } = queue.shift(); // 判断访问节点类型 const type = getType(source); // }
  • 每次的迭代处理流程 这里是需要分情况讨论
    • 访问节点是数组 if (type === "Array") { // .... source.forEach((x, index) => { const xType = getType(x); }); }
    • 数组项是对象 (1) if (xType === "Object") { // 生成一个对象引用,给下一次迭代的时候用 dest[index] = {}; // 入栈,需要下一次迭代 queue.push({ source: x, dest: dest[index] }); return; }
    • 数组项是数组(2) if (xType === "Array") { // 生成一个数组引用,给下一次迭代的时候用 dest[index] = []; // 入栈,需要下一次迭代 queue.push({ source: x, dest: dest[index] }); return; }
    • 数组项是简单值。直接设置这个值到dest上 if (!getType(x)) { dest[index] = x; return; }
  • 访问节点是对象。类似于数组处理
    • 对象键是对象
    • 对象键是数组
    • 对象键是简单值

再加上循环引用处理也非常简单,每次迭代的最后将当前source添加到set中。在每次进行处理对象类型的stack.push的时候判断pushsource是否在Set中就可以了,若在Set中说明是循环引用,直接设置值,不进行push

while (stack.lenght) {
    //....
    if (xType === "Object") {
        if (set.has(x)) {
            dest[index] = x;
            return;
        }
        dest[index] = {};
        queue.push({
            source: x,
            dest: dest[index]
        });
        return;
    }
    //....
    set.add(source);
}

最终我们的非递归版本的深拷贝就完成了。虽然花了一些力气,实现这个拷贝,代码也比递归版本复杂很多,性能可能也更差,但是如果能重头看到尾,并且自己实现一遍,相信会大大加深自己对深拷贝的理解和函数递归思想的的理解。下一次面试官让你写深拷贝的时候,你写一个非递归版本的,一定会大大惊艳面试官!

完整代码如下

const copy = source => {
    if (!getType(source)) {
        // 简单值
        return source;
    }
    let dest = Array.isArray(source) ? [] : {};
    const queue = [{ source, dest }];

    const set = new Set([]);

    while (queue.length) {
        const { dest, source } = queue.shift();
        const type = getType(source);
        if (type === "Array") {
            // 数组
            source.forEach((x, index) => {
                const xType = getType(x);
                if (!getType(x)) {
                    dest[index] = x;
                    return;
                }

                if (xType === "Array") {
                    dest[index] = [];
                    queue.push({
                        source: x,
                        dest: dest[index]
                    });
                    return;
                }

                if (xType === "Object") {
                    if (set.has(x)) {
                        dest[index] = x;
                        return;
                    }
                    dest[index] = {};
                    queue.push({
                        source: x,
                        dest: dest[index]
                    });
                    return;
                }
            });
        } else {
            // 对象
            for (let [k, v] of Object.entries(source)) {
                const vType = getType(v);
                if (!vType) {
                    dest[k] = v;
                    continue;
                }
                if (vType === "Array") {
                    dest[k] = [];
                    queue.push({
                        source: v,
                        dest: dest[k]
                    });
                }
                if (vType === "Object") {
                    if (set.has(v)) {
                        dest[k] = v;
                        continue;
                    }
                    dest[k] = {};
                    queue.push({
                        source: v,
                        dest: dest[k]
                    });
                }
            }
        }
        set.add(source);
    }
    return dest;
};

码字不易,如果觉得不错,求给个 star 或者赞吧!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    最近经常看到很多 JavaScript手写代码的文章总结,里面提供了很多 JavaScriptApi的手写实现。

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

    最近经常看到很多 JavaScript手写代码的文章总结,里面提供了很多 JavaScriptApi的手写实现。

    Nealyang
  • 前端应该要掌握的几种手写代码实现

    https://juejin.im/post/5e24590ef265da3e152d27bc

    前端迷
  • 赋值、浅拷贝、深拷贝的区别

    基本类型数据保存在在栈内存中 引用类型数据保存在堆内存中,引用数据类型的变量是一个指向堆内存中实际对象的引用,存在栈中。

    木子星兮
  • JS浅拷贝与深拷贝

    本来只想改变obj2的 value 的值,但是改变之后连obj1的值也一同改变了,很显然,这不是我们想要的的结果。

    九旬
  • 前端进阶第3周打卡题目汇总

    思路大致是这样的,你们也可以根据业务自己封装更复杂的ajax库,比如添加请求响应拦截器

    徐小夕
  • 手写实现深度拷贝

    那么,对一个对象进行拷贝,无非就是对对象的属性进行拷贝,按照拷贝处理的方式不同,可分为浅拷贝和深拷贝:

    请叫我大苏
  • 前端面试拔高题

    对象是 JS 中基本类型之一,而且和原型链、数组等知识息息相关。不管是面试中,还是实际开发中我们都会碰见深拷贝对象的问题。

    李才哥
  • 浅探JavaScript深拷贝和浅拷贝

    对象和数组的拷贝对我来说一直都是一个比较模糊的概念,一直有点一知半解,但是在实际工作中又偶尔会涉及到,有时候还会一不小心掉坑里,不知道大家有没有同样的感受,因此...

    Fundebug
  • JavaScript中的拷贝(copy)

    如果现有var obj1 = {…}这个对象,想要复制对象obj1,一贯的做法就是obj2 = obj1,这时虽然obj2拥有了obj1的所有属性,但obj2却...

    刘亦枫
  • 原生JS灵魂之问,看看你是否熟悉JavaScript?

    笔者最近在对原生JS的知识做系统梳理,因为我觉得JS作为前端工程师的根本技术,学再多遍都不为过。打算来做一个系列,一共分三次发,以一系列的问题为驱动,当然也会有...

    ConardLi
  • javaScript中的浅拷贝 vs 深拷贝

    在前端的数据处理当中,有时候往往需要对原有的数据进行克隆拷贝一份,然后在进行操作,但是又不能影响原来的数据

    itclanCoder
  • 「面试基础小册」数据类型及其延伸

    「面试基础小册」系列正式开写。主要是对一些基础相关的知识进行归纳整理与拓展。后续还有更多,敬请期待

    小皮咖
  • 深拷贝和浅拷贝原来是这样?

    为了让读者更好的理解深浅拷贝,在讲深浅拷贝之前要引入基本数据类型 , 引用数据类型 和 数据储存(栈和堆)这几个概念,如果已经理解,可直接跳过这一part。

    IT人一直在路上
  • JavaScript - 浅拷贝和深拷贝

    注: JSON.stringify()转换对象过程中,undefined、任意的函数以及 symbol 值,在序列化过程中会被忽略(出现在非数组对象的属性值中时...

    愤怒的小鸟
  • 实现浅拷贝与深拷贝

    Js包含基本数据类型与引用数据类型两种不同的数据类型的值,深拷贝与浅拷贝的概念只存在于引用数据类型。对于引用类型,浅拷贝是拷贝了指向这个对象堆内存的指针,是拷贝...

    WindrunnerMax
  • 前端面试题库系列(4)

    defer 是“渲染完再执行”,async 是“下载完就执行”,defer 如果有多个脚本,会按照在页面中出现的顺序加载,多个async 脚本不能保证加载顺...

    李才哥
  • 阿里巴巴内推一面过程

    一面是有个人给我打的电话跟我约了一个面试时间,他们人真的很好,是按你的时间来,如果有事就可以往后延。然后我约了今天晚上7点半,于是就开始了我的一面,我面完试赶紧...

    @零一
  • JavaScript进阶教程(6)—硬核动图让你轻松弄懂递归与深浅拷贝

    递归简单的来说就是程序自己调用自己,就像下面这幅图一样,一直循环往复。就像我们经常听到的小和尚的故事,从前有座山,山里有座庙,庙里有个老和尚和一个小和尚,有一天...

    AlbertYang

扫码关注云+社区

领取腾讯云代金券