logo标签列表

寻找层次结构

javajava-8
6

让我们考虑一个Java类

class Entity  {

Integer id;
Integer parentId;

public Integer getId() {
    return id;
}

public void setId(Integer id) {
    this.id = id;
}

public Integer getParentId() {
    return parentId;
}

public void setParentId(Integer parentId) {
    this.parentId = parentId;
}


}
 }

考虑 parentId 就像外键（关联到另一个对象的 id）。

现在我创建了 6 个对象并设置了一些值。

Entity e1 = new Entity();
    e1.setId(400);

    Entity e2 = new Entity();
    e2.setId(300);
            e2.setParentId(400);

    Entity e3 = new Entity();
    e3.setId(200);
    e3.setParentId(300);

    Entity e4 = new Entity();
    e4.setId(100);
            e4.setParentId(200);

    Entity e5 = new Entity();
    e5.setId(50);
            e5.setParentId(100);

    Entity e6 = new Entity();
    e6.setParentId(50);

现在我想获取对象的层次结构。这意味着，如果我提供一个ID，我应该获得完整的父层次和子层次。

例如：如果我给出100作为ID（实体：e4），我应该获得以下父级层次结构：e4，e3，e2，e1 子层次结构：e4，e5，e6

说明：对于父层次结构：我们应该先添加初始的e4对象。然后，我们将找到ID与e4的parentID相同的对象。（这里是e3）该过程继续，直到parentid为null。 对于子层次结构：我们应该先添加初始的e4对象。然后，我们将找到parentID与e4的ID相同的对象。（这里是e5）该过程继续，直到parentid为null。

我的解决方案： 对于父级层次结构：

 List<Entity> parent = new ArrayList<Entity>();

    Entity ent = list.stream().filter(e -> e.getId() == 100).findFirst()
            .get(); // // 100 input id value

    parent.add(ent);

    Integer parentId = ent.getParentId();

    while (parentId != null) {

        int search = parentId;
        Entity newEntity = list.stream().filter(e -> e.getId() == search)
                .findFirst().get();

        parent.add(newEntity);
        parentId = newEntity.getParentId();
    }

对于子层级：

    Entity entnew = list.stream().filter(e -> e.getId() == 100).findFirst()
            .get(); // 100 input id value



    child.add(entnew);


    Integer idNew = entnew.getId();


    while (idNew != null) {

    int searchNew = idNew;

    Entity newEnt = list.stream().filter(f -> f.getParentId()!= null && f.getParentId() == searchNew)
            .findFirst().get();

    child.add(newEnt);
    idNew = newEnt.getId();

    }

我找到了解决这个场景的方法，但我希望使用Java 8的核心概念来实现更高效的解决方案。

你为什么要保留 parentId 而不是使用对父级的引用？ - user902383
3个回答
1
我找到了一个更符合Java8风格的解决方案，带有函数式编程的味道。
鉴于您的六个实体（请注意，我已经为e6设置了Id，否则我们会得到NullPointerException）：
Entity e1 = new Entity();
e1.setId(400);

Entity e2 = new Entity();
e2.setId(300);
e2.setParentId(400);

Entity e3 = new Entity();
e3.setId(200);
e3.setParentId(300);

Entity e4 = new Entity();
e4.setId(100);
e4.setParentId(200);

Entity e5 = new Entity();
e5.setId(50);
e5.setParentId(100);

Entity e6 = new Entity();
e6.setId(25); // this Id must be set, or we'll get a NPE
e6.setParentId(50);

并且包含它们的列表：

List<Entity> list = new ArrayList<>();
list.add(e1);
list.add(e2);
list.add(e3);
list.add(e4);
list.add(e5);
list.add(e6);

然后，对于父母层次结构：
Function<Integer, Entity> byId = 
    id -> list.stream()
        .filter(e -> e.getId().equals(id))
        .findFirst()
        .orElse(null);

Entity parentsSeed = byId.apply(100); // e4

UnaryOperator<Entity> nextParent = 
    e -> e == null ? e : byId.apply(e.getParentId());

List<Entity> parents = 
    Stream.iterate(parentsSeed, nextParent)
        .limit(list.size())
        .filter(Objects::nonNull)
        .collect(Collectors.toList()); // [e4, e3, e2, e1]

而对于儿童的层次结构：

Entity childrenSeed = byId.apply(100); // e4

Function<Integer, Entity> byParentId = 
    id -> list.stream()
        .filter(e -> id.equals(e.getParentId()))
        .findFirst()
        .orElse(null);

UnaryOperator<Entity> nextChild = 
    e -> e == null ? e : byParentId.apply(e.getId());

List<Entity> children = 
    Stream.iterate(childrenSeed, nextChild)
        .limit(list.size())
        .filter(Objects::nonNull)
        .collect(Collectors.toList()); // [e4, e5, e6]

使用Stream.iterate()方法的想法是通过创建一个“功能性”迭代来创建流。
对于父母，我创建了一个UnaryOperator（函数），它给定一个Entity，返回其父Entity或null；对于子项，我创建了一个UnaryOperator，它给定一个Entity，返回其子Entity或null。
为了执行这两个搜索，我使用了另一个Function，它仅通过id和parentId分别搜索list。
0

我会为对象、父级和子级创建查找表：

List<Integer> ancestors = new ArrayList<>();
List<Integer> descendants = new ArrayList<>();
Map<Integer, Entity> objectById = list.stream().collect(Collectors.toMap(e ->e.getId(), e->e));
Map<Integer, Integer> parentIdByChildId = list.stream().collect(Collectors.toMap(e->e.getId(), e ->e.getParentId());
Map<Integer, Integer> childIdByParentId = list.stream().collect(Collectors.toMap(e ->e.getParentId(), e->e.getId());
Integer parentId = 10;
Integer current = parentId;
while(current!=null) {
    current = childIdByParentId.get(current);
    if(current!=null){
        descendants.add(objectById.get(current));
    }
}
current = parentId;
while(current!=null) {
    current = parentIdByChildId.get(current);
    if(current!=null){
        ancestors.add(objectById.get(current));
    }
}

这不支持具有多个子元素的实体，您可能需要检查java.util.stream.Collectors.groupBy的示例。

-1

你必须使用整数ID来链接到父级吗？根据你想要实现的目标，但是你不能只是像这样链接吗：

class Entity  {
    Integer id;
    Entity  parent;
}

一旦您获得了第一个实体，您就不必搜索整个列表。

我认为你应该提供一个解决方案来回答这个问题，而不是编辑问题。 - Manu Joy
在解决某些问题时，使用适当的数据结构至少与算法本身同样重要。如果您使用的数据结构不适合该问题，则算法可能会变得缓慢和复杂。因此，我想知道为什么必须使用这种数据结构。 - user140547
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接