Premium

Hash Set

Basic Algorithms
≈ 2 min read

When only membership matters

HashSet stores unique values without a separate associated value. The main question it answers is: “is this element in the set?”. Insertion, membership checks, and deletion take O(1) on average.

If the same element is added several times, the set still contains only one logical entry. The add() method returns true when an element is actually added and false when it was already present.

Finding a duplicate value

static boolean hasDuplicate(int[] numbers) {
    Set<Integer> seen = new HashSet<>();

    for (int value : numbers) {
        if (!seen.add(value)) {
            return true;
        }
    }

    return false;
}

Each value is added to seen only on its first occurrence. If add() returns false, the value has already been seen, so the duplicate is detected immediately without scanning the previous elements separately.

With an expected O(1) cost per operation, the entire algorithm runs in O(n) and uses up to O(n) additional memory. Directly comparing every element with all following elements would require O(n²) time.

Set or Map

The choice is usually simple. If we only need to store unique values and check whether they exist, use a Set. If each key needs associated information, use a Map. There is no need to store dummy values in a Map just for membership checks when a Set expresses the problem more clearly.

HashSet does not provide an algorithmically useful element order. If a solution depends on traversal order, do not rely on the incidental order in which elements happen to come out of a hash set.
Back Next