ArrayList中合并对象的高效算法

Question

我有一个自定义对象（DTO）的ArrayList，DTO的结构如下：

private String id;
private String text;
private String query;
private String locatorId;
private Collection<String> categories;
private Collection<String> triggers;

我有两个任务：

• 在数组中删除重复项（看起来可以使用 HashSet）
• 查找 ArrayList 中具有相同 id 字段的对象，并将它们合并为一个对象（应合并 categories 和 triggers 字段），然后创建包含合并对象的最终列表。

对于这样的任务，最有效的方法是什么？此外，我有兴趣在我的算法中使用 Lambda 表达式。

- Evgeniy Kruglov

---

你如何合并文本、查询和类别？ - m0skit0

这些字段不会被合并（它们将保持相同，在字段类别和触发器方面的唯一区别）。 - Evgeniy Kruglov

Answer 1

使用流API按指定键合并对象非常容易。首先，在您的Entity类中定义一个merge方法，如下所示：

public Entity merge(Entity other) {
    this.categories.addAll(other.categories);
    this.triggers.addAll(other.triggers);
    return this;
}

然后您可以构建一个自定义的分组收集器：

import static java.util.stream.Collectors.*;

public static Collection<Entity> mergeAll(Collection<Entity> input) {
    return input.stream()
                .collect(groupingBy(Entity::getId,
                    collectingAndThen(reducing(Entity::merge), Optional::get)))
                .values();
}

在这里，我们通过getId方法的结果对Entity元素进行分组，并且当遇到相同的id时，下游收集器只需调用Entity.merge()（我们还需要在Optional上展开）。在此解决方案中，不需要为Entity实现特殊的hashCode()或equals()。

请注意，此解决方案修改了现有未合并的Entity对象。如果不希望如此，请在merge()方法中创建一个新的Entity并返回它（就像@Marco13的答案中那样）。

- Tagir Valeev

---

作为“groupingBy” - “reducing”的替代方案，您可以使用toMap(Entity::getId, e->e, Entity::merge)。 - Misha

@Misha，谢谢。可能我太过于使用“groupingBy”方式思考了，总是忘记了“toMap”的替代方法。 - Tagir Valeev

请注意，除非categories和triggers是Set，否则合并方法可能会在这些Collections中生成重复的条目，这可能不是OP所指的“合并”的意思。 - Mick Mnemonic

@MickMnemonic，OP已经在问题中同意使用HashSet。 - Tagir Valeev

如果解包Optional不那么棘手，groupingBy就不会那么糟糕了。我希望我们可以通过Collector上的默认方法执行reducing(Entity::merge).andThen(Optional::get)，这样它就可以更自然地从左到右读取，而不是使用静态的collectingAndThen。 - Misha

@TagirValeev，我在问题中没有看到这个陈述，除非你的意思是“删除数组中的重复项（看起来可以，我应该使用HashSet）”（对我而言相当模糊，并且似乎与DTO的“数组”有关）？ - Mick Mnemonic

Answer 2

创建Map<Integer, DTO>，将ID作为键，对象作为DTO。在放入映射之前，请检查它是否已经包含该键，并且如果确实包含该键，则取出该键的DTO对象并与旧对象合并类别和触发器。

- Naman Gala

Answer 3

在Naman Gala的回答中提到的一种可能的解决方案是使用一个从ID到实体的Map，并在它们具有相同ID时手动合并实体。

这里通过mergeById方法实现，使用一些虚拟/示例输入，其中：

• 两个实体需要合并（因为ID相同）
• 两个实体相等（它们也将被“合并”，得到与其中一个输入相同的结果）

。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;


public class MergeById
{
    public static void main(String[] args)
    {
        List<Entity> entities = new ArrayList<Entity>();
        entities.add(new Entity("0", "A", "X", "-1", 
            Arrays.asList("C0", "C1"), Arrays.asList("T0", "T1")));
        entities.add(new Entity("0", "A", "X", "-1", 
            Arrays.asList("C2", "C3"), Arrays.asList("T2")));
        entities.add(new Entity("1", "B", "Y", "-2", 
            Arrays.asList("C0"), Arrays.asList("T0", "T1")));
        entities.add(new Entity("1", "B", "Y", "-2", 
            Arrays.asList("C0"), Arrays.asList("T0", "T1")));
        entities.add(new Entity("2", "C", "Z", "-3", 
            Arrays.asList("C0", "C1"), Arrays.asList("T1")));

        System.out.println("Before merge:");
        for (Entity entity : entities)
        {
            System.out.println(entity);
        }

        List<Entity> merged = mergeById(entities);

        System.out.println("After  merge:");
        for (Entity entity : merged)
        {
            System.out.println(entity);
        }
    }

    private static List<Entity> mergeById(Iterable<? extends Entity> entities)
    {
        Map<String, Entity> merged = new HashMap<String, Entity>();
        for (Entity entity : entities)
        {
            String id = entity.getId();
            Entity present = merged.get(id);
            if (present == null)
            {
                merged.put(id, entity);
            }
            else
            {
                merged.put(id, Entity.merge(present, entity));
            }
        }
        return new ArrayList<Entity>(merged.values());
    }

}


class Entity
{
    private String id;
    private String text;
    private String query;
    private String locatorId;
    private Collection<String> categories;
    private Collection<String> triggers;

    Entity()
    {
        categories = new LinkedHashSet<String>();
        triggers = new LinkedHashSet<String>();
    }

    Entity(String id, String text, String query, String locatorId,
        Collection<String> categories, Collection<String> triggers)
    {
        this.id = id;
        this.text = text;
        this.query = query;
        this.locatorId = locatorId;
        this.categories = categories;
        this.triggers = triggers;
    }

    String getId()
    {
        return id;
    }

    static Entity merge(Entity e0, Entity e1)
    {
        if (!Objects.equals(e0.id, e1.id))
        {
            throw new IllegalArgumentException("Different id");
        }
        if (!Objects.equals(e0.text, e1.text))
        {
            throw new IllegalArgumentException("Different text");
        }
        if (!Objects.equals(e0.query, e1.query))
        {
            throw new IllegalArgumentException("Different query");
        }
        if (!Objects.equals(e0.locatorId, e1.locatorId))
        {
            throw new IllegalArgumentException("Different id");
        }
        Entity e = new Entity(e0.id, e0.text, e0.query, e0.locatorId, 
            new LinkedHashSet<String>(), new LinkedHashSet<String>());
        e.categories.addAll(e0.categories);
        e.categories.addAll(e1.categories);
        e.triggers.addAll(e0.triggers);
        e.triggers.addAll(e1.triggers);
        return e;
    }

    @Override
    public String toString()
    {
        return "Entity [id=" + id + ", text=" + text + ", query=" + query +
            ", locatorId=" + locatorId + ", categories=" + categories +
            ", triggers=" + triggers + "]";
    }

}

输出结果为：

Before merge:
Entity [id=0, text=A, query=X, locatorId=-1, categories=[C0, C1], triggers=[T0, T1]]
Entity [id=0, text=A, query=X, locatorId=-1, categories=[C2, C3], triggers=[T2]]
Entity [id=1, text=B, query=Y, locatorId=-2, categories=[C0], triggers=[T0, T1]]
Entity [id=1, text=B, query=Y, locatorId=-2, categories=[C0], triggers=[T0, T1]]
Entity [id=2, text=C, query=Z, locatorId=-3, categories=[C0, C1], triggers=[T1]]
After  merge:
Entity [id=0, text=A, query=X, locatorId=-1, categories=[C0, C1, C2, C3], triggers=[T0, T1, T2]]
Entity [id=1, text=B, query=Y, locatorId=-2, categories=[C0], triggers=[T0, T1]]
Entity [id=2, text=C, query=Z, locatorId=-3, categories=[C0, C1], triggers=[T1]]

关于使用lambda完成此操作的请求：可能可以编写一些巧妙的entities.stream().collect(...)应用程序。但由于这不是问题的主要目标，我将把这部分答案留给其他人（但不会省略这个小提示：仅仅因为你能做到并不意味着你必须这样做。有时候，循环也是可以的）。

另外请注意，这可能很容易被概括，可能需要从数据库中借鉴一些词汇。但我认为问题的主要点应该得到回答。

- Marco13

---

谢谢@Marco13，我会采用这种方法，因为对我来说更有效率（稍后自己添加一些Lambda内容）。 - Evgeniy Kruglov

Answer 4

实现基于DTO中的"id"字段的"equals"和"hashCode"方法，并将DTO存储在一个"Set"中。这样可以解决你遇到的两个问题；根据现在定义的DTO相等性方式，"Set"中不会存在具有相同"id"的重复项。

编辑：

根据你的要求，基于新DTO的值合并现有DTO的类别和触发器，更适合存储DTO的数据结构是"Map"（因为一旦将元素放入"Set"中，从中检索元素会比较繁琐）。此外，我认为DTO中的类别和触发器应定义为"Set"，以防止重复项；这将使合并操作更加简单。

private Set<String> categories;
private Set<String> triggers;

假设DTO提供了上述字段的访问器（getCategories / getTriggers）（并且这些字段从不为null），则合并现在可以以下面的方式实现：

public static void mergeOrPut(Map<DTO,DTO> dtos, DTO dto) {
    if (dtos.containsKey(dto)) {
        DTO existing = dtos.get(dto);
        existing.getCategories().addAll(dto.getCategories());
        existing.getTriggers().addAll(dto.getTriggers());
    } else {
        dtos.put(dto, dto);
    }
}

上面的代码也可以很容易地修改为与 Map<Integer, DTO> 一起使用，这种情况下，您不需要在 DTO 类中覆盖 equals 和 hashCode 方法。

- Mick Mnemonic

---

这不会将具有相同ID的实体合并。它只会省略其中一个，其ID将重复。除此之外，我怀疑仅基于ID时，hashCode和equals的明智实现是否可能。 - Marco13

@Marco13，基于仅有ID的“equals”实现在DTO表示对应于数据库表中行的实体时非常有意义。 - Mick Mnemonic

@Evgeniy，如果您需要合并实体，则需要告诉我们应该如何进行。 - Mick Mnemonic

@MickMnemonic 可以对此进行争论，但直觉上，当具有相同“ID”的两个对象具有不同的属性时，则该“ID”不是“ID”，而只是任意值。（但我知道，在涉及数据库中的ID角色和“主键”等内容时，这种直觉可能是错误的，因为我不熟悉这些内容...） - Marco13

@Marco13，当数据传输对象具有唯一标识对象的标识符属性时，我认为定义相等的唯一合理方式是仅通过该属性。我不知道您所说的标识符“变成任意值”的含义。 - Mick Mnemonic

Answer 5

如果您坚持使用lambda表达式，可以按照以下步骤操作：

Set<X> x = new TreeSet<>((o1, o2) -> 
        ((X)o1).getId().equals(((X)o2).getId()) ? 0 : 1);

List<X> list = new ArrayList<>(set.addAll(x));

这将创建一个根据id唯一的对象集合。接下来，对于list中的每个对象，从原始列表中找到相应的对象并合并内部集合。

- Maroun