Hash Set

A hash set stores unique values and supports fast membership checks in typical cases. In Python, the built-in set is the standard hash set.

Sets are useful when the algorithm only needs to know whether a value has appeared, not what value is attached to it.

Core Idea

A set answers membership questions directly: “Have I seen this before?” or “Is this value allowed?”

Typical add, remove, and membership operations are treated as O(1) average time.

The set is useful when the only stored fact is presence. If the algorithm also needs a count, index, distance, or other value, a hash map is usually the better structure.

Function Contract

has_duplicate(values) expects an iterable of hashable values. Hashable values include integers, strings, and tuples of hashable values.

It returns True as soon as a repeated value is found. If the loop finishes without finding a repeat, it returns False.

Python Example

seen = set()
 
for value in [4, 7, 4, 9]:
    if value in seen:
        print("duplicate", value)
    seen.add(value)

The second 4 is detected because 4 is already in seen.

Duplicate Detection

A set can detect duplicates in one pass:

def has_duplicate(values):
    seen = set()
 
    for value in values:
        if value in seen:
            return True
        seen.add(value)
 
    return False

The brute-force alternative would compare pairs of values. The set version stores previous values so each new value needs only one membership check.

Visited State

Sets are also common in graph and grid traversal:

visited = set()
visited.add((row, col))

The stored value should represent the full state that has already been seen. For a plain grid, (row, col) may be enough. For a grid with keys or remaining fuel, the set may need a larger tuple.

Complexity

Membership, insertion, and deletion are average O(1). A set that stores up to n values uses O(n) space.

Step-by-Step Trace

For [4, 2, 4], the set is empty at first. After seeing 4, the set is {4}. After seeing 2, it is {4, 2}. When the second 4 appears, membership check says 4 was already seen, so the function returns True.

Common Confusions

A set does not store duplicates. Adding the same value again does not create another copy.

A set is not a list without order. If the algorithm depends on sequence position, use a list or store the position separately.

The values must be hashable. Numbers, strings, and tuples of hashable values work. Lists and dictionaries do not.

When To Use It

Use a hash set for duplicate detection, visited nodes, allowed values, forbidden values, and fast membership checks.

Do not use a set if multiplicity matters. For example, checking whether two words have the same character counts needs a dictionary or collections.Counter, not just a set of characters.

The Main Point

A hash set answers whether a value has already appeared. It is the default tool for duplicate detection and fast membership checks when values are hashable.