Introduction to Designing a HashSet in Go
A HashSet is one of the most fundamental data structures in computer science. It provides average O(1) time complexity for insertions, deletions, and lookups, making it ideal for scenarios where you need to track unique elements efficiently. In this tutorial, we'll walk through how to design and implement a HashSet from scratch in Go, mirroring the popular LeetCode problem "Design HashSet" (Problem 705).
While Go already provides an excellent built-in map type that can simulate set behavior, building your own HashSet teaches you about hashing, collision resolution, and dynamic resizing — concepts every backend developer should understand deeply.
What Is a HashSet?
A HashSet is a collection that stores unique elements with no duplicates. Unlike arrays or slices, it does not maintain insertion order, but it offers extremely fast membership testing. The core idea is to use a hash function that maps each element to an index in an underlying array (often called "buckets").
The two essential operations of any HashSet are:
Add(key)— insert a key if it doesn't already exist.Contains(key)— return true if the key exists in the set.Remove(key)— delete the key if present.
Why Designing Your Own HashSet Matters
You might wonder: why build a HashSet when Go's map[int]bool already does the job? The answer is twofold. First, understanding the internals helps you make better engineering decisions when choosing data structures in production systems. Second, many coding interviews and system design questions require you to implement these primitives from scratch, demonstrating your grasp of time and space tradeoffs.
Designing a HashSet also forces you to confront real-world challenges such as hash collisions, load factors, and memory allocation strategies — all of which appear in distributed systems, databases, and caching layers.
Approach 1: Simple Array-Based HashSet
The simplest approach is to use a boolean array where the index represents the key. This works only when the key range is small and known in advance. For the LeetCode problem, keys range from 0 to 1,000,000, so we can allocate a fixed-size slice.
Implementation
package main
import "fmt"
type MyHashSet struct {
data []bool
}
func Constructor() MyHashSet {
return MyHashSet{
data: make([]bool, 1000001),
}
}
func (this *MyHashSet) Add(key int) {
this.data[key] = true
}
func (this *MyHashSet) Remove(key int) {
this.data[key] = false
}
func (this *MyHashSet) Contains(key int) bool {
return this.data[key]
}
func main() {
set := Constructor()
set.Add(1)
set.Add(2)
fmt.Println(set.Contains(1)) // true
fmt.Println(set.Contains(3)) // false
set.Add(2)
fmt.Println(set.Contains(2)) // true
set.Remove(2)
fmt.Println(set.Contains(2)) // false
}
This solution is extremely fast — every operation is O(1) — but it consumes a fixed 1MB of memory regardless of how many elements are actually stored. For sparse datasets, this is wasteful.
Approach 2: Hashing with Separate Chaining
A more realistic and memory-efficient approach uses a hash function to map keys into a fixed number of buckets. Each bucket holds a linked list (or slice) of keys that hash to the same index. When collisions occur, the keys are chained together. This technique is called separate chaining.
Implementation
package main
import "fmt"
const base = 769
type MyHashSet struct {
buckets [][]int
}
func Constructor() MyHashSet {
return MyHashSet{
buckets: make([][]int, base),
}
}
func (this *MyHashSet) hash(key int) int {
return key % base
}
func (this *MyHashSet) Add(key int) {
h := this.hash(key)
for _, v := range this.buckets[h] {
if v == key {
return // already exists
}
}
this.buckets[h] = append(this.buckets[h], key)
}
func (this *MyHashSet) Remove(key int) {
h := this.hash(key)
bucket := this.buckets[h]
for i, v := range bucket {
if v == key {
// remove element at index i
this.buckets[h] = append(bucket[:i], bucket[i+1:]...)
return
}
}
}
func (this *MyHashSet) Contains(key int) bool {
h := this.hash(key)
for _, v := range this.buckets[h] {
if v == key {
return true
}
}
return false
}
func main() {
set := Constructor()
set.Add(1)
set.Add(1000001)
set.Add(769)
fmt.Println(set.Contains(1)) // true
fmt.Println(set.Contains(769)) // true
set.Remove(769)
fmt.Println(set.Contains(769)) // false
}
Why 769 Buckets?
The choice of 769 is deliberate — it is a prime number. Using a prime as the modulus reduces the likelihood of clustering when keys share common divisors with the bucket count. With 769 buckets and up to 1,000,000 possible keys, the average chain length is roughly 1,300, keeping operations efficient in practice.
Approach 3: Using Go's Built-in Map
In production Go code, the idiomatic way to implement a set is to use a map with boolean or struct values. The empty struct struct{} consumes zero bytes, making it the most memory-efficient choice.
package main
import "fmt"
type IntSet struct {
items map[int]struct{}
}
func NewIntSet() *IntSet {
return &IntSet{
items: make(map[int]struct{}),
}
}
func (s *IntSet) Add(key int) {
s.items[key] = struct{}{}
}
func (s *IntSet) Remove(key int) {
delete(s.items, key)
}
func (s *IntSet) Contains(key int) bool {
_, ok := s.items[key]
return ok
}
func (s *IntSet) Size() int {
return len(s.items)
}
func main() {
s := NewIntSet()
s.Add(10)
s.Add(20)
fmt.Println(s.Contains(10)) // true
fmt.Println(s.Size()) // 2
s.Remove(10)
fmt.Println(s.Contains(10)) // false
}
This approach leverages Go's highly optimized runtime map implementation, which handles resizing, hashing, and collision resolution internally. For most real-world applications, this is the recommended approach.
Best Practices
- Choose prime bucket counts when implementing custom hash tables to minimize collision clustering.
- Use
struct{}as the map value type when building sets with Go's built-in map to save memory. - Preallocate capacity when you know the approximate number of elements using
make(map[int]struct{}, n)to avoid costly rehashing. - Make operations idempotent — adding an existing key or removing a missing key should not cause errors.
- Consider thread safety — if your set is accessed concurrently, wrap operations with a
sync.RWMutexor usesync.Map. - Profile before optimizing — the simple array-based approach may be the fastest for small, dense key ranges, while chaining wins for sparse, large-range keys.
Thread-Safe Variant Example
package main
import "sync"
type ConcurrentIntSet struct {
mu sync.RWMutex
items map[int]struct{}
}
func NewConcurrentIntSet() *ConcurrentIntSet {
return &ConcurrentIntSet{
items: make(map[int]struct{}),
}
}
func (s *ConcurrentIntSet) Add(key int) {
s.mu.Lock()
defer s.mu.Unlock()
s.items[key] = struct{}{}
}
func (s *ConcurrentIntSet) Remove(key int) {
s.mu.Lock()
defer s.mu.Unlock()
delete(s.items, key)
}
func (s *ConcurrentIntSet) Contains(key int) bool {
s.mu.RLock()
defer s.mu.RUnlock()
_, ok := s.items[key]
return ok
}
Using a RWMutex allows multiple readers to access the set concurrently while ensuring exclusive access for writers, which is a good balance between safety and performance for read-heavy workloads.
Conclusion
Designing a HashSet in Go is a deceptively simple exercise that reveals important principles about hashing, collision handling, and memory tradeoffs. The array-based approach offers unbeatable speed for small, dense key ranges, while separate chaining with a prime bucket count provides a scalable, memory-efficient solution for sparse datasets. In production, however, Go's built-in map with struct{} values remains the most pragmatic choice, combining readability, performance, and maintainability. By understanding all three approaches, you'll be well-equipped to choose the right strategy for any problem — whether it's a coding interview, a systems design discussion, or a real-world Go service.