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.
| Operation | Complexity |
|---|---|
| Access | O(1) avg / O(n) worst |
| Search | O(1) avg / O(n) worst |
| Insertion | O(1) avg / O(n) worst |
| Deletion | O(1) avg / O(n) worst |
| Space | O(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.