Introduction to Designing a HashMap in Go
A HashMap is one of the most fundamental data structures in computer science. It provides average O(1) time complexity for insert, delete, and lookup operations, making it indispensable for solving a wide variety of algorithmic problems. In this tutorial, we'll walk through how to design and implement a custom HashMap from scratch in Go, mirroring the popular LeetCode problem "Design HashMap" (Problem 706).
While Go already ships with a powerful built-in map type, building your own HashMap is an excellent way to understand the underlying mechanics: hashing, collision resolution, dynamic resizing, and bucket management. By the end of this guide, you'll have a working, production-style HashMap implementation and a deep understanding of how it works under the hood.
What Is a HashMap?
A HashMap (also called a hash table) is a data structure that maps keys to values using a hash function. The hash function converts a key into an integer index, which is then used to locate the storage bucket where the value resides. This direct addressing is what gives HashMaps their characteristic speed.
The core components of any HashMap are:
- Hash function: Converts a key into a numeric index within the bounds of the underlying array.
- Buckets array: An array of slots, each holding one or more key-value pairs.
- Collision resolution strategy: A mechanism to handle cases where two different keys hash to the same index.
- Load factor and resizing: A threshold that triggers the array to grow, keeping operations efficient.
Why Designing Your Own HashMap Matters
You might wonder why you should build a HashMap when Go's map already exists. There are several compelling reasons:
- Interview readiness: "Design HashMap" is a common coding interview question that tests your understanding of data structures.
- Deep learning: Implementing a HashMap forces you to confront edge cases like collisions, resizing, and hash distribution.
- Customization: In specialized systems, you may need a HashMap with custom eviction policies, concurrency semantics, or memory constraints.
- Performance tuning: Understanding internals helps you reason about performance characteristics in real applications.
Choosing a Collision Resolution Strategy
When two distinct keys produce the same hash index, a collision occurs. There are two main strategies to resolve collisions:
Separate Chaining
Each bucket holds a linked list (or slice) of all key-value pairs that hash to that index. On lookup, you traverse the list to find the matching key. This approach is simple, handles high load factors gracefully, and is what we'll use in this tutorial.
Open Addressing
All entries are stored directly in the bucket array. When a collision occurs, the algorithm probes for the next available slot using strategies like linear probing, quadratic probing, or double hashing. Open addressing can be more cache-friendly but degrades quickly when the table becomes full.
For this tutorial, we'll implement separate chaining because it's intuitive and robust.
Step-by-Step Implementation in Go
Step 1: Defining the Core Types
First, we define the key-value pair structure and the HashMap itself. Each bucket will be a slice of pairs, which gives us a simple and idiomatic way to implement chaining in Go.
package hashmap
// Pair represents a single key-value entry stored in a bucket.
type Pair struct {
Key int
Value int
}
// MyHashMap is our custom hash map implementation.
type MyHashMap struct {
buckets [][]Pair
size int
capacity int
}
We use int keys and values to match the LeetCode problem specification, but the same pattern works for any type with a suitable hash function.
Step 2: Constructor and Hash Function
The constructor initializes the bucket array with a reasonable starting capacity. The hash function maps a key to a valid index using the modulo operation.
const initialCapacity = 16
// Constructor initializes a new MyHashMap.
func Constructor() *MyHashMap {
return &MyHashMap{
buckets: make([][]Pair, initialCapacity),
size: 0,
capacity: initialCapacity,
}
}
// hash converts a key into a bucket index.
func (m *MyHashMap) hash(key int) int {
// A simple but effective hash for integers.
// Multiplying by a prime helps distribute sequential keys.
h := key * 2654435761
if h < 0 {
h = -h
}
return h % m.capacity
}
The multiplier 2654435761 is a well-known constant derived from Knuth's multiplicative hashing method. It helps spread clustered keys more evenly across buckets.
Step 3: The Put Operation
The Put method inserts or updates a key-value pair. If the key already exists in a bucket, we update its value. Otherwise, we append a new pair to the bucket and increment the size. After insertion, we check whether resizing is needed.
// Put inserts or updates the value for the given key.
func (m *MyHashMap) Put(key int, value int) {
index := m.hash(key)
bucket := m.buckets[index]
// Check if the key already exists; if so, update it.
for i := range bucket {
if bucket[i].Key == key {
bucket[i].Value = value
return
}
}
// Key not found, so append a new pair.
m.buckets[index] = append(bucket, Pair{Key: key, Value: value})
m.size++
// Resize if the load factor exceeds 0.75.
if float64(m.size)/float64(m.capacity) > 0.75 {
m.resize()
}
}
Step 4: The Get Operation
The Get method retrieves the value associated with a key. It computes the bucket index, then scans the bucket for a matching key. If not found, it returns -1 as specified by the problem.
// Get returns the value for the given key, or -1 if not found.
func (m *MyHashMap) Get(key int) int {
index := m.hash(key)
bucket := m.buckets[index]
for i := range bucket {
if bucket[i].Key == key {
return bucket[i].Value
}
}
return -1
}
Step 5: The Remove Operation
The Remove method deletes a key-value pair. We locate the pair within its bucket and remove it by slicing it out of the underlying slice. This avoids leaving gaps and keeps the bucket compact.
// Remove deletes the key-value pair for the given key.
func (m *MyHashMap) Remove(key int) {
index := m.hash(key)
bucket := m.buckets[index]
for i := range bucket {
if bucket[i].Key == key {
// Remove the element at index i.
m.buckets[index] = append(bucket[:i], bucket[i+1:]...)
m.size--
return
}
}
}
Step 6: Dynamic Resizing
To maintain O(1) average performance, the HashMap must resize when it becomes too full. Resizing doubles the capacity and rehashes every existing entry into new buckets. This is the most expensive operation, but it happens infrequently and amortizes well.
// resize doubles the capacity and rehashes all entries.
func (m *MyHashMap) resize() {
oldBuckets := m.buckets
m.capacity *= 2
m.buckets = make([][]Pair, m.capacity)
m.size = 0
for _, bucket := range oldBuckets {
for _, pair := range bucket {
m.Put(pair.Key, pair.Value)
}
}
}
Notice that resize reuses the existing Put method. Since size is reset to zero before reinsertion, and the load factor after doubling will be well below 0.75, no recursive resizing occurs.
Step 7: Putting It All Together
Here is the complete implementation in one file, ready to compile and test:
package hashmap
type Pair struct {
Key int
Value int
}
type MyHashMap struct {
buckets [][]Pair
size int
capacity int
}
const initialCapacity = 16
func Constructor() *MyHashMap {
return &MyHashMap{
buckets: make([][]Pair, initialCapacity),
size: 0,
capacity: initialCapacity,
}
}
func (m *MyHashMap) hash(key int) int {
h := key * 2654435761
if h < 0 {
h = -h
}
return h % m.capacity
}
func (m *MyHashMap) Put(key int, value int) {
index := m.hash(key)
bucket := m.buckets[index]
for i := range bucket {
if bucket[i].Key == key {
bucket[i].Value = value
return
}
}
m.buckets[index] = append(bucket, Pair{Key: key, Value: value})
m.size++
if float64(m.size)/float64(m.capacity) > 0.75 {
m.resize()
}
}
func (m *MyHashMap) Get(key int) int {
index := m.hash(key)
bucket := m.buckets[index]
for i := range bucket {
if bucket[i].Key == key {
return bucket[i].Value
}
}
return -1
}
func (m *MyHashMap) Remove(key int) {
index := m.hash(key)
bucket := m.buckets[index]
for i := range bucket {
if bucket[i].Key == key {
m.buckets[index] = append(bucket[:i], bucket[i+1:]...)
m.size--
return
}
}
}
func (m *MyHashMap) resize() {
oldBuckets := m.buckets
m.capacity *= 2
m.buckets = make([][]Pair, m.capacity)
m.size = 0
for _, bucket := range oldBuckets {
for _, pair := range bucket {
m.Put(pair.Key, pair.Value)
}
}
}
Testing the Implementation
Let's write a small test program to verify that our HashMap behaves correctly across insertions, updates, lookups, and deletions.
package main
import (
"fmt"
"yourmodule/hashmap"
)
func main() {
m := hashmap.Constructor()
m.Put(1, 10)
m.Put(2, 20)
fmt.Println("Get(1):", m.Get(1)) // Expected: 10
fmt.Println("Get(3):", m.Get(3)) // Expected: -1
m.Put(2, 30)
fmt.Println("Get(2):", m.Get(2)) // Expected: 30
m.Remove(2)
fmt.Println("Get(2):", m.Get(2)) // Expected: -1
// Stress test with many entries to trigger resizing.
for i := 0; i < 10000; i++ {
m.Put(i, i*10)
}
fmt.Println("Get(9999):", m.Get(9999)) // Expected: 99990
}
Run the program with go run main.go. You should see all expected values printed, confirming that the HashMap handles updates, deletions, and resizing correctly.
Best Practices
Now that you have a working implementation, here are some best practices to keep in mind when designing or using HashMaps in real-world Go applications:
- Choose a good hash function: A poor hash function clusters keys into a few buckets, degrading performance to O(n). For non-integer keys, consider using Go's
hash/fnvorcrypto/sha256packages. - Pick a sensible load factor: A load factor between 0.6 and 0.75 balances memory usage and performance. Too high, and chains grow long; too low, and you waste memory.
- Avoid premature resizing: Start with a reasonable initial capacity based on expected usage. If you know you'll insert 10,000 entries, initialize accordingly to avoid repeated resizing.
- Handle concurrency carefully: This implementation is not safe for concurrent use. For concurrent scenarios, wrap operations with a
sync.RWMutexor use Go's built-insync.Map. - Prefer the built-in map in production: Go's
mapis highly optimized and battle-tested. Only build your own when you have specific requirements the built-in type cannot meet. - Write thorough tests: Cover edge cases such as inserting duplicate keys, removing non-existent keys, and resizing under heavy load. Table-driven tests in Go are ideal for this.
Conclusion
Designing a HashMap from scratch in Go is a rewarding exercise that deepens your understanding of one of the most important data structures in software engineering. By implementing separate chaining for collision resolution, a multiplicative hash function for even distribution, and dynamic resizing to maintain performance, you now have a complete and functional HashMap that mirrors the behavior of Go's built-in map at a conceptual level. Whether you're preparing for a coding interview or simply curious about how things work under the hood, the principles covered here — hashing, collision handling, load factors, and amortized resizing — form the foundation upon which virtually all modern hash-based data structures are built. Use this implementation as a starting point, experiment with open addressing or generic key types, and you'll walk away with a solid grasp of HashMap internals that will serve you throughout your programming career.