How the ArrayList objects are stored inside a HashSet in Java?

Question

Today I was doing a question and in that they have used a code similar to this. I am amazed to see this. I thought every HashSet stores the hash of an object and the answer would be 2. However, the answer to this 1. Could anyone explain what actually happens internally when I store HashSet of ArrayList of objects and why the answer is 1 instead of 2?

import java.io.*;
import java.util.*;

class Code {
    public static void main (String[] args) {
        
        HashSet<ArrayList<Integer>> set=new HashSet<>();
        ArrayList<Integer> list1=new ArrayList<>();
        ArrayList<Integer> list2=new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list2.add(1);
        list2.add(2);
        set.add(list1);
        set.add(list2);
        System.out.println(set.size()); // 1
    }
}

It's because of how `equals()` and `hashCode()` are implemented for ArrayList. The HashSet recognizes "duplicates" using those two. Also mind the [contract between the two](https://stackoverflow.com/questions/2265503/why-do-i-need-to-override-the-equals-and-hashcode-methods-in-java). — bkis, Jul 19 '20 at 12:06
Does this answer your question? [How Set checks for duplicates? Java HashSet](https://stackoverflow.com/questions/52339600/how-set-checks-for-duplicates-java-hashset) — Eklavya, Jul 19 '20 at 12:08
From doc _If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result._ so for both list same hashcode generated and when add method called it check hash of list and discard as duplicate — Eklavya, Jul 19 '20 at 12:14

score 5 · Accepted Answer · answered Jul 19 '20 at 12:06

Two instances of List are considered "equal" if they have the same elements in the same order. So that means list1 and list2 are "equal". By the general contract of the hashCode method they must also have the same hash code

HashSet does not store duplicate items: if you give it two items that are equal it stores only the first one. So here it's storing list1 only.

score 1 · Answer 2 · answered Jul 19 '20 at 12:05

The answer is 1 because both Lists contain the same elements. The hash code of an ArrayList is a function of the hash codes of all elements in the list. In your case, both lists contain the same elements which means they correspond to the same hash code.

score 1 · Answer 3 · answered Jul 19 '20 at 12:10

HashSet implements the Set interface, backed by a hash table. Any implementation of Set simply discards the duplicate elements. Since both list1 and list2 are equal, set will discard list2 when you try to insert it into into set when set already has list1. Thus, the size of set remains 1.

score 0 · Answer 4 · answered Jul 19 '20 at 12:22

0

Here both the list values are equal so there hashcode is also the same by the contract and hashset stores hash value of its object and doesn't contain duplicates so list1 is replaced with list2 and hence the size is 1.

answered Jul 19 '20 at 12:22

prachi julka

76
3

score 0 · Answer 5 · answered Jul 19 '20 at 12:31

It would follow its default behaviour - it would first check if there is any existing entry (using hashCode() and equals() ) and if found, it would replace it and if not, it would insert it.

Note that the hashCode() and equals() method invocations will eventually get invoked on the object-entry - in this case the ArrayList object itself (ArrayList inturn inherits the methods from AbstractList ).

PS : It appears HashSet is implemented internally as a HashMap !

How the ArrayList objects are stored inside a HashSet in Java?

5 Answers5