产品或项目开发过程中,经常遇到一些存在上下级关系的树形结构,但在数据库中存储为二维表关系数据的情况。而前端树形控件又要求按照树形层级组织数据,这就存在一个平铺的关系数据转换为树形层级结构的典型问题。
表结构及二维数据示例(以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; } }
标签:code,name,关系数据,二维,树形,allMap,import,id From: https://www.cnblogs.com/zhaoguan_wang/p/18332090