How Set<List<Integer>> is working conceptually

Question

I wrote a program as below:

public static void main(String[] args) {
        Set<List<Integer>> s = new HashSet<>();
        List<Integer> l1 = new ArrayList<>(List.of(1,2,3));
        List<Integer> l2 = new ArrayList<>(List.of(1,2,3));
        List<Integer> l3 = new ArrayList<>(List.of(3,2,1));
        s.add(l1);
        if(s.contains(l2)) {
            System.out.println("l2 is already present");
        }
        if(s.contains(l3)) {
            System.out.println("l3 is present");
        } else {
            System.out.println("l3 is absent");
        }
}

Here is the output:

l2 is already present
l3 is absent

I have a general idea of equals and hashcode in Java and rough idea of Object type, etc.

Can someone explain conceptually how this thing able to compare internally a list of integers and find if it is already present? Notice that it works only if the order of elements in the list is same.

Answer 1

HashSet relies on the equals and hashCode methods of the element type (which in your case is List). The documentation for those methods on the List type is as follows:

equals - Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if Objects.equals(e1, e2).) In other words, two lists are defined to be equal if they contain the same elements in the same order.
hashCode - Returns the hash code value for this list. The hash code of a list is defined to be the result of the following calculation:

int hashCode = 1;
for (E e : list)
    hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

This ensures that list1.equals(list2) implies that list1.hashCode()==list2.hashCode() for any two lists, list1 and list2, as required by the general contract of Object.hashCode().

I.e. in summary, the hashCode and equals implementations for Lists simply operate on each element of the list.

Answer 2

The HashSet#contains(Object o) javadoc states the following (emphasis mine):

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

So, this means when you check s.contains(l2), the Lists in s are actually checked for equality against l2 via List#equals() internally.

And the List#equals(Object o) javadoc states (emphasis mine):

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ? e2==null : e1.equals(e2)).) In other words, two lists are defined to be equal if they contain the same elements in the same order. This definition ensures that the equals method works properly across different implementations of the List interface.

Which is exactly why l2 is found to be contained in s, but l3 is not.