基于哈希表实现扁平对象数组到多层级树形结构的优化问题

嘿，我来帮你梳理下这个问题！首先得纠正一个小误解：你最开始找到的那个哈希表方案其实是支持多层嵌套的，它之所以看起来好像只能处理单层级，可能是你测试的时候没注意到——因为它的逻辑是通过哈希表快速查找父节点，不管嵌套多少层都能正确挂载子节点。

接下来咱们逐个解决你遇到的两个问题：

问题1：移除无子类节点的空children数组 #

你的第一个需求是不想让没有子节点的对象带上children: []这个空属性。咱们可以在构建完整个树形结构之后，遍历每个节点删掉空的children；不过更高效的方式是只在需要的时候才添加children属性，避免预先创建空数组。修改后的代码如下：

const createDataTree = dataset => {
    const hashTable = Object.create(null);
    const dataTree = [];

    // 第一步：先把所有节点存入哈希表，不预设children属性
    dataset.forEach(aData => {
        hashTable[aData.id] = { ...aData };
    });

    // 第二步：遍历节点，挂载子节点到对应的父节点上
    dataset.forEach(aData => {
        if (aData.parent_id) {
            // 如果父节点还没有children属性，先创建空数组
            if (!hashTable[aData.parent_id].children) {
                hashTable[aData.parent_id].children = [];
            }
            // 将当前节点挂载到父节点的children中
            hashTable[aData.parent_id].children.push(hashTable[aData.id]);
        } else {
            // 没有parent_id的根节点直接加入树形数组
            dataTree.push(hashTable[aData.id]);
        }
    });

    return dataTree;
};

// 测试示例数据
const data = [
   {"id":"m1", "name":"M1"},
   {"id":"m2", "name":"M2"},
   {"parent_id":"m2", "id":"s1", "name":"S1"},
   {"parent_id":"m2", "id":"s2", "name":"S2"},
   {"parent_id":"m2", "id":"s3", "name":"S3"},
   {"parent_id":"s3", "id":"b1", "name":"B1"}
];

console.log(createDataTree(data));

这样处理后，只有真正拥有子节点的对象才会带有children属性，完全符合你的需求。

问题2：关于哈希表和dataTree的“自动更新”疑惑 #

你提到的“hashTable修改后dataTree自动更新”其实是JavaScript引用类型的特性，不是什么魔法：

当我们执行hashTable[aData.id] = { ...aData }时，我们创建了一个新对象，并把这个对象的引用存在哈希表里。之后把hashTable[aData.id]推入dataTree时，其实是把这个对象的引用放进了数组，而非复制新对象。所以后续修改哈希表里的对象（比如添加children并挂载子节点），本质上是在修改同一个对象的内容，dataTree里的引用指向的也是这个对象，自然会同步看到更新后的结果。

关于性能的补充 #

这个哈希表方案的时间复杂度是O(n)，只需要遍历数组两次，不管数组规模多大（哪怕几千条）、嵌套层级有多深（几十层），效率都非常高，几乎是最优实现了，不需要再找更快的方案。

如果需要处理边界情况（比如存在无效的parent_id，指向不存在的节点），可以在挂载子节点时加个判断：

if (aData.parent_id && hashTable[aData.parent_id]) {
    // 仅当父节点存在时才挂载
    if (!hashTable[aData.parent_id].children) {
        hashTable[aData.parent_id].children = [];
    }
    hashTable[aData.parent_id].children.push(hashTable[aData.id]);
}

这样可以避免无效父ID导致的报错。

备注：内容来源于stack exchange，提问作者DHHJ