Divide a Set into Subsets of objects having equal field?

Question

I am currently trying to implement a data structure in java, and would like to divide a set of input objects, into different subsets of objects having an equal field.

An example use case:

We want to divide a list of persons to sub list of persons being born a certain date.

Input: person1 born 1990, person2 born 2000, person3 born 1990.

Output:

1 -> person1, person3

2 -> person2

public Map<Integer, List<Foo>> getIntToFooMap(List<Foo> foos) { 
    Map<Integer, List<Foo>> map = new TreeMap<>(); // need keys to be automatically ordered.
    List<Foo> foosWithSameSetId = new ArrayList<>();
    if (!foos.isEmpty) { 
       for (Foo foo: foos) {
           for (Foo foo2: foos) {
               if (foo.getSetId().equals(foo2.getSetId())) {
                   foosWithSameSetId.add(foo2);
               }
           }
        map.put(foo.getSetId(), foosWithSameSetId);
        foosWithSameSetId.clear();
       }
    }
  return map;
 }

The code above is not optimal, the time complexity is quadratic, and also not thread safe. Can someone tell me of a better way to divide a List or a Set into subsets of objects having an equal field, in this case the setId.

Answer 1

First, there's no need for the nested loop. You'd just get or create the set of the current foo's setId, and add foo to it:

for (Foo foo : foos) {
    map.computeIfAbsent(foo.getSetId(), i -> new ArrayList<>()).add(foo);
}

Which would be equivalent to:

for (Foo foo : foos) {
    List<Foo> list = map.get(foo.getSetId());
    if(null == list) list = new ArrayList<>();
    list.add(foo);
}

Now, you need to keep in mind the time complexity for your map implementation.

As an alternative, a groupingBy stream collector would add brevity to your code:

return foos.stream().collect(
        Collectors.groupingBy(Foo::getSetId, TreeMap::new, Collectors.toList()));