HashSet is the common implementation of the Set interface. It stores unique elements with no guaranteed order and offers constant-time average performance for the three operations that come up most often: add, remove, and contains. This lesson covers what's inside a HashSet, why equals and hashCode matter so much, the issues around mutable elements, and the capacity and load factor numbers.

A HashSet doesn't store elements in a custom data structure. It wraps a HashMap and uses the elements as the map's keys. The values are all the same dummy object that the implementation keeps as a private constant. A call to set.add(productCode) runs map.put(productCode, PRESENT) internally. A call to set.contains(productCode) runs map.containsKey(productCode). The set is a thin facade.

Most properties of HashSet follow from this fact. No order? HashMap has no defined order. O(1) average lookup? That's the average cost of HashMap.containsKey. The role of equals and hashCode? Same as for any HashMap key. With "a HashMap with the values thrown away" as the model, most of HashSet's behavior follows directly.

The diagram is small on purpose. HashSet is a wrapper that stores each element as a key in a private HashMap and pairs it with a single shared placeholder value called PRESENT. The placeholder is the same object for every entry, so the set never wastes space tracking distinct values.

The most basic usage: a warehouse wants to track the unique product codes it currently has in stock. The same physical item code might be scanned twice during a delivery; the set absorbs the duplicate.

The duplicate "P-1001" is dropped. add returns false in that case (not an exception, just false), which is the way to check whether the element was actually new. contains and size run in their usual constant-time average mode, so even with millions of product codes, the lookup stays fast.

add, remove, and contains are O(1) on average but O(n) in the worst case if many elements collide into the same bucket. Good hashCode implementations keep collisions rare.

The two headline properties of HashSet are easy to state and easy to misuse. There are no duplicates, and there is no order. Both rules deserve a closer look because the second one is unfamiliar to anyone who hasn't worked with hash-based collections before.

"No duplicates" is enforced by equals. A call to add(x) makes the set compute x.hashCode(), find the bucket that hash code points to, and walk the elements in that bucket comparing each one to x using equals. If any of them returns true, the new element is rejected. If none do, it goes in.

"No order" means the iteration order has nothing to do with insertion order, natural ordering, or anything predictable from outside the JVM. It depends on the hash codes of the elements and the current size of the internal table. Adding the same elements to two different HashSet instances usually produces the same order, but that's a side effect of the implementation, not a guarantee. The order can also change as the set grows and the internal table is resized.

A small program demonstrates the point. A newsletter operator collects subscriber emails into a HashSet. The print order has no relationship to the order the emails came in.

Running this on different machines may produce a different order, and that's the point. Treat any specific order observed as a coincidence. For insertion order, use LinkedHashSet.

A common deduplication pattern: given a list of visitor IDs (possibly with repeats), produce the unique ones. Passing the list into a HashSet constructor drops duplicates in one line.

Six visit records, four distinct visitors. The set constructor calls add on each element internally, and add skips the duplicates. The List.of(...) produces an immutable list, which is fine because the set only reads from it.

Everything HashSet does depends on two methods from java.lang.Object: hashCode() and equals(Object). Objects from a class that doesn't override these correctly will cause the set to misbehave in ways that look like bugs but are actually contract violations.

The contract has two rules that matter here:

Rule 1 is broken most often. When two objects are equal according to equals, they must produce the same hash code. The reverse doesn't have to hold: two unequal objects can share a hash code (that's a collision and it's fine), but two equal objects with different hash codes will break the set.

The diagram captures the asymmetry. Equal objects must agree on hash code (the green arrow is the contract). Matching hash codes do not imply equality (the teal arrow allows either outcome).

To see why this matters, consider a Product class that overrides equals correctly but forgets to override hashCode. The result is that two Product instances representing the same product look unequal to the set, even though they look equal in source.

The set holds two entries for the same product, and asking whether it contains that product returns false. The reason is that Object.hashCode (which BrokenProduct inherits without overriding) returns a different value for each instance, based on the object's memory identity. The set sends the two equal products to different buckets, never compares them with equals, and never sees them as duplicates. The contains call uses a fresh instance with a third, unrelated hash code, lands in yet another bucket, and finds nothing.

Fixing it is mechanical. Override hashCode to use the same field(s) as equals. Both methods must agree on which fields define equality.

Two distinct products, and a fresh Product("P-1001", "Notebook") is correctly recognised as already present. Objects.hash(code) is a one-line way to derive a hash from one or more fields; for multiple fields, write Objects.hash(code, name). The only rule is that every field used in equals should also feed into hashCode, and nothing else.

One more detail: Object's default equals compares identity (a == b), and its default hashCode is derived from identity as well. They're consistent with each other by default. The trap is that "consistent" doesn't mean "useful". For a class meant to represent values rather than identities (two products with the same code are the same product), both must be overridden in lockstep.

A nasty bug happens when an object is put into a HashSet and then one of the fields that contribute to its hash code is mutated. The set placed the object in a bucket based on its original hash code. After the mutation, the hash code changes, but the set has no idea, so the object is still sitting in the old bucket. Now contains looks for the object in the new bucket and finds nothing. The object is in the set but unreachable.

The same problem applies in reverse for removal. The object can't be removed using a freshly built equivalent, because the lookup lands in the wrong bucket.

The fix is to treat objects placed into a HashSet as if they were immutable. Make the fields used by equals and hashCode final, or at least never change them once the object has been added to a set.

A small program creates the bug on purpose to make it concrete. The Cart class is set up so that the cart ID drives both equals and hashCode, and the program then changes the ID after the cart is in the set.

The set's size is still 1, so the cart is technically still inside. But contains(cart) returns false, because the new hash code points to a different bucket. The cart is now invisible to the set's lookup machinery. A carts.remove(cart) does nothing; the cart remains stuck in its original bucket forever.

The lesson is to keep elements stored in a HashSet immutable in the fields that matter for equality. The final keyword in the earlier Product class did exactly that. Mutable fields are fine as long as they don't participate in equals or hashCode. To change the identity of an object, the safe sequence is: remove from the set, mutate, add again.

HashSet accepts two constructor arguments that come up in interviews and in code reviews of high-throughput systems. They are initialCapacity and loadFactor.

initialCapacity is the size of the internal bucket array when the set is created. The default is 16. loadFactor is a number between 0 and 1 that controls when the set decides to grow. The default is 0.75. The product of capacity and load factor is the threshold: once the number of elements exceeds it, the internal table doubles in size and every existing element is re-bucketed. With the defaults, the first growth happens once the set has more than 16 * 0.75 = 12 elements.

When the set will hold thousands of elements, presizing avoids a series of expensive resizes as it grows. The conventional formula is to set initialCapacity to expectedSize / 0.75 + 1, rounded up. For 1,000 elements that's about 1,334.

The set holds exactly the expected count, but more importantly, the internal table never had to resize during the loop. For small sets, this kind of tuning is invisible. For sets that get loaded with millions of elements at startup, it can matter.

Resizing copies every existing element into a new larger table, which is O(n). When the size can be roughly predicted, presizing converts many small growth events into zero.

Most code uses the no-argument constructor and never thinks about these numbers. The defaults are tuned for the common case. Tune only when profiling tells you to.

A short program that uses everything from the lesson. It deduplicates incoming visitor records into a HashSet of Visitor objects, where two visitors are considered the same if they share an email address. The Visitor class implements equals and hashCode correctly, with final fields so the mutation trap is impossible.

Five raw visit records, three unique visitors keyed on email. The two "alice@shop.com" entries collapse into one (the first one wins; later equal entries are rejected by add), and the two "bob@shop.com" entries do the same. The iteration order is whatever the set's buckets produced; running the program again may print the visitors in a different order, and that's expected.

The Visitor class is built the way it should be. The field that drives equality (email) is final. The equals and hashCode methods use the same field. The class is static (so it doesn't carry a hidden reference to the outer instance), and it's final (so subclasses can't reintroduce identity-based equality). None of that is required by HashSet, but it keeps the class consistent as a value type.