Comparing unordered list in java

Question

I want to compare two unordered list and currently I am doing it in the following way. Is there a better way to do this as I am repeating my code twice (for null check & then converting to a Set). Maybe there exists a library in Guava which does this?

public class CompareUnorderedList implements BiPredicate<Object, Object> {
 private Function<Object, Object> mapping;
 public CompareUnorderedList(Function<Object, Object> mapping) {
 this.mapping = mapping;
 }
 @Override
 public boolean test(Object o1, Object o2) {
 o1 = o1 != null ? o1 : Collections.EMPTY_LIST;
 o2 = o2 != null ? o2 : Collections.EMPTY_LIST;
 Set<Object> firstSet = (List<Object>o1).stream().map(mapping).collect(Collectors.toSet());
 Set<Object> secondSet = (List<Object>o2).stream().map(mapping).collect(Collectors.toSet());
 return firstSet.equals(secondSet);
 }
}

• Vogel612: one big issue for this is that your generic type bound is Object instead of Collection<?> or even List<?> ... why is that the case??
• user1692342: @Vogel612 I am not sure. This is existing code and I was trying to find a way to reduce this :o

Answer 1

I think it would be better to not convert the List to a Set, but just check if they are the same size and if one contains all of the other (as it is done in HashSet) like so:

public static boolean test(Object o1, Object o2){
 try{
 Collection<?> c1 = (Collection<?>)o1,
 c2 = (Collection<?>)o2;
 return (c1.size()==c2.size())&&c1.containsAll(c2);
 }
 catch(Exception e){
 return false;
 }
}

• user1692342: Slona containsAll is a O(n2) operation.
• Jenna Sloan: In the question, the code firstSet.equals(secondSet) internally calls code very similar to the code in this answer.
• user1692342: stackoverflow.com/questions/5552219/…
• Gaurav khurana: What if there are duplicates , then this will not give right, Suppose 1,2,2,2,2 and other set 2,1,1,1,1 . Both conditions will satisfy but list is not equal

Answer 2

I believe your solution as well as Jenna Sloan's solution is wrong.

Your solution compares the sets of both unordered lists. Thus, it removes duplicates. This implies that the following two unordered lists are equal:

{1, 2} == {1, 1, 2} // true

In other words, set equality does not consider the cardinalities of individual elements.

According to this question, containsAll does also not consider the element cardinalities. Thus, the implementation of Jenna Sloan has the same issue.

My proposal would be the following:

1. Compare lengths of the lists and return false if they are not equal.

2. For both lists: Count the occurences of the elements in the unordered list using a HashMap<object,int>:

   • if the hashmap does not already contain the element, set the value of the element (key) to 0
   • if the hashmap contains already the element, set the value of the element to value+1.
3. For each element in the first HashMap, check if both HashMaps have the same value. If a value does not match, return false.
4. Return true.

The complexity should be O(n).