AntInLoop

Hash Set Data Structure Data Structure

A Hash Set stores unique elements backed by a hash table, providing O(1) expected membership testing, insertion, and deletion for deduplication and fast lookups.

OperationComplexity
AccessO(1) avg / O(n) worst
SearchO(1) avg / O(n) worst
InsertionO(1) avg / O(n) worst
DeletionO(1) avg / O(n) worst
SpaceO(n)

Interactive Visualizer · C++ / Python / Java / JS Code

Hash Set Data Structure

A Hash Set (std::unordered_set in C++, set in Python, HashSet in Java) stores a collection of unique keys (no duplicates, no associated values) using an underlying Hash Table. It supports $O(1)$ expected insert, erase, and contains, making it the go-to structure for deduplication, visited-state tracking, and fast membership checks.

At a Glance

| Operation | Average Case | Worst Case |

| :--- | :---: | :---: |

| contains(x) / count(x) | $O(1)$ | $O(n)$ |

| insert(x) | $O(1)$ amortized | $O(n)$ |

| erase(x) | $O(1)$ | $O(n)$ |

| Auxiliary Space | $O(n)$ | $O(n)$ |

---

Practice Problems

Easy

1. Longest Consecutive Sequence in $O(n)$ (LeetCode 128)

Given an unsorted integer array, find the length of the longest consecutive integer sequence (e.g., [1, 2, 3, 4]) in $O(n)$ time!

Approach: Insert all elements into an unordered_set. Only start counting upward from x if x - 1 is NOT in the set (so each consecutive run is scanned exactly once!). Time: $O(n)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <unordered_set>
#include <vector>

int longestConsecutive(const std::vector<int>& nums) {
    std::unordered_set<int> s(nums.begin(), nums.end());
    int best = 0;
    for (int x : s) {
        if (!s.count(x - 1)) {
            int len = 1;
            while (s.count(x + len)) ++len;
            best = std::max(best, len);
        }
    }
    return best;
}

int main() {
    std::cout << longestConsecutive({100, 4, 200, 1, 3, 2}) << "\n"; // 4
    return 0;
}

</details>

2. Intersection of Two Arrays (Unique Elements, LeetCode 349)

Return the unique elements present in both arrays a and b in $O(n + m)$ expected time.

Approach: Put a into a Hash Set; for each element x in b, if s.erase(x) removes 1 element, push x to the result (automatically deduplicating!). Time: $O(n + m)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <unordered_set>
#include <vector>

std::vector<int> intersection(const std::vector<int>& a, const std::vector<int>& b) {
    std::unordered_set<int> s(a.begin(), a.end());
    std::vector<int> res;
    for (int x : b) {
        if (s.erase(x) > 0) res.push_back(x);
    }
    return res;
}

int main() {
    for (int x : intersection({4, 9, 5}, {9, 4, 9, 8, 4})) std::cout << x << " ";
    std::cout << "\n"; // 9 4
    return 0;
}

</details>

---

Intermediate

3. Open-Addressing Hash Set with Linear Probing & Tombstones

Implement a compact cache-friendly Hash Set using a single flat array with linear probing and tombstone markers for deletion.

Approach: Track slot states {EMPTY, OCCUPIED, DELETED}. On lookup, stop only at EMPTY (skip DELETED tombstones so probe chains aren't broken!); on insert, reuse the first DELETED or EMPTY slot.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <vector>

class OpenAddressHashSet {
    enum State : char { EMPTY, OCCUPIED, DELETED };
    std::vector<int> keys;
    std::vector<State> states;
    size_t sz = 0;

    size_t hash(int k) const { return static_cast<size_t>(k * 2654435761u) % keys.size(); }

public:
    explicit OpenAddressHashSet(size_t cap = 32) : keys(cap, 0), states(cap, EMPTY) {}

    bool contains(int k) const {
        size_t i = hash(k), n = keys.size();
        for (size_t step = 0; step < n; ++step) {
            size_t pos = (i + step) % n;
            if (states[pos] == EMPTY) return false;
            if (states[pos] == OCCUPIED && keys[pos] == k) return true;
        }
        return false;
    }

    void insert(int k) {
        if (contains(k)) return;
        size_t i = hash(k), n = keys.size();
        for (size_t step = 0; step < n; ++step) {
            size_t pos = (i + step) % n;
            if (states[pos] != OCCUPIED) {
                keys[pos] = k;
                states[pos] = OCCUPIED;
                ++sz;
                return;
            }
        }
    }

    void erase(int k) {
        size_t i = hash(k), n = keys.size();
        for (size_t step = 0; step < n; ++step) {
            size_t pos = (i + step) % n;
            if (states[pos] == EMPTY) return;
            if (states[pos] == OCCUPIED && keys[pos] == k) {
                states[pos] = DELETED;
                --sz;
                return;
            }
        }
    }
};

int main() {
    OpenAddressHashSet hs;
    hs.insert(10); hs.insert(42); hs.insert(74);
    hs.erase(42);
    std::cout << std::boolalpha << hs.contains(10) << " " << hs.contains(42) << " " << hs.contains(74) << "\n";
    return 0;
}

</details>

---

Related Structures & Algorithms

  • Hash Table — key-value generalization of Hash Set.
  • Bloom Filter — space-efficient probabilistic alternative to Hash Set.