HashMap Implementation from Scratch in DSA Go - Time & Space Complexity

Time Complexity: HashMap Implementation from Scratch

O(1) average, O(n) worst

Understanding Time Complexity

When building a HashMap from scratch, it is important to understand how fast it can add and find items.

We want to know how the time to do these actions changes as we add more items.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func (h *HashMap) Put(key string, value int) {
  index := h.hash(key) % len(h.buckets)
  for i := 0; i < len(h.buckets[index]); i++ {
    if h.buckets[index][i].key == key {
      h.buckets[index][i].value = value
      return
    }
  }
  h.buckets[index] = append(h.buckets[index], entry{key, value})
}

This code adds or updates a key-value pair in a HashMap using separate chaining to handle collisions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop through the bucket list at the hashed index to find the key.
• How many times: Up to the number of entries in that bucket, which depends on collisions.

How Execution Grows With Input

As more items are added, buckets may have more entries, making the loop longer.

Input Size (n)	Approx. Operations
10	Few entries per bucket, loop runs about 1-2 times
100	More entries, loop runs several times if collisions occur
1000	Many entries, loop can run many times if buckets are uneven

Pattern observation: If the hash spreads keys well, the loop stays short; otherwise, it grows with n.

Final Time Complexity

Time Complexity: O(1) on average, O(n) in worst case

On average, adding or finding a key takes constant time, but if many keys collide, it can take time proportional to the number of keys.

Common Mistake

[X] Wrong: "HashMap operations always take the same short time no matter what."

[OK] Correct: If many keys end up in the same bucket, the operation slows down because it must check many entries.

Interview Connect

Understanding how HashMaps work under the hood helps you explain why they are fast and when they might slow down, a key skill in coding interviews.

Self-Check

"What if we changed the collision handling from separate chaining to open addressing? How would the time complexity change?"

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