HashMap Implementation from Scratch in DSA Go

Mental Model

A HashMap stores key-value pairs by turning keys into indexes to quickly find values.

Analogy: Imagine a library where each book has a unique code. Instead of searching all shelves, you use the code to go directly to the right shelf and find the book fast.

Buckets array:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null
Each bucket can hold a linked list of entries.

Dry Run Walkthrough

Input: Insert keys: "cat"->1, "dog"->2, "bird"->3; then get "dog"

Goal: Store key-value pairs and retrieve the value for "dog" quickly

Step 1: Compute hash for "cat" and find bucket index

[0] -> null
[1] -> null
[2] -> (cat,1) -> null
[3] -> null
[4] -> null

Why: We need to place "cat" in the correct bucket based on its hash

Step 2: Compute hash for "dog" and find bucket index

[0] -> null
[1] -> null
[2] -> (cat,1) -> null
[3] -> null
[4] -> (dog,2) -> null

Why: Place "dog" in its bucket to keep keys organized

Step 3: Compute hash for "bird" and find bucket index

[0] -> null
[1] -> null
[2] -> (bird,3) -> (cat,1) -> null
[3] -> null
[4] -> (dog,2) -> null

Why: Add "bird" to its bucket

Step 4: Get value for key "dog" by hashing and searching bucket

[0] -> null
[1] -> null
[2] -> (bird,3) -> (cat,1) -> null
[3] -> null
[4] -> [(dog,2) ↑] -> null

Why: Find "dog" in its bucket to return its value

Result:

[0] -> null
[1] -> null
[2] -> (bird,3) -> (cat,1) -> null
[3] -> null
[4] -> (dog,2) -> null
Return value: 2

Annotated Code

DSA Go

package main

import (
	"fmt"
)

// Entry holds a key-value pair and points to next entry in bucket
type Entry struct {
	key   string
	value int
	next  *Entry
}

// HashMap holds buckets array
type HashMap struct {
	buckets []*Entry
	size    int
}

// NewHashMap creates a hashmap with fixed bucket size
func NewHashMap(size int) *HashMap {
	return &HashMap{
		buckets: make([]*Entry, size),
		size:    size,
	}
}

// hash function converts key string to bucket index
func (h *HashMap) hash(key string) int {
	hash := 0
	for _, ch := range key {
		hash = (hash*31 + int(ch)) % h.size
	}
	return hash
}

// Put inserts or updates key-value pair
func (h *HashMap) Put(key string, value int) {
	index := h.hash(key) // find bucket
	current := h.buckets[index]
	// traverse bucket to find key
	for current != nil {
		if current.key == key {
			current.value = value // update existing
			return
		}
		current = current.next
	}
	// insert new entry at bucket head
	newEntry := &Entry{key: key, value: value, next: h.buckets[index]}
	h.buckets[index] = newEntry
}

// Get returns value for key, or -1 if not found
func (h *HashMap) Get(key string) int {
	index := h.hash(key) // find bucket
	current := h.buckets[index]
	// search bucket linked list
	for current != nil {
		if current.key == key {
			return current.value
		}
		current = current.next
	}
	return -1 // not found
}

func main() {
	hm := NewHashMap(5)
	hm.Put("cat", 1)
	hm.Put("dog", 2)
	hm.Put("bird", 3)

	fmt.Println(hm.Get("dog"))
}

index := h.hash(key) // find bucket

compute bucket index from key

for current != nil { if current.key == key { current.value = value; return } current = current.next }

search bucket for existing key to update

newEntry := &Entry{key: key, value: value, next: h.buckets[index]}

create new entry and link it at bucket head

current := h.buckets[index]

start searching bucket linked list for get

for current != nil { if current.key == key { return current.value } current = current.next }

traverse bucket to find key and return value

Output

2

Complexity Analysis

Time: O(1) average because hashing gives direct bucket access; O(n) worst if many collisions in one bucket

Space: O(n) because we store all entries in buckets linked lists

vs Alternative: Compared to array search O(n), hashmap average O(1) is much faster for large data

Edge Cases

Empty hashmap

Get returns -1 because no keys exist

DSA Go

return -1 // not found

Insert duplicate key

Value updates instead of adding new entry

DSA Go

if current.key == key { current.value = value; return }

Keys with same hash (collision)

Entries stored in linked list in same bucket

DSA Go

newEntry := &Entry{key: key, value: value, next: h.buckets[index]}

When to Use This Pattern

When you need fast key-value lookup and see collisions handled by chaining, reach for HashMap pattern because it balances speed and memory well.

Common Mistakes

Mistake: Not handling collisions, overwriting entries in bucket
Fix: Use linked list chaining to store multiple entries per bucket

Mistake: Not updating value when key already exists
Fix: Check keys in bucket and update value if found

Summary

Stores key-value pairs using hashing to find bucket quickly.

Use when you want fast insert and lookup by key.

Hashing turns keys into bucket indexes; collisions handled by linked lists.

Practice

1. What is the main purpose of a HashMap in data structures?

easy

A. To store key-value pairs for fast data retrieval

B. To store elements in a sorted order

C. To perform mathematical calculations

D. To store data sequentially like an array

Solution

1. Step 1: Understand the role of HashMap

   A HashMap stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Compare with other data structures

   Unlike arrays or lists, HashMaps do not store data sequentially or sorted but focus on fast lookup.

3. Final Answer:

   To store key-value pairs for fast data retrieval -> Option A

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = key-value pairs for quick lookup [OK]

Common Mistakes:

• Confusing HashMap with arrays or lists
• Thinking HashMap stores data in order
• Assuming HashMap is for mathematical operations

2. Which of the following is the correct way to declare a HashMap in Go?

easy

A. var m = make(map[string]int)

B. var m map[string]int = map[string]int

C. var m = map[string]int()

D. var m map[string]int

Solution

1. Step 1: Understand Go map declaration

   In Go, maps are created using make function: make(map[keyType]valueType).

2. Step 2: Check each option

   A declares a nil map which cannot be used for assignments. B has invalid syntax (cannot assign type as value). C has incorrect syntax (cannot call map type as function). D uses make correctly.

3. Final Answer:

   var m = make(map[string]int) -> Option A

4. Quick Check:

   Use make() to create maps in Go [OK]

Hint: Use make(map[key]value) to create HashMap in Go [OK]

Common Mistakes:

• Declaring without initializing (nil map)
• Using map type without literal or make
• Trying to call map as a function

3. What will be the output of the following Go code snippet implementing a simple HashMap?

package main
import "fmt"
func main() {
  m := make(map[string]int)
  m["apple"] = 5
  m["banana"] = 3
  m["apple"] = 7
  fmt.Println(m["apple"])
}

medium

A. 5

B. Compilation error

C. 0

D. 7

Solution

1. Step 1: Analyze map insertions

   Initially, "apple" is set to 5, then updated to 7, so the last value is 7.

2. Step 2: Print the value for key "apple"

   Printing m["apple"] outputs the updated value 7.

3. Final Answer:

   7 -> Option D

4. Quick Check:

   Last assigned value for key is returned [OK]

Hint: Last value assigned to key is stored [OK]

Common Mistakes:

• Assuming first value remains after update
• Confusing zero value with stored value
• Expecting compilation error due to reassignment

4. Identify the error in this Go code implementing a HashMap:

package main
import "fmt"
func main() {
  var m map[string]int
  m["key"] = 10
  fmt.Println(m["key"])
}

medium

A. Key type is incorrect

B. Map is not initialized before use

C. Value type is incorrect

D. Print statement syntax error

Solution

1. Step 1: Check map initialization

   The map variable m is declared but not initialized with make(), so it is nil.

2. Step 2: Understand assignment to nil map

   Assigning to a nil map causes runtime panic because map is not ready to store data.

3. Final Answer:

   Map is not initialized before use -> Option B

4. Quick Check:

   Maps must be initialized with make() before assignment [OK]

Hint: Always initialize map with make() before adding keys [OK]

Common Mistakes:

• Forgetting to initialize map before use
• Assuming declaration alone creates map
• Confusing map initialization with slice

5. You want to implement a HashMap from scratch in Go without using built-in maps. Which of the following is the best approach to handle collisions?

hard

A. Ignore collisions and store only one key-value pair per bucket

B. Overwrite existing key-value pair without checking

C. Use a linked list at each bucket to store multiple key-value pairs

D. Use an array of fixed size without hashing keys

Solution

1. Step 1: Understand collision in HashMap

   When two keys hash to the same bucket, collision occurs and must be handled to store both pairs.

2. Step 2: Evaluate collision handling methods

   Using a linked list at each bucket allows storing multiple pairs safely. Overwriting loses data, ignoring collisions loses data, and fixed arrays without hashing lose efficiency.

3. Final Answer:

   Use a linked list at each bucket to store multiple key-value pairs -> Option C

4. Quick Check:

   Separate chaining with linked lists handles collisions [OK]

Hint: Use linked lists per bucket to handle collisions [OK]

Common Mistakes:

• Overwriting values on collision
• Ignoring collisions causing data loss
• Not using hashing for key distribution