HashSet is a commonly used implementation of Java's Set interface. It stores unique elements and does not guarantee the order in which those elements are iterated.

For example, an inventory application may receive the same product code more than once while processing a delivery. If the application needs a collection of distinct product codes, a HashSet is a natural choice: the first occurrence is stored, while later equal occurrences are rejected.

The three operations used most often are:

• add(element) — attempts to add an element.
• remove(element) — attempts to remove an element.
• contains(element) — checks whether an element is present.

These operations generally have constant-time average performance, O(1), assuming hash codes distribute elements reasonably well. Their worst-case performance can be O(n), depending on collisions and implementation details.

A HashSet is especially useful when uniqueness and fast membership checks matter more than maintaining a particular order.

2. Main Characteristics of HashSet

Remember that “unique” does not necessarily mean that two objects have different memory identities. It means that the set treats them as duplicates according to its equality and hashing behavior.

3. What Happens Inside a HashSet?

A HashSet is implemented using a HashMap. Rather than maintaining an entirely separate hashing structure, it stores each set element as a key in the internal map. The map's values are the same placeholder object, commonly referred to in the implementation as PRESENT.

Conceptually:

• set.add(element) stores the element as a map key paired with the placeholder.
• set.contains(element) checks whether the internal map contains that key.
• set.remove(element) removes the corresponding map key.

The placeholder does not represent a different value for every set element. Its purpose is simply to let the map store keys while the public Set API exposes only the keys.

This internal design explains several visible properties of HashSet: its behavior depends on hashing, its order is not guaranteed, and its equality rules follow the same requirements that apply to keys in a HashMap.

The diagram is a conceptual model of the implementation. Internal implementation details can vary across Java versions, but the public behavior described by the Set contract remains the key point for application code.

4. Adding Elements and Detecting Duplicates

The add() method returns a boolean:

• true means the element was added as a new set member.
• false means an equal element was already present, so the set did not gain a new member.

A duplicate does not normally cause an exception. This return value can be useful when an application needs to know whether an incoming identifier was new.

For instance, if a warehouse receives product codes P-1001, P-1002, and P-1001 again, the set contains only two distinct codes. The repeated code does not increase the set's size.

The important detail is that duplicate detection is not simply a comparison of the text printed by objects. For objects of a custom class, the class's equals() and hashCode() implementations determine whether two instances represent the same logical value.

5. No Duplicates Does Not Mean Ordered

The two defining ideas behind HashSet are uniqueness and the absence of a guaranteed iteration order. These are separate properties.

5.1 Uniqueness

When an element is added, the hash-based lookup process identifies a location using its hash code and checks candidates in the relevant bucket. Equality comparisons help determine whether an equivalent element already exists. If an equal member is found, the new element is not added.

A correctly implemented equals()/hashCode() pair is therefore essential for custom objects. If the methods violate their contract, the collection may appear to accept duplicates or fail to find an object that logically should be present.

5.2 No guaranteed order

A HashSet does not promise:

• insertion order;
• alphabetical or natural order;
• a stable order across resizing;
• the same iteration order across Java implementations or versions.

An observed order may look repeatable in one run or environment, but code must not rely on it. Adding elements or changing the table's capacity can change the order.

Choose the collection that matches the ordering requirement:

5.3 Deduplicating existing data

A HashSet can also be constructed from a collection such as a list. As the source elements are added, duplicates are ignored according to the set's equality rules. This is a convenient way to obtain the distinct values from a collection.

The original list is not automatically rewritten; creating a new set produces a separate collection. Also, the set's resulting iteration order is not guaranteed to match the list's original order.

6. The equals() and hashCode() Contract

The correctness of a HashSet depends heavily on two methods inherited from Object:

• equals(Object) defines logical equality.
• hashCode() supplies an integer used by hash-based collections to find a likely storage location.

These methods have a contract that custom classes must respect.

6.1 The two central rules

Rule 1: Equal objects must have equal hash codes.

If a.equals(b) returns true, then a.hashCode() and b.hashCode() must return the same integer.

Rule 2: Hash codes must remain consistent while equality-relevant state remains unchanged.

Repeated calls to hashCode() on the same object should return the same value as long as the information used by the equality and hashing logic has not changed.

The reverse of Rule 1 is not required. Two objects can have the same hash code and still be unequal. This is called a hash collision, and a hash-based collection is designed to handle collisions.

6.2 Why equals() alone is not enough

Suppose a Product class defines two products as equal when their product codes match, but overrides equals() without overriding hashCode().

Two different Product instances may then compare equal while returning different inherited hash codes. A HashSet can send them to different locations and may not compare them with each other during lookup. The set can consequently appear to contain two copies of the same logical product.

The same problem can affect contains(): a newly constructed object that is equal to a stored object may not be found if the hashing contract is broken.

6.3 Implement both methods using the same equality fields

If product code defines product identity, both methods should use that field. For example, Objects.hash(code) can calculate a hash based on code; multiple equality fields can be supplied to Objects.hash(...).

The guiding principle is not that the two methods must contain identical code. It is that the fields defining equality must be reflected consistently in the hash code. If equals() uses code and name, hashCode() should use those same equality-relevant fields.

The default implementations of Object.equals() and Object.hashCode() are compatible with one another because the default equality is based on object identity. That default is often unsuitable for value-like objects, such as products, where separate instances with the same identifier should be considered equal.

7. Hash Collisions and Performance

A hash code helps the collection narrow down where to search, but it is not a unique identifier. Different elements may have the same hash code. When this happens, the collection must distinguish them using equality checks.

The usual performance summary is:

The O(1) figures describe expected average behavior, not a guarantee for every input. Poorly distributed hash codes can create more collisions and slow down operations. Good hashCode() implementations help distribute values, while a correct equals() implementation preserves correctness even when collisions occur.

Avoid treating a hash code as a unique ID or comparing objects only by their hash codes. Hash codes support efficient lookup; equality determines whether two objects are logically equal.

8. The Mutable Element Trap

One of the most subtle HashSet bugs occurs when an element is added and then changed in a way that affects its hashCode() or equals() result.

Imagine that a Cart object is inserted into a set when its ID is C-10. The collection places it according to the hash code calculated from that ID. If the ID is later changed to C-20, the object's hash code may change, but the set does not automatically remove the object from its old location and insert it into a new one.

As a result:

• contains(cart) may return false;
• remove(cart) may fail;
• the set's size() may still include the element.

The object has not necessarily disappeared from the internal data structure. Rather, the normal lookup path may no longer lead to its stored location.

8.1 How to prevent this bug

Treat fields that determine equality and hashing as effectively immutable while an object is stored in a hash-based set.

Useful practices include:

• Make equality-relevant fields final where the class design permits it.
• Avoid changing those fields after insertion.
• Mutable fields are generally acceptable if they do not participate in equals() or hashCode().
• If the object's logical identity must change, remove it from the set before changing the field, then add it again afterward.

The remove–change–add sequence gives the collection an opportunity to store the object using its new hash. It assumes the object can still be removed successfully before the change; do not mutate the relevant field first and expect ordinary lookup to repair the problem.

9. Capacity and Load Factor

HashSet constructors can accept an initial capacity and a load factor. These settings influence the size of the internal hash table and when it grows.

9.1 Initial capacity

The initial capacity is the requested starting capacity for the underlying hash table. The default capacity commonly documented for HashSet/HashMap is 16, though modern implementations may allocate the table lazily rather than creating the bucket array immediately in the constructor.

A larger initial capacity can reduce the number of resizing operations when the expected collection size is known. However, an unnecessarily large table can waste memory and add overhead to iteration.

9.2 Load factor

The load factor controls how full the table is allowed to become before growth is triggered. The commonly used default is 0.75.

A simplified threshold calculation is:

For a table capacity of 16 and a load factor of 0.75, the threshold is approximately 12 entries. When the threshold is exceeded, the table grows and entries are redistributed into the expanded table. Exact behavior depends on the Java implementation and its resizing rules.

9.3 Effects of changing the settings

These are trade-offs, not universal guarantees. The right choice depends on the expected data volume, memory constraints, and workload.

9.4 Presizing for an expected number of elements

When an application knows approximately how many distinct elements will be inserted, choosing a suitable initial capacity can avoid repeated resizing. A commonly used estimate is:

For an expected 1,000 elements, this estimate is about 1,334. This is a sizing guideline, not a promise that every Java version will use precisely that many buckets immediately. The implementation may round capacities to supported table sizes.

Resizing can require redistributing existing entries, so avoiding unnecessary growth can help when large sets are populated in bulk. For small collections, the defaults are usually adequate; tune capacity and load factor when measurement or a known workload justifies it.

10. Important HashSet Methods

These methods are part of the collection API, so their behavior should be understood in terms of the Set contract. The lack of ordering remains true even when the elements are read through an iterator.

11. Choosing Between HashSet, LinkedHashSet, and TreeSet

All three collections implement the Set interface, but they differ in how they organize elements.

Choose HashSet when order is irrelevant. Use LinkedHashSet when callers should see elements in insertion order. Use TreeSet when sorted traversal is required and the elements can be ordered by natural ordering or a supplied comparator.

12. Common Mistakes to Avoid

1. Relying on iteration order. An order that appears stable in a test is not guaranteed by HashSet.
2. Overriding equals() but not hashCode(). Equal objects must return equal hash codes.
3. Changing equality-relevant fields after insertion. The object can become difficult to locate or remove.
4. Assuming equal hash codes mean equal objects. Collisions are allowed; equals() distinguishes objects.
5. Assuming O(1) is guaranteed in every case. It is the average expected performance, not an unconditional worst-case guarantee.
6. Using HashSet when order matters. Select LinkedHashSet or TreeSet if the application needs a defined order.
7. Tuning capacity without a reason. Defaults are appropriate for many workloads; tune when expected size or measurements support it.
8. Assuming HashSet is thread-safe. Use an appropriate concurrency strategy when multiple threads access and modify the collection.

13. Best Practices

• Use HashSet for uniqueness and fast average membership checks.
• Define equals() and hashCode() together for value-like custom classes.
• Base both methods on consistent equality-relevant fields.
• Keep those fields unchanged while the object is a set member.
• Use add()'s boolean result when the caller needs to know whether an element was new.
• Do not expose or depend on the set's iteration order.
• Presize only when the expected number of elements makes it worthwhile.
• Use the collection whose ordering and concurrency properties fit the application's requirements.
• Remember that a hash code is a lookup aid, not a unique identifier.

14. A Practical Mental Model

The most useful mental model is: a HashSet behaves like a hash map whose keys are the set elements and whose values are ignored placeholders.

From this model, the main rules follow naturally:

• Hashing helps find the likely location of an element.
• Equality determines whether a matching element already exists.
• Correct equals() and hashCode() implementations are necessary for reliable membership.
• Mutating the fields that determine hashing after insertion can disrupt lookup.
• The collection does not promise insertion or sorted order.
• Average performance is fast when hash codes distribute elements well.

15. Quick Revision

• HashSet implements the Set interface and stores unique elements.
• It does not guarantee iteration order.
• Typical average performance for add(), remove(), and contains() is O(1); worst-case behavior can be O(n).
• In common implementations, elements are keys in an internal HashMap paired with a shared placeholder value.
• If a.equals(b) is true, both objects must return the same hash code.
• Equal hash codes do not prove that objects are equal.
• Avoid changing equality-relevant fields while an object is in the set.
• The default load factor is commonly 0.75, and the default initial capacity is commonly 16.
• Use LinkedHashSet for insertion order and TreeSet for sorted order.

16. Conclusion

HashSet is a practical choice when an application needs distinct elements and fast average membership operations. Its simplicity hides a few important requirements: custom objects must follow the equals()/hashCode() contract, fields used for equality should remain stable while stored, and iteration order must never be assumed.

Understanding its internal relationship with HashMap, collision handling, and capacity settings makes it easier to use HashSet correctly and to recognize the subtle bugs that can arise when equality or mutability is handled carelessly.