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;
    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);
  • 2
    \$\begingroup\$ one big issue for this is that your generic type bound is Object instead of Collection<?> or even List<?> ... why is that the case?? \$\endgroup\$ – Vogel612 Sep 22 '17 at 23:15
  • \$\begingroup\$ @Vogel612 I am not sure. This is existing code and I was trying to find a way to reduce this :o \$\endgroup\$ – user1692342 Sep 23 '17 at 0:07

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){
        Collection<?> c1 = (Collection<?>)o1,
                      c2 = (Collection<?>)o2;
        return (c1.size()==c2.size())&&c1.containsAll(c2);
    catch(Exception e){
        return false;
| improve this answer | |
  • \$\begingroup\$ Slona containsAll is a O(n2) operation. \$\endgroup\$ – user1692342 Sep 23 '17 at 0:09
  • \$\begingroup\$ In the question, the code firstSet.equals(secondSet) internally calls code very similar to the code in this answer. \$\endgroup\$ – Jenna Sloan Sep 23 '17 at 0:13
  • \$\begingroup\$ stackoverflow.com/questions/5552219/… \$\endgroup\$ – user1692342 Sep 23 '17 at 0:18
  • \$\begingroup\$ 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 \$\endgroup\$ – Gaurav khurana Oct 13 at 10:05

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).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.