Java HashSet Iteration: Order, Removal, and Performance

When you iterate over a Java HashSet, the order in which elements are visited is not guaranteed. The iteration order depends on the hash codes of the elements and the internal bucket array size, which can change when the set is resized. This article explains how HashSet iteration behaves, how to remove elements safely during traversal, and what performance tradeoffs to expect compared with other Set implementations.

What Order Does HashSet Iteration Follow?

A HashSet stores elements in buckets based on their hashCode() values. The iteration order is determined by the bucket index and the linked list or tree structure inside each bucket. Because the bucket count can grow when the set exceeds its load factor, the iteration order can change after additions that trigger a resize. There is no guarantee that elements will appear in insertion order, sorted order, or any stable order across JVM runs.

Consider this example:

Set<String> fruits = new HashSet<>();
fruits.add("apple");
fruits.add("banana");
fruits.add("cherry");
System.out.println(fruits);

The output might be [banana, cherry, apple] or another order. The exact order depends on the string hash codes and the current capacity of the internal array. If you add more elements and trigger a resize, the order can change even for the same set.

This behavior is intentional. HashSet is designed for average constant-time add, remove, and contains operations, not for predictable traversal. If your code relies on iteration order, you need a different collection.

Iterating with For-Each and Iterator

The simplest way to iterate over a HashSet is the enhanced for-each loop, which compiles to an iterator under the hood:

Set<String> names = new HashSet<>();
names.add("Alice");
names.add("Bob");
names.add("Carol");

for (String name : names) {
    System.out.println(name);
}

If you need to access the iterator explicitly, for example to remove elements, use the Iterator interface:

Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    String name = iterator.next();
    System.out.println(name);
}

Both approaches traverse the same internal structure. The for-each loop is more readable for simple reads, while the explicit iterator gives you control over removal and lets you check hasNext() before each call.

Removing Elements During Iteration

Attempting to modify a HashSet while iterating with the for-each loop throws ConcurrentModificationException if the set is structurally modified after the iterator is created. For example, this code fails:

for (String name : names) {
    if (name.startsWith("A")) {
        names.remove(name); // throws ConcurrentModificationException
    }
}

The iterator maintains a modCount value to detect concurrent changes. Calling remove() on the collection directly increments that count, and the iterator checks it on the next next() call.

To remove elements safely, use the iterator's own remove() method:

Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    String name = iterator.next();
    if (name.startsWith("A")) {
        iterator.remove();
    }
}

The Iterator.remove() method removes the current element and updates the iterator's internal state so no exception is thrown. Using this method is the safe way to remove the current element while continuing a manual traversal.

If you are using Java 8 or later, you can also use removeIf on the collection directly, which handles the iteration internally:

names.removeIf(name -> name.startsWith("A"));

This is often clearer and avoids manual iterator management.

Performance Characteristics of HashSet Iteration

Iterating over a HashSet takes O(n) time, where n is the number of elements. The iterator visits each bucket and then each element inside the bucket. The constant factor depends on the number of empty buckets and the distribution of hash codes.

A sparse set with many empty buckets still requires the iterator to skip those buckets, so the iteration cost can be higher than the number of elements suggests. If you frequently iterate over a large set and need predictable performance, consider whether a LinkedHashSet or a sorted structure might be more appropriate.

Memory locality also matters. The backing array of a HashSet holds bucket references, and entries are distributed across that array and any linked lists or trees. Iterating over an ArrayList, by contrast, reads a contiguous array of references, which can offer better cache behavior. For performance-critical loops, copying the set to a list and iterating over that list may be faster, but the copy itself has an O(n) cost.

There are no guaranteed performance numbers across JVMs or hardware, so profile your specific workload if iteration speed is a bottleneck.

Iterating in a Deterministic Order

When you need a predictable iteration order, HashSet is the wrong choice. Two standard alternatives are LinkedHashSet and TreeSet.

LinkedHashSet maintains a doubly linked list of entries in insertion order. Iteration follows that list, so elements appear in the order they were added. The cost is slightly higher memory usage and a small overhead on insertion.

TreeSet stores elements in a red-black tree and iterates in natural sorted order or according to a custom Comparator. Operations are O(log n), so it is slower than HashSet for add, remove, and contains, but iteration order is deterministic.

The table below summarizes the key differences:

If you only need a one-off sorted iteration, you can convert the HashSet to a list and sort it:

List<String> sorted = new ArrayList<>(names);
Collections.sort(sorted);

This is O(n log n) and may be simpler than switching the collection type when the set is used mainly for membership checks.

Common Pitfalls and Edge Cases

HashSet allows at most one null element. If you add null, it is stored in a dedicated bucket. Iteration will include null, so your loop should handle it if you expect it.

Another subtle issue arises when you store mutable objects in a HashSet. If an object's hashCode() changes after it is inserted, the set will not be able to locate it later. Iteration may still show the element, but contains and remove can fail to find it. This is a general problem with hash-based collections, not specific to iteration.

When you iterate over a HashSet that is being modified by another thread, the iterator is fail-fast and will throw ConcurrentModificationException as soon as it detects concurrent modification. This detection is a best-effort safeguard, not a guarantee. For concurrent access, use ConcurrentHashMap.newKeySet() or Collections.synchronizedSet(), but be aware that synchronized iteration still requires external locking to avoid exceptions.

Finally, be cautious with the hashCode and equals contract. If two objects are equal but have different hash codes, they will be stored in different buckets, and iteration may return both even though the set logically contains only one. This violates the Set contract and can lead to confusing behavior during iteration.

Understanding these edge cases helps you use HashSet iteration correctly in production code, especially when you combine it with removal or rely on the set's contents for downstream processing.