HashSet in Java
HashSet is implemented internally as a HashMap where the set elements are keys and a shared dummy Object (called PRESENT) is the value for every entry. Whe...
HashMap as the Backing Store
HashSet is implemented internally as a HashMap where the set elements are keys and a shared dummy Object (called PRESENT) is the value for every entry. When you call hashSet.add(e), it delegates to map.put(e, PRESENT) and returns true if no mapping existed for e before. When you call contains(e), it calls map.containsKey(e). This design lets HashSet reuse all of HashMap's hash table logic without duplicating code.
The hash table uses an array of buckets. An element's bucket index is computed from its hashCode, passed through a spreading function to distribute bits more evenly, and then masked to the current array length (always a power of two for efficient bitwise modulo). Elements whose hash codes map to the same bucket are stored in a linked list, or, since Java 8, in a balanced tree (a red-black tree) once a bucket's linked list reaches a threshold of 8 entries. The tree conversion reduces worst-case lookup in a heavily loaded bucket from O(n) to O(log n).
Load Factor and Capacity
Two parameters control HashSet's performance: initial capacity (number of buckets at creation) and load factor (how full the table can get before resizing). The default initial capacity is 16 and the default load factor is 0.75. When the number of elements exceeds capacity times load factor (16 * 0.75 = 12 elements by default), the table doubles its capacity and rehashes all elements.
Rehashing is expensive: it is O(n) because every element must be reinserted into a new bucket position. For large sets where the final size is known, specify the initial capacity to avoid rehashing: new HashSet<>(expectedSize / 0.75 + 1). A higher load factor reduces memory usage but increases collision frequency and slows operations. A lower load factor does the opposite.
Average time complexity: add, remove, contains are all O(1). Iteration over all elements is O(capacity + size), so an under-filled HashSet with a large capacity is expensive to iterate.
Null Handling and Interview Tip
HashSet permits exactly one null element because HashMap allows one null key. The null element is stored in bucket 0 (its hash is treated as 0). Attempting to add a second null simply returns false, maintaining uniqueness.
A practical example: Set<String> tags = new HashSet<>(Arrays.asList("java", "backend", "spring")); tags.add("java"); System.out.println(tags.size()); prints 3 because "java" was already present. tags.contains("spring") returns true in O(1) average time.
An interview tip: interviewers often ask what happens when you put a mutable object into a HashSet and then change the field used in hashCode. The answer is that the object ends up in the wrong bucket for its new hash, so contains returns false even though the object is visually in the set. The set is now in a corrupted state. This is why it is best practice to use only immutable objects, or objects whose hash-relevant fields never change, as set elements or map keys.