🔥别再用递归了！WeakMap 的影子索引“让树不再是树！”

一、前言

大家好，我是微澜。今天来分享一个基于 WeakMap 实现的快速对树形结构数据进行增删改查操作的useTree hook函数，它是基于JavaScript 的 WeakMap 特性，在不改动原始数据的前提下，实现了一套 O(1) 查找的影子索引结构，这个影子其实就是对象的引用地址，让树形数据操作像操作数组一样简单！

二、为什么选择 WeakMap？

1. 非侵入性 (Non-invasive)

通过 WeakMap 在内存中构建了一套 Node -> Parent 的映射。原始数据对象保持纯净，没有任何多余属性，完美支持序列化。

2. 内存安全 (Memory Safety)

这是最关键的一点。WeakMap 对键（对象）是弱引用的。

• 如果你删除了原始树中的某个节点，且没有其他地方引用它，垃圾回收器（GC）会自动清理索引表中的对应项。
• 这种特性非常适合处理大型动态树，完全不用担心手动维护索引带来的内存泄漏。

3、不同实现方案对比

在开始之前，我们先看看为什么选择 WeakMap。我们可以通过一个综合对比来看看操作树形数据不同方案的差异：

三、核心实现原理

1. 整体架构图

我们通过一个外部的 WeakMap 来存储节点与其父级的对应关系。这种设计最大的好处是：“不改变原始树结构，不产生循环引用，且能实现 O(1) 的溯源。”

1graph TD
2    A[原始树形数据] --> B{useTree Hook}
3    B -- "1. 递归扫描" --> C[WeakMap 存储库]
4
5    subgraph "WeakMap 存储策略"
6    C -- "Key: 根节点" --> D["Value: 整个 Tree 数组 (方便删除)"]
7    C -- "Key: 子节点" --> E["Value: 直接父节点对象 (实现溯源)"]
8    end
9
10    F[业务请求: 查找/删除] --> C
11    C -- "返回父级引用" --> G[完成操作]
12

2. 数据映射图解 (核心逻辑)

为了让大家更直观地看到 WeakMap 里到底存了什么，我们看下面这个例子：

示例数据：

1const list = [
2  {
3    id: 1, name: '掘金',
4    children: [ { id: 11, name: '前端组' } ]
5  },
6  {
7    id: 2, name: '社区',
8    children: []
9  }
10];
11

WeakMap 内部映射关系：

💡 核心秘诀： 以上设计了一套巧妙的判断规则：如果节点是根节点，其映射值就是数组；如果节点是子节点，其映射值就是父对象。 这样在执行 removeChild 时，我们只需要判断 Array.isArray(parent)，就能自动切换“从数组中删除”根节点或“从 children 属性中删除”子节点的逻辑，极其优雅！

四、useTree()实现方法逐一拆解

接下来，我们看看 useTree 内部每个方法的具体实现原理。

1. initTree - 初始化索引

功能：递归遍历整棵树，建立 WeakMap 映射。

1// 数据索引对象
2const _treeWeakMap = new WeakMap<TreeNode, TreeNode | TreeNode[]>();
3
4const useTree = (
5  props: Props = {
6    // 外部数据对象字段映射
7    treeNodeProp: {
8      value: 'value',
9      label: 'label',
10      children: 'children',
11    }
12  }
13){
14    // 初始化树结构索引
15    function initTree(list, parent){...}
16}
17

1  // 初始化树结构索引
2  function initTree(list: TreeNode[], parent?: TreeNode) {
3    list.forEach((item) => {
4      // 根节点的父级为完整的树数据，在删除根节点时需要通过完整的数组删除
5      _treeWeakMap.set(item, parent || list);
6      if (item[treeNodeProp.children]) {
7        // 删除子节点只需要通过对应子节点的children数组删除
8        initTree(item[treeNodeProp.children], item);
9      }
10    });
11  }
12

原理：在组件挂载或数据更新时调用。通过这种“差异化映射”，我们让每个节点都拥有了一个指向其“归属集合”的指针，也就是指向了父级的引用地址。

以上文的表格列出的示例数据为例，调用initTree方法初始化后，可以得到以下对应关系：

1graph LR
2    subgraph Keys [节点对象 - Key]
3        K11("前端组 (id:11)")
4        K1("掘金 (id:1)")
5        K2("社区 (id:2)")
6    end
7
8    subgraph Values [映射值 - Value]
9        V_Obj1["父节点对象 (id:1)"]
10        V_Arr["根数据数组 [Tree]"]
11    end
12
13    K11 -- "指向直接父级" --> V_Obj1
14    K1 -- "指向所属根数组" --> V_Arr
15    K2 -- "指向所属根数组" --> V_Arr
16
17    style K11 fill:#f9f,stroke:#333
18    style K1 fill:#bbf,stroke:#333
19    style K2 fill:#bbf,stroke:#333
20    style V_Arr fill:#dfd,stroke:#333
21    style V_Obj1 fill:#fff,stroke:#333
22

2. _setParent - 节点索引设置

功能：建立节点与其所属容器（父节点对象或根数组）的映射关系。

1  // 设置节点的父节点映射。为防止用户错误使用，不向外暴露，内部使用
2  function _setParent(node: TreeNode, parent: TreeNode | TreeNode[]) {
3    _treeWeakMap.set(node, parent);
4  }
5

原理：这是对 WeakMap.set 的一层简单封装。通过这种方式，我们将节点对象引用作为 Key，其父级引用作为 Value 存入索引库。通过_前缀标记为私有是为了防止外部直接篡改映射关系，保证索引的单一可靠性。

3. getParent - 获取父节点

功能：获取指定节点的直接父节点。

1  // 获取节点的父节点
2  function getParent(node: TreeNode) {
3    return _treeWeakMap.get(node);
4  }
5

• 原理：利用 WeakMap.get 直接获取。时间复杂度为 O(1)。

4. getParents - 获取全路径父节点

功能：递归向上检索父级，获取从当前节点到根部的所有父节点数组。

1  // 获取节点的所有父节点
2  function getParents(item: TreeNode, parentList: (TreeNode | string)[] = [], key?: string): (TreeNode | string)[] {
3    const parent = _treeWeakMap.get(item);
4    // 递归到根节点数组时停止
5    if (parent && !_isRootNode(parent)) {
6      parentList.push(key ? parent[key] : parent);
7      getParents(parent, parentList, key);
8    }
9    return parentList;
10  }
11  
12  // 判断是否根节点，下文都用这个方法判断是否根节点
13  function _isRootNode(node: TreeNode | TreeNode[]) {
14    return Array.isArray(node);
15  }
16

原理：通过节点自身的引用地址在WeakMap中查找父级。相比于DFS(深度优先遍历)全树，这种垂直爬升的方式效率极高。 什么是垂直爬升？

类似于：

show code is me.parent.parent. ......

就这样，连祖宗十八代都能给你扒出来！

5. addChild - 动态添加节点

功能：向指定节点添加子节点，并自动更新索引。

1  // 添加子节点或根节点，节点不存在.children时，代表添加到根节点数组
2  function addChild(node: TreeNode, child: TreeNode) {
3    if(_isRootNode(node)) {
4      // 根节点数组直接添加
5      const i = node.push(child) - 1;
6      /**
7       * 为新增加的子节点构建一个WeakMap索引，指向父节点
8       * 注意：注册为key的引用地址是经过proxy处理后的节点
9       */
10      node[i] && _setParent(node[i], node);
11    } else {
12      // 非根节点，添加到children数组
13      if (!node[treeNodeProp.children]) {
14        node[treeNodeProp.children] = [];
15      }
16      const i = node[treeNodeProp.children].push(child) - 1;
17      // 和上面设置根节点同理
18      node.children[i] && _setParent(node.children[i], node);
19    }
20  }
21

原理：在操作原始数据的同时，同步更新 WeakMap索引。也就是为新增的对象建立父级索引。

注意：这里不能把新添加的child对象当做WeakMap的Key，因为child只是一个外部传入的一个临时变量，还没有和整棵树建立联系，需要在添加到树当中后，获取树当中的对象地址作为Key建立索引。

6. removeChild - 删除指定节点

功能：无痛删除任意节点，无需手动遍历查找。

1  // 删除指定子节点
2  function removeChild(node: TreeNode) {
3    // 找到父节点，通过父节点删除
4    const parent = getParent(node);
5    if(!parent) {
6      // 没有找到父级节点，抛出错误
7      throw new Error('没有找到父级节点！');
8    }
9    if(_isRootNode(parent)) {
10      // 删除根节点
11      const index = parent.findIndex((item: TreeNode) => item === node);
12      if(index >= 0) {
13        parent.splice(index, 1);
14      } else {
15        // 没有找到要删除的根节点，抛出错误
16        throw new Error('没有找到要删除的根节点！');
17      }
18    } else {
19      // 通过找到父级删除自己
20      parent.children = parent.children.filter((item: TreeNode) => item !== node);
21    }
22  }
23

原理：这是该方案最精妙的地方！通过 initTree 建立的差异化映射，我们只需要简单的 Array.isArray 判断，就能准确找到节点所在的“容器”，实现秒删。

五、完整代码实现

代码不多，却能快速~实现对树形数据的增删改查操作。

1// useTree.ts
2
3type Props = {
4  // 树形数据字段名映射类型
5  treeNodeProp: TreeNodeProp
6}
7
8// 树节点属性映射类型
9type TreeNodeProp = {
10  value: string;
11  label: string;
12  children: string;
13}
14
15// 数节点
16type TreeNode = any
17
18/**
19 * 树结构索引数据
20 * key为节点本身，value为父节点或根节点数组(即整棵树)
21 * 如果value为Array，代表根节点数组
22 * 如果value为Object，代表子节点
23 */
24const _treeWeakMap = new WeakMap<TreeNode, TreeNode | TreeNode[]>();
25
26// 使用weakmap构建树形数据数据索引
27export const useTree = (
28  props: Props = {
29    // 外部数据对象字段映射
30    treeNodeProp: {
31      value: 'value',
32      label: 'label',
33      children: 'children',
34    }
35  }
36) => {
37  const { treeNodeProp } = props;
38
39  // 设置节点的父节点映射。为防止用户错误使用，不向外暴露，内部使用
40  function _setParent(node: TreeNode, parent: TreeNode | TreeNode[]) {
41    _treeWeakMap.set(node, parent);
42  }
43
44  // 判断是否根节点
45  function _isRootNode(node: TreeNode | TreeNode[]) {
46    return Array.isArray(node);
47  }
48
49  // 初始化树结构索引
50  function initTree(list: TreeNode[], parent?: TreeNode) {
51    list.forEach((item) => {
52      // 根节点的父级为完整的树数据，在删除根节点时需要通过完整的数组删除
53      _treeWeakMap.set(item, parent || list);
54      if (item[treeNodeProp.children]) {
55        // 删除子节点只需要通过对应子节点的children数组删除
56        initTree(item[treeNodeProp.children], item);
57      }
58    });
59  }
60
61  // 添加子节点或根节点，节点不存在.children时，代表添加到根节点数组
62  function addChild(node: TreeNode, child: TreeNode) {
63    if(_isRootNode(node)) {
64      // 根节点数组直接添加
65      const i = node.push(child) - 1;
66      /**
67       * 为新增加的子节点构建一个WeakMap索引，指向父节点
68       * 注意：注册为key的引用地址是经过proxy处理后的节点
69       */
70      node[i] && _setParent(node[i], node);
71    } else {
72      // 非根节点，添加到children数组
73      if (!node[treeNodeProp.children]) {
74        node[treeNodeProp.children] = [];
75      }
76      const i = node[treeNodeProp.children].push(child) - 1;
77      // 和上面设置根节点同理
78      node.children[i] && _setParent(node.children[i], node);
79    }
80  }
81
82  // 删除指定子节点
83  function removeChild(node: TreeNode) {
84    // 找到父节点，通过父节点删除
85    const parent = getParent(node);
86    if(!parent) {
87      // 没有找到父级节点，抛出错误
88      throw new Error('没有找到父级节点！');
89    }
90    if(_isRootNode(parent)) {
91      // 删除根节点
92      const index = parent.findIndex((item: TreeNode) => item === node);
93      if(index >= 0) {
94        parent.splice(index, 1);
95      } else {
96        // 没有找到要删除的根节点，抛出错误
97        throw new Error('没有找到要删除的根节点！');
98      }
99    } else {
100      // 通过找到父级删除自己
101      parent.children = parent.children.filter((item: TreeNode) => item !== node);
102    }
103  }
104
105  // 获取节点的父节点
106  function getParent(node: TreeNode) {
107    return _treeWeakMap.get(node);
108  }
109
110  // 获取节点的所有父节点
111  function getParents(item: TreeNode, parentList: (TreeNode | string)[] = [], key?: string): (TreeNode | string)[] {
112    const parent = _treeWeakMap.get(item);
113    // 递归到根节点数组时停止
114    if (parent && !_isRootNode(parent)) {
115      parentList.push(key ? parent[key] : parent);
116      getParents(parent, parentList, key);
117    }
118    return parentList;
119  }
120
121  // 获取节点的所有父节点label数组
122  function getParentLabels(item: TreeNode, labelList: string[] = []): string[] {
123    return getParents(item, labelList, treeNodeProp.label) as string[];
124  }
125
126  // 获取节点的所有父节点value数组
127  function getParentValues(item: TreeNode, valueList: string[] = []): string[] {
128    return getParents(item, valueList, treeNodeProp.value) as string[];
129  }
130
131  return {
132    getParents,
133    getParentLabels,
134    getParentValues,
135    getParent,
136    initTree,
137    addChild,
138    removeChild,
139  };
140};
141
142

六、总结

通过 WeakMap 实现的 useTree，核心优势在于解耦。它将“业务数据”与“层级关系”分离开来，既保证了数据的纯净，又获得了极高的查找性能。

WeakMap 作为一个容易被忽视的原生特性，在处理这类关联关系映射时有着天然的优势。

如果你也在为复杂树结构的管理发愁，不妨尝试下这种“影子索引”的思路。

如有不足或可优化的地方，欢迎在评论区交流讨论，如果觉得有用，点个👍也挺好的！👏

如果你在处理大型树形表格或复杂的组织架构，这个 Hook 绝对是你的提效神器！

七、预览和源码地址

多场景演示 (Demo)

• 项目预览总入口: java6688.github.io/Tree_By_Wea…
• 原生 HTML 版本: java6688.github.io/Tree_By_Wea…
• Vue 3 + Element+ 版本: java6688.github.io/Tree_By_Wea…
• React + AntD 版本: java6688.github.io/Tree_By_Wea…

项目源码地址

github：https://github.com/java6688/Tree_By_WeakMap

《🔥别再用递归了！WeakMap 的影子索引“让树不再是树！”》 是转载文章，点击查看原文。