···
public class TreeBuilderTest {
private <E, ID> Node<E> buildTree(Collection<E> elements, Function<E, ID> getId, Function<E, ID> getParentId) {
Map<ID, Node<E>> idNodeMap =
elements.stream().collect(Collectors.toMap(getId, Node::new));
Node<E> root = null;
for (E element : elements) {
ID parentId = getParentId.apply(element);
ID selfId = getId.apply(element);
Node<E> selfNode = idNodeMap.get(selfId);
if (idNodeMap.containsKey(parentId)) {
Node<E> parentNode = idNodeMap.get(parentId);
parentNode.children.add(selfNode);
selfNode.parent = parentNode;
} else {
if (root != null) {
throw new IllegalArgumentException("root node more than one");
}
root = selfNode;
}
}
Objects.requireNonNull(root, "there is not root node");
return root;
}
@
Test public void test() {
Random random = new SecureRandom();
List<TestData> resultFromSql = IntStream.range(0, 100_000)
.mapToObj(i -> new TestData(i, random))
.collect(Collectors.toList());
long startTime = System.nanoTime();
Node<TestData> testDataNode = buildTree(resultFromSql, e ->
e.id, e -> e.parentId);
System.out.println("cost = " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime));
}
private static class Node<E> {
E data;
Set<Node<E>> children;
Node<E> parent;
Node(E data) {
this.data = data;
children = new HashSet<>();
}
}
private static class TestData {
int id;
int parentId;
TestData(int id, Random r) {
this.id = id;
parentId = id == 0 ? -1 : r.nextInt(id);
}
}
}
···
抛砖引玉，十万条数据在我这里只要 0.1 秒。我觉得构造树的时间可以忽略不记。