Java ArrayList remove duplicates on a custom condition

Question

I have an array list of items of class

Class foo {
    String name;
    String time;
}

I want to get a list of foo objects with unique names. If two objects in the list have same name I want to retain only the one with least time (lexicographic is fine). This list is being returned by an underlying library so I can not do anything at insert time. I know this is easy with a map in O(n) time and space (worst case). Is there a more efficient solution ?

score 2 · Answer 1 · edited May 23 '17 at 12:01

What is the problem with :

// myList is the List returned by the library
List<foo> new List = new ArrayList<foo>(new LinkedHashSet<foo>(myList));

Override the equals() and hashCode()in foo .

This list is being returned by an underlying library so I can not do anything at insert time. I know this is easy with a map in O(n) time and space (worst case). Is there a more efficient solution ?

I believe no , that is the most optimized solution . Look at this SO answer.

score 1 · Answer 2 · answered Jul 16 '13 at 07:23

1

Why you don't simply use a java.util.Set and don't forget to override the equals and hashCode methods for foo class.

answered Jul 16 '13 at 07:23

M. Abbas

6,409
4
33
46

1

As I mentioned the class foo is defined in an underlying library so I can not modify it. Is there a way I can use a custom comparator for the set ? – Pradhan Jul 16 '13 at 08:01

score 0 · Answer 3 · answered Nov 28 '13 at 09:55

Even if there was a way to modify the class to get a proper hash code, the question would be, which hash code should it be. Normally, hash codes and equality are using all properties of an object, so such a standard implementation would not help here as you want to have unique objects regarding a single property of the instances.

There is no standard hash map allowing you to provide a custom hash and equality function but you can do this for sorted maps. This will not give you O(1) like hashing, but it can give you O(log(n)) for a lookup which is still better than O(n).

Here is how it works like:

List<foo> list = // however you get it
Set<foo> set=new TreeSet<>(FooComparator.INSTANCE);
// now the set has no duplicates regarding foo.name

…

final class FooComparator implements Comparator<foo>
{
  static final FooComparator INSTANCE = new FooComparator();
  public int compare(foo o1, foo o2)
  {
    return o1.name.compareTo(o2.name);
  }
}
class foo {
  String name;
  String time;
}

Java ArrayList remove duplicates on a custom condition

3 Answers3