What amount of memory is allocated inside HashSet for storing two elements, one with hashCode 0 and the other with 1000000?

In Java, HashSet is implemented based on HashMap, where elements are stored as keys. Inside HashMap, a bucket array (table) is used, whose size is always a power of two, defaulting to 16.

When adding the first element, HashSet allocates an array of 16 buckets. Each bucket is either null or a linked list (or a tree if there are many elements).

For two elements with hashCode 0 and 1000000:

• The bucket index is calculated as hash & (table.length - 1).
• For hashCode 0, the index will be 0.
• For hashCode 1000000 (in binary), the index will be 1000000 & 15.

1000000 in binary ends with 0, so the index will be 0.

Thus, both elements will fall into the same bucket (index 0), and inside this bucket, there will be a linked list of two elements.

Memory usage:

• Bucket array: 16 references (each 4 or 8 bytes depending on JVM).
• Two Node objects (internal elements of HashMap), each containing a key, a value (dummy value for HashSet), a reference to the next element, and hash.

In total, an array of 16 elements and two node objects linked in a chain in one bucket are allocated.

Example:

HashSet<Integer> set = new HashSet<>();
set.add(0);       // hashCode = 0
set.add(1000000); // hashCode = 1000000

Both elements will be in the bucket with index 0, which can lead to performance degradation during search.