V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
devwolf
V2EX  ›  JavaScript

完全忘了 itemMap[id]还代表了引用

  •  
  •   devwolf · 346 天前 · 1316 次点击
    这是一个创建于 346 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在看一个掘金的帖子 https://juejin.cn/post/6983904373508145189 “扁平数据结构转 Tree”。

    看的时候在想,自己很少用 Map 对象,要不试试用 Map 改造一下,结果改造失败,找了半天原因,靠同事指了出来。

    let arr = [
        { id: 1, name: "部门 1", pid: 0 },
        { id: 2, name: "部门 2", pid: 1 },
        { id: 3, name: "部门 3", pid: 1 },
        { id: 4, name: "部门 4", pid: 3 },
        { id: 5, name: "部门 5", pid: 4 },
    ];
    let result = [];
    function arrayToTree1(items) {
        const result = [];
        const itemMap = {};
    
        for (const item of items) {
            itemMap[item.id] = { ...item, children: [] };
        }
    
        for (const item of items) {
            const id = item.id;
            const pid = item.pid;
            const treeItem = itemMap[id];
            if (pid === 0) {
                result.push(treeItem);
            } else {
                if (!itemMap[pid]) {
                    itemMap[pid] = {
                        children: [],
                    };
                }
                itemMap[pid].children.push(treeItem);
            }
        }
        return result;
    }
    result = arrayToTree1(arr);
    console.log(result);
    console.log("========");
    
    function arrayToTree2(items) {
        const result = [];
        const itemMap = new Map();
        items.map((item, index) => {
            itemMap.set(item.id, { ...item, children: [] });
        });
        items.map((item, index) => {
            const id = item.id;
            const pid = item.pid;
            const treeItem = itemMap.get(id);
    
            if (pid === 0) {
                result.push(treeItem);
            } else {
                if (!itemMap.get(pid)) {
                    itemMap.set(pid, { children: [] });
                }
    
                itemMap.set(pid, {
                    ...itemMap.get(pid),
                    children: itemMap.get(pid).children.concat(treeItem),
                });
            }
        });
        return result;
    }
    result = arrayToTree2(arr);
    console.log(result);
    

    https://i.v2ex.co/1G1gNIox.png

    中途甚至试着问了问 chat ,它没看出来啥区别敷衍了一下我 TAT 。后面我再想想能不能抢救一下 arrayToTree2

    ===接上一贴:裸辞了,但是单子还没提,总之大小领导都通知了。这里的规矩是通知完点头后才能提单子,这会儿学点自己想学的,边休息变沉淀一下了。

    10 条回复    2023-04-19 13:10:26 +08:00
    shakukansp
        1
    shakukansp  
       346 天前   ❤️ 1
    if (!itemMap.get(pid)) {
    itemMap.set(pid, { children: [] });
    }

    const item = itermMap.get(pid)
    item.children.push(treeItem)
    devwolf
        2
    devwolf  
    OP
       346 天前
    @shakukansp 感谢感谢,原来可以这样改,学到了
    shakukansp
        3
    shakukansp  
       346 天前
    @devwolf arrayToTree1 改的是 itemMap[pid]的 chidren
    你原本的写法 arrayToTree2 改的不是 itemMap.get(pid)的值的 children, 而是改了整个 itemMap.get(pid)的值
    TWorldIsNButThis
        4
    TWorldIsNButThis  
       346 天前 via iPhone
    啥意思
    map 里存的是对 obj 的引用?
    shakukansp
        5
    shakukansp  
       346 天前
    简单地说从柜子里面拿出来一个盒子,盒子里面放了另一个盒子,arrayToTree1 是在盒子(itemMap[pid])里面的盒子(children)里加了一个小盒子(treeitem)
    arrayToTree2 是把最外面的大盒子(itemMap.get(pid))整个换掉了,所以你需要做的是不把最外面的盒子换掉,而是先拿出来,再往盒子里面的盒子加小盒子
    devwolf
        6
    devwolf  
    OP
       346 天前
    @TWorldIsNButThis 就是 #5 的那个巧妙的比喻。
    itemMap[pid] 是个`大盒子`,itemMap[pid].children 是一个`中盒子`,treeitem 是`中盒子`里的`小盒子`。
    需要的是更新`中盒子`里的内容,但是 arrayToTree2 中 itemMap.set 的做法改变了`大盒子`——这个角度上来讲,确实 不一样。
    itemMap.set(pid, { ...itemMap.get(pid), children: itemMap.get(pid).children.concat(treeItem)}); 这段写成这样,
    我初衷也是想在拷贝大盒子的同时只更新`中盒子`里的内容,虽然就结果而言并不如我所想的那样,这块我得慢慢悟一下为啥不一样,有成果了就回复你一下(手头来活还在忙别的)
    gitignore
        7
    gitignore  
       346 天前   ❤️ 1
    // normalize 对象,构建索引便于查找
    const map = {};
    for (const item of arr) {
    item.children = [];
    map[item.id] = item;
    }
    // 将对象添加至父节点
    for (const item of arr) {
    const parent = map[item.pid];
    if (parent) {
    parent.children.push(item);
    }
    }
    // pid 为 0 就是根节点
    return arr.filter(item => item.pid == 0);


    =========
    O(N) 复杂度。

    是我不理解题意,还是考虑不周全,还是什么问题 😳
    devwolf
        8
    devwolf  
    OP
       345 天前
    😫完全不记得白天自己看这段代码的时候在想啥了。。。彷佛真在面试现场一样大脑浆糊翻滚,1 楼提醒了也没完全懂用意。
    现在理了一下,确认我之前连 arrayToTree1 都没消化掉。
    结合 shakukansp 的提示,我的理解是:
    [题意] : id 区分每一个值,pid 标记位置,每个 id 按照 pid 来摆放。
    [arrayToTree1] :
    const treeItem = itemMap[id];//treeItem 保存了当前 id 的值

    itemMap[pid].children.push(treeItem);//itemMap 虽然在创建时用 id 作为 key 但可以视作与 id 同值的 pid ,记录一个位置,以此来将 treeItem 放在合适的 children 里

    [arrayToTree2] : 改造后
    const _item = itermMap.get(pid);//这里就是正文里错误代码所欠缺的"盒子"
    _item.children.push(treeItem);//在这个"盒子"里塞东西

    ------------
    天亮我再想想
    devwolf
        9
    devwolf  
    OP
       345 天前
    一个上午的进展:
    let a = {b:1}, c = a;
    console.log(a);// { b: 1 }
    c.b = 2;
    a = {b:3};
    console.log(a);// { b: 3 }
    console.log(c);// { b: 2 }

    let x = new Map(), z = x;
    x['y'] = '方括号表示法 1';
    x.set('y','set 赋值 1')
    console.log(x.y);// 打印"方括号表示法 1"
    console.log(x.get('y')) // 打印"set 赋值 1"

    阶段总结:
    原本以为是“换了一个写法”的"改引用的值还是改引用" 这类问题。
    现在发现 Map 对象用 方括号 /点号表示法 存的位置和 set 不一样 🧐
    devwolf
        10
    devwolf  
    OP
       345 天前
    @gitignore 没啥问题啊,你这个对我而言可读性还更友好了。

    @TWorldIsNButThis 不是这个意思,标题我是在未理解题意的时候起的,现在看来和标题关系不大了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2935 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 11:09 · PVG 19:09 · LAX 04:09 · JFK 07:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.