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 ?
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.
Why you don't simply use a java.util.Set and don't forget to override the equals and hashCode methods for foo class.
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;
}
