Hash Sets vs Hash Maps

In the world of hash-based data structures, we often focus on the key-value paradigm—a dictionary-like model where every key is associated with some meaningful data. But there exists a simpler, equally powerful abstraction: the hash set. A hash set answers one question, and one question only: Is this element present?

This seemingly simple question—membership testing—forms the backbone of countless algorithms, from duplicate detection to graph traversal, from spell checking to database query optimization. Understanding hash sets deeply means understanding when simplicity is not just sufficient, but optimal.

In this comprehensive exploration, we will dissect the hash set from first principles, examining its mathematical foundations, implementation mechanics, and the subtle but critical distinction between storing keys alone versus key-value pairs.

Before diving into hash sets as a data structure, we must first understand sets as a mathematical concept. This foundation is essential because a hash set is simply an efficient implementation of the mathematical set abstraction.

What Is a Mathematical Set?

A set is a well-defined collection of distinct objects, considered as an object in its own right. The objects in a set are called elements or members. The defining properties of a set are:

1. Distinctness: No element appears more than once. The set {1, 2, 2, 3} is identical to {1, 2, 3}.
2. Unordered nature: The set {a, b, c} is identical to {c, a, b}. Order has no meaning.
3. Membership is binary: An element is either in the set or not. There is no "how much" or "how many times."

This third property is crucial: a set tracks presence, not quantity or association. This is fundamentally different from a map, which associates keys with values.

Additional Set Operations

Beyond the five fundamental operations, sets support several derived operations:

• Difference (S₁ \ S₂): Elements in S₁ but not in S₂
• Symmetric Difference (S₁ △ S₂): Elements in exactly one of S₁ or S₂
• Subset Test (⊆): Is every element of S₁ also in S₂?
• Superset Test (⊇): Does S₁ contain every element of S₂?
• Cardinality (|S|): The number of elements in the set

Why Sets Matter in Computing

Sets appear everywhere in computing because many problems are fundamentally about presence, not association:

• Visited tracking in graph traversal: Have we seen this node? (Yes/No)
• Duplicate detection: Have we encountered this value before? (Yes/No)
• Spell checking dictionary: Is this a valid word? (Yes/No)
• Bloom filter seeds: Which values have we potentially seen? (Maybe Yes/Definitely No)
• Database constraint validation: Is this primary key already taken? (Yes/No)

In all these cases, we don't need to store what is associated with the key—we only need to know whether the key exists.

A mathematical set is an abstraction. To use sets in a computer program, we need a concrete implementation. The question becomes: how do we implement set operations efficiently?

Naive Implementations and Their Limitations

Let's consider how we might implement a set without hashing:

Unsorted Array/List:

• Membership test: O(n) — must scan entire collection
• Insertion: O(n) — must first check for duplicates
• Deletion: O(n) — must find element, then shift

Sorted Array:

• Membership test: O(log n) — binary search
• Insertion: O(n) — binary search + shift elements
• Deletion: O(n) — binary search + shift elements

Balanced Binary Search Tree (BST):

• Membership test: O(log n)
• Insertion: O(log n)
• Deletion: O(log n)
• Bonus: Elements remain sorted

A balanced BST (like a red-black tree or AVL tree) provides O(log n) for all operations, which is respectable. But for sets where we don't need ordering, we can do better.

The Hash Set Breakthrough

A hash set achieves O(1) average-case complexity for membership, insertion, and deletion by using a hash function to compute array indices directly from element values.

The key insight: instead of searching for an element, we compute where it should be. If we want to know whether element x is in the set, we:

1. Compute hash(x) to get an integer
2. Calculate index = hash(x) % tableSize
3. Look at position index in our array
4. Handle collisions if multiple elements map to the same index

This transforms searching from "scan everything" to "go directly to the answer."

What Gets Stored in a Hash Set?

This is the crucial distinction from a hash map:

Hash Map stores: hash(key) → bucket containing [(key₁, value₁), (key₂, value₂), ...]

Hash Set stores: hash(key) → bucket containing [key₁, key₂, ...]

In a hash set, we store only the keys themselves. There is no value associated with each key. Each bucket (or slot, depending on collision strategy) contains just the elements that hashed to that position.

Understanding how hash sets are represented in memory illuminates both their efficiency and their constraints.

The Underlying Array Structure

At its core, a hash set maintains an array (sometimes called a "bucket array" or "hash table"). Each position in this array is a slot that can hold:

• In open addressing: A single element, an empty marker, or a "deleted" tombstone
• In separate chaining: A linked list (or other collection) of elements that hashed to this position

Let's visualize both approaches:

Memory Efficiency: Set vs Map

Because hash sets don't store values, they use less memory per element than hash maps:

Separate Chaining:

• Hash Set node: [key data][next pointer]
• Hash Map node: [key data][value data][next pointer]

Open Addressing:

• Hash Set slot: [key data] or [state flag]
• Hash Map slot: [key data][value data] or [state flag]

The memory savings depend on the size of values in the map case. If values are large (e.g., objects, strings), a hash set can use significantly less memory than a hash map with dummy values.

The Null Value Pattern: An Anti-Pattern

Some developers, when they need set semantics but only have a hash map available, use a pattern like:

# Anti-pattern: Using map as set with null values
seen = {}
for item in items:
    seen[item] = None  # or True, or 1, or any dummy value

While this works, it's suboptimal:

1. Wastes memory: Each entry stores an unnecessary value
2. Obscures intent: The code doesn't clearly communicate "this is a set"
3. May prevent optimization: The language runtime can't optimize for set-specific patterns

When you need a set, use a set.

Let's examine each core hash set operation with implementation-level detail, understanding exactly what happens under the hood.

The add(element) Operation

Purpose: Insert an element into the set if it doesn't already exist.

Algorithm (Separate Chaining):

1. Compute hashCode(element)
2. Calculate index = hashCode % tableSize
3. Traverse the linked list at buckets[index]
4. If element is found, return (already exists, no-op)
5. If not found, prepend element to the list
6. Increment size counter
7. If load factor exceeds threshold, trigger rehashing

Algorithm (Open Addressing - Linear Probing):

1. Compute hashCode(element)
2. Calculate index = hashCode % tableSize
3. While slots[index] is occupied:
   • If slots[index] == element, return (already exists)
   • Increment index = (index + 1) % tableSize
4. Store element at slots[index]
5. Increment size counter
6. If load factor exceeds threshold, trigger rehashing

Key insight: The "no duplicates" invariant is enforced by checking for existence before insertion. This is why hash sets require elements to be both hashable and comparable for equality.

The contains(element) / has(element) Operation

Purpose: Test whether an element is present in the set.

Algorithm:

1. Compute hashCode(element)
2. Calculate index = hashCode % tableSize
3. Search for element in buckets[index] (chain or probe sequence)
4. Return true if found, false otherwise

This is the most frequently used operation in most applications. The O(1) average complexity is why hash sets are preferred for membership testing.

The remove(element) Operation

Purpose: Remove an element from the set if it exists.

Algorithm (Separate Chaining):

1. Compute hashCode(element)
2. Calculate index = hashCode % tableSize
3. Traverse the linked list, maintaining a previous pointer
4. If found, unlink the node from the chain
5. Decrement size counter
6. Return true if removed, false if not found

Algorithm (Open Addressing):

1. Find the element using the probing sequence
2. If found, mark the slot with a DELETED tombstone
3. Decrement size counter

The tombstone is necessary because simply emptying the slot would break the probe sequence for other elements.

A critical aspect of hash sets that catches many developers off guard is the immutability requirement for set elements.

The Problem: Mutable Elements in Sets

Consider this scenario:

# Dangerous: Mutable element in a set
class Person:
    def __init__(self, name):
        self.name = name
    
    def __hash__(self):
        return hash(self.name)
    
    def __eq__(self, other):
        return self.name == other.name

person = Person("Alice")
people = {person}  # Add to set

# Later...
person.name = "Bob"  # Mutate the object!

# Now we have a problem:
print(Person("Alice") in people)  # False - original hash bucketing
print(Person("Bob") in people)    # False - wrong bucket!
print(person in people)           # Undefined behavior!

What happened? The person object was hashed based on "Alice" and placed in the corresponding bucket. When we changed the name to "Bob", the hash value changed, but the object's position in the set didn't. Now:

1. Searching for "Alice" looks in the right bucket but finds an object that says "Bob"
2. Searching for "Bob" looks in the wrong bucket
3. The object is effectively lost in the set

What Makes a Type Hashable?

Not all types can be used in a hash set. The requirements are:

1. The type must implement a hash function

This function must:

• Return an integer (the hash code)
• Be deterministic (same input → same output)
• Be consistent with equality (equal objects → equal hash codes)

2. The type must implement equality comparison

This is needed because:

• Hash collisions occur (different objects, same hash)
• We must be able to distinguish colliding elements

3. Ideally, the type should be immutable

Immutability guarantees that the hash value never changes, preventing the "lost object" problem.

Language-Specific Hashability Rules

Python:

• Built-in immutable types are hashable: int, float, str, tuple (if contents are hashable), frozenset
• Mutable types are NOT hashable by default: list, dict, set
• Custom classes are hashable by default (based on object identity), but should override __hash__ and __eq__ for value-based equality

Java:

• Primitive wrappers are hashable: Integer, String, Double, etc.
• Custom classes must override hashCode() and equals() for use in HashSet
• Using mutable objects as keys is allowed but dangerous

JavaScript:

• Set uses the SameValueZero algorithm (similar to ===)
• Only primitives and object references are directly usable
• Object equality is by reference, not by value

One of the powerful features of sets (that maps don't naturally provide) is set algebra—operations that combine or compare sets in mathematically meaningful ways. These operations are built into most set implementations.

Union: Combining Two Sets

Mathematical definition: A ∪ B = {x : x ∈ A or x ∈ B}

Implementation: Create a new set containing all elements from both input sets.

set1 = {1, 2, 3}
set2 = {3, 4, 5}

# Using operator
result = set1 | set2  # {1, 2, 3, 4, 5}

# Using method
result = set1.union(set2)  # {1, 2, 3, 4, 5}

Time Complexity: O(|A| + |B|) — we must examine every element from both sets.

Intersection: Common Elements

Mathematical definition: A ∩ B = {x : x ∈ A and x ∈ B}

Implementation: Create a new set containing only elements present in both.

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}

result = set1 & set2  # {3, 4}
result = set1.intersection(set2)  # {3, 4}

Time Complexity: O(min(|A|, |B|)) — iterate over the smaller set, check membership in the larger.

Difference: Elements in One But Not the Other

Mathematical definition: A \ B = {x : x ∈ A and x ∉ B}

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}

result = set1 - set2  # {1, 2}
result = set1.difference(set2)  # {1, 2}

Time Complexity: O(|A|) — must examine every element in the first set.

Symmetric Difference: Exclusive Elements

Mathematical definition: A △ B = {x : x ∈ A XOR x ∈ B}

set1 = {1, 2, 3}
set2 = {3, 4, 5}

result = set1 ^ set2  # {1, 2, 4, 5}
result = set1.symmetric_difference(set2)  # {1, 2, 4, 5}

Time Complexity: O(|A| + |B|)

Recognizing when to use a set versus a map is a fundamental skill. Here's a framework for making the right choice.

Use a Hash Set When:

The fundamental question is "Is X present?"

If you only need to know whether something exists—without needing to retrieve associated data—a set is appropriate.

Examples:

• Tracking visited nodes in graph traversal
• Checking if a word is in a dictionary
• Detecting duplicates in a stream
• Maintaining a blacklist or whitelist
• Implementing set algebra (union, intersection, etc.)

You need to enforce uniqueness without additional data

Sets naturally enforce uniqueness. If you're storing items where duplicates are meaningless, a set documents this constraint.

Memory efficiency matters

When storing millions of elements, the memory saved by not storing values can be significant.

You want clear, self-documenting code

Using if item in my_set is clearer than if item in my_dict when you don't care about the value.

When NOT to Use a Set (Use a Map Instead)

You need to associate data with each key

If you're tracking not just presence but also information about each key, you need a map.

• User ID → User profile data
• Word → Definition
• Node → Distance from source
• Cache key → Cached value

You need to count occurrences

If you need to know how many times something appears, use a map where values are counts.

# Counting occurrences - need a map, not a set
word_counts = {}  # word → count
for word in document:
    word_counts[word] = word_counts.get(word, 0) + 1

You need key-value semantics

Configuration settings, environment variables, HTTP headers—these are naturally key-value pairs.

We have taken a deep dive into hash sets—their mathematical foundations, implementation mechanics, and practical usage patterns. Let's consolidate the key insights: