Efficient algorithm for merging objects in ArrayList

Question

I have an ArrayList of custom objects (DTO) , the structure of DTO:

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

I have two task:

• Remove duplicates in Array (it seems OK, I should use HashSet)
• Find objects in ArrayList with the same id field and merge them into one object (I should merge fields categories and triggers) and create final List with merged objects.

What is the most efficient approach for such task? Also I'm interesting to use Lambda expression in my algorithm.

Answer 1

It's quite easy to merge objects by specified key using the stream API. First, define a merge method in your Entity class like this:

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

Then you can build a custom grouping collector:

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();
}

Here we group Entity elements by the result of getId method and downstream collector just calls Entity.merge() when the same id is encountered (we need to unfold on Optional additionally). No special hashCode() or equals() implementation is necessary for Entity in this solution.

Note that this solution modifies the existing unmerged Entity objects. If it's undesirable, create a new Entity in the merge() method and return it instead (as in @Marco13 answer).

Answer 2

Create Map<Integer, DTO> and put your id as key and object as DTO. And before putting into map just check if it already contain that key and if it does contain that key then take out the DTO object for that key and merge categories and triggers with the old object.