产品或项目开发过程中，经常遇到一些存在上下级关系的树形结构，但在数据库中存储为二维表关系数据的情况。而前端树形控件又要求按照树形层级组织数据，这就存在一个平铺的关系数据转换为树形层级结构的典型问题。
表结构及二维数据示例（以id，parentid自关联为例）：
Create Table TreeData(id varchar(36), code varchar(50), name narchar(100), parentid varchar(36)); [{id: "", code: "", name: "", parentid: ""}]
期望的数据示例：
[{ id: "", code: "", name: "", parentid: "", subNodes: [{ id: "", code: "", name: "", parentid: "", subNodes: [] } ] } ]
在实际编码过程，我们可以采用嵌套循环或递归等方式处理，但如果遇到数据量较大、层级较深且层级不固定等场景，此种实现性能不佳。从时间复杂度来说，是O(n2).
之前在几次性能优化时，采用过一个方法，先构造全量数据的HashMap，然后再快速将自身加到父对象的子节点集合，此方式性能稳定、时间复杂度为O(n)，经过实际验证效果也不错（5k节点时间消耗从>700ms优化到<100ms），在此记录备忘。
import lombok.Data; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; @Data public class Func { private String id; private String code; private String name; private String parentId; private List<Func> subNodes; public List<Func> BuildTreeData(List<Func> orignList) { Map<String, Func> allMap = new HashMap<>(); List<Func> rootList = new ArrayList<>(); for (Func func : orignList) { allMap.put(func.getId(), func); } for (Map.Entry<String, Func> map : allMap.entrySet()) { if (allMap.containsKey(map.getValue().getParentId())) { Func parent = allMap.get(map.getValue().getParentId()); if (parent.getSubNodes() == null) { parent.setSubNodes(new ArrayList<>()); } parent.getSubNodes().add(map.getValue()); } else { rootList.add(map.getValue()); } } return rootList; } }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。