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

在看一个掘金的帖子 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

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

devwolf

2023-04-18 15:55:01 +08:00

@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

2023-04-18 18:05:29 +08:00

// 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

2023-04-18 22:39:47 +08:00

😫完全不记得白天自己看这段代码的时候在想啥了。。。彷佛真在面试现场一样大脑浆糊翻滚,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

2023-04-19 11:17:36 +08:00

一个上午的进展：
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 不一样 🧐