Introduction to Designing a HashSet in JavaScript
A HashSet is one of the most fundamental data structures in computer science. It stores unique elements and provides constant-time average complexity for insertion, deletion, and lookup operations. While JavaScript has a native Set object, implementing your own HashSet from scratch is a classic interview question and an excellent way to understand hashing, collision resolution, and array-based data structures.
In this tutorial, you will learn what a HashSet is, why it matters, how to design one in JavaScript, and the best practices to follow when implementing it. By the end, you will have a working, well-tested HashSet implementation that mirrors the behavior expected in coding interviews and real-world systems alike.
What Is a HashSet?
A HashSet is a collection that stores only unique elements. Unlike an array, it does not maintain a guaranteed order, and it does not allow duplicates. The "Hash" part of the name comes from the fact that it uses a hash function to compute an index where each element should be stored in an underlying array.
The core operations a HashSet must support are:
add(value)— inserts a value into the set if it is not already present.remove(value)— removes the value from the set if it exists.contains(value)— returns a boolean indicating whether the value is in the set.
Optionally, a HashSet can also expose helper methods like size(), clear(), or isEmpty().
Why Designing a HashSet Matters
Understanding how to build a HashSet teaches you several critical concepts:
- Hash functions: How to map arbitrary inputs to fixed-size array indices.
- Collision resolution: What happens when two different values hash to the same index.
- Time-space tradeoffs: How the size of the underlying array affects performance.
- Amortized complexity: Why most operations are O(1) on average but can degrade without resizing.
In real-world applications, HashSets are used for deduplication, caching, membership checks, and as building blocks for more complex structures like HashMaps. Knowing how they work under the hood makes you a stronger engineer and a more confident problem solver.
The Core Idea: Hashing and Buckets
The HashSet maintains an internal array called the bucket array. Each slot in this array is called a bucket. When you want to add a value, you first compute its hash, then take the modulo of the hash with the bucket array length to find the target index.
Because multiple values can hash to the same index, each bucket typically holds a smaller collection — often a linked list or an array. This technique is called separate chaining. When a collision occurs, you simply append the new value to the bucket's collection.
An alternative approach is open addressing, where collisions are resolved by probing for the next available slot. For this tutorial, we will use separate chaining because it is simpler to implement and reason about.
Step-by-Step Implementation
Step 1: Setting Up the Class
We start by defining the class and choosing a default bucket size. A common choice is a prime number like 1000, which helps distribute hashes more uniformly.
class MyHashSet {
constructor() {
this.size = 1000;
this.buckets = new Array(this.size).fill(null).map(() => []);
}
}
Each bucket is initialized as an empty array. Using .map(() => []) ensures that each bucket is a distinct array rather than shared references.
Step 2: Writing the Hash Function
The hash function converts a value into a valid index in the bucket array. For integer keys, a simple modulo works well. For more general inputs, you can use a string-based hash.
_hash(key) {
// For numeric keys, simple modulo works
if (typeof key === 'number') {
return key % this.size;
}
// For other types, convert to string and compute a simple hash
const str = String(key);
let hash = 0;
for (let i = 0; i < str.length; i++) {
hash = (hash * 31 + str.charCodeAt(i)) % this.size;
}
return hash;
}
The multiplier 31 is a common choice in hash functions because it is prime and produces good distribution for typical inputs.
Step 3: Implementing the add Method
To add a value, compute its hash, find the corresponding bucket, and append the value only if it is not already present. This prevents duplicates.
add(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
if (!bucket.includes(key)) {
bucket.push(key);
}
}
Step 4: Implementing the remove Method
Removing a value requires finding its index within the bucket and splicing it out. If the value is not present, the operation does nothing.
remove(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
const pos = bucket.indexOf(key);
if (pos !== -1) {
bucket.splice(pos, 1);
}
}
Step 5: Implementing the contains Method
The contains method checks whether a value exists in the appropriate bucket.
contains(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
return bucket.includes(key);
}
The Complete Implementation
Putting all the pieces together, here is the full HashSet class with some additional helper methods for convenience.
class MyHashSet {
constructor() {
this.size = 1000;
this.buckets = new Array(this.size).fill(null).map(() => []);
this.count = 0;
}
_hash(key) {
if (typeof key === 'number') {
return key % this.size;
}
const str = String(key);
let hash = 0;
for (let i = 0; i < str.length; i++) {
hash = (hash * 31 + str.charCodeAt(i)) % this.size;
}
return hash;
}
add(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
if (!bucket.includes(key)) {
bucket.push(key);
this.count++;
}
}
remove(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
const pos = bucket.indexOf(key);
if (pos !== -1) {
bucket.splice(pos, 1);
this.count--;
}
}
contains(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
return bucket.includes(key);
}
size() {
return this.count;
}
isEmpty() {
return this.count === 0;
}
clear() {
this.buckets = new Array(this.size).fill(null).map(() => []);
this.count = 0;
}
}
Testing the Implementation
Let us verify the HashSet works correctly with a few operations.
const set = new MyHashSet();
set.add(1);
set.add(2);
console.log(set.contains(1)); // true
console.log(set.contains(3)); // false
set.add(2);
console.log(set.size()); // 2 (duplicate not added)
set.remove(2);
console.log(set.contains(2)); // false
console.log(set.size()); // 1
set.add('hello');
console.log(set.contains('hello')); // true
console.log(set.size()); // 2
The output confirms that duplicates are ignored, removals work, and non-numeric keys are handled correctly.
Handling Collisions and Load Factor
As more elements are added, buckets grow longer, and operations slow down. The load factor is the ratio of stored elements to the number of buckets. When the load factor exceeds a threshold — commonly 0.75 — you should resize the bucket array and rehash all existing elements.
Here is how you can add resizing to the implementation:
_resize() {
const oldBuckets = this.buckets;
this.size *= 2;
this.buckets = new Array(this.size).fill(null).map(() => []);
this.count = 0;
for (const bucket of oldBuckets) {
for (const key of bucket) {
this.add(key);
}
}
}
add(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
if (!bucket.includes(key)) {
bucket.push(key);
this.count++;
if (this.count / this.size > 0.75) {
this._resize();
}
}
}
This keeps average time complexity close to O(1) even as the set grows large.
Best Practices
- Choose a prime bucket size: Primes reduce clustering when keys have patterns.
- Use a good hash function: A weak hash function leads to many collisions and degraded performance.
- Resize proactively: Monitor the load factor and resize before buckets become too long.
- Avoid storing duplicates: Always check for existence before inserting.
- Prefer arrays for small buckets: For interview-style implementations, arrays are simpler than linked lists and perform well for small bucket sizes.
- Handle edge cases: Consider what happens with null, undefined, or very large keys.
Time and Space Complexity
With a well-distributed hash function and resizing, the average complexities are:
add: O(1) average, O(n) worst case during resize.remove: O(1) average, O(k) where k is the bucket length.contains: O(1) average, O(k) worst case.- Space: O(n) where n is the number of stored elements.
The worst case occurs when all elements hash to the same bucket, effectively turning the HashSet into a list. A good hash function makes this scenario extremely unlikely.
Conclusion
Designing a HashSet in JavaScript is a rewarding exercise that deepens your understanding of hashing, collision resolution, and dynamic resizing. By building the structure from scratch, you gain insight into how the native Set works internally and how to reason about performance tradeoffs. The implementation covered here — using separate chaining, a simple hash function, and load-factor-based resizing — provides a solid foundation that you can extend with features like iteration, custom equality, or support for complex objects. Whether you are preparing for an interview or simply sharpening your fundamentals, mastering the HashSet is a valuable step in becoming a more capable JavaScript developer.