HashMap Implementation from Scratch in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Basic Put and Get Operations

What is the output of the following Go code that uses a simple HashMap implementation to put and get values?

DSA Go

package main
import "fmt"

func main() {
    m := NewHashMap(5)
    m.Put("apple", 10)
    m.Put("banana", 20)
    fmt.Println(m.Get("apple"))
    fmt.Println(m.Get("banana"))
    fmt.Println(m.Get("cherry"))
}

type entry struct {
    key   string
    value int
    next  *entry
}

type HashMap struct {
    buckets []*entry
    size    int
}

func NewHashMap(size int) *HashMap {
    return &HashMap{
        buckets: make([]*entry, size),
        size:    size,
    }
}

func (h *HashMap) hash(key string) int {
    hash := 0
    for _, c := range key {
        hash += int(c)
    }
    return hash % h.size
}

func (h *HashMap) Put(key string, value int) {
    index := h.hash(key)
    head := h.buckets[index]
    for e := head; e != nil; e = e.next {
        if e.key == key {
            e.value = value
            return
        }
    }
    newEntry := &entry{key: key, value: value, next: head}
    h.buckets[index] = newEntry
}

func (h *HashMap) Get(key string) int {
    index := h.hash(key)
    for e := h.buckets[index]; e != nil; e = e.next {
        if e.key == key {
            return e.value
        }
    }
    return -1
}

A

10
20
-1

B

0
0
0

C

10
20
0

D

20
10
-1

💡 Hint

Check how the Get method returns -1 if the key is not found.

The code puts two key-value pairs: "apple"->10 and "banana"->20. Then it gets the values for "apple", "banana", and "cherry". Since "cherry" was never added, Get returns -1 for it.

🧠 Conceptual

intermediate

Collision Handling in HashMap

In the given HashMap implementation, how are collisions handled when two different keys hash to the same bucket?

A By resizing the bucket array immediately

B By overwriting the existing entry with the new one

C By using open addressing with linear probing

D By storing entries in a linked list at the bucket index

💡 Hint

Look at how new entries are added to the bucket linked list.

The implementation uses chaining with linked lists to handle collisions. New entries are added at the head of the linked list for the bucket.

🔧 Debug

advanced

Identify the Bug in the Remove Method

Consider this Remove method added to the HashMap. What error will it cause when removing a key that does not exist?

DSA Go

func (h *HashMap) Remove(key string) {
    index := h.hash(key)
    var prev *entry
    for e := h.buckets[index]; e != nil; e = e.next {
        if e.key == key {
            if prev == nil {
                h.buckets[index] = e.next
            } else {
                prev.next = e.next
            }
            return
        }
        prev = e
    }
}

A Runtime error due to nil pointer dereference

B Compilation error due to missing return statement

C No error, removal works correctly even if key not found

D Infinite loop because e.next is not updated properly

💡 Hint

Check what happens if the key is not found in the loop.

If the key is not found, the loop finishes and the function returns without modifying anything. No error occurs.

❓ Predict Output

advanced

Output After Updating an Existing Key

What is the output of this code snippet that updates the value of an existing key in the HashMap?

DSA Go

package main
import "fmt"

func main() {
    m := NewHashMap(3)
    m.Put("cat", 5)
    m.Put("dog", 7)
    m.Put("cat", 10)
    fmt.Println(m.Get("cat"))
    fmt.Println(m.Get("dog"))
}

// HashMap and entry types and methods same as previous examples

A

5
7

B

10
7

C

10
0

D

5
0

💡 Hint

Put updates the value if the key already exists.

The second Put call with key "cat" updates its value from 5 to 10. The value for "dog" remains 7.

🚀 Application

expert

Predict the Number of Items in HashMap Buckets

Given a HashMap of size 4 and these keys inserted: "a", "e", "i", "m", "q", "u", how many entries will be in the bucket at index 1 after all insertions?

DSA Go

func (h *HashMap) hash(key string) int {
    sum := 0
    for _, c := range key {
        sum += int(c)
    }
    return sum % h.size
}

// HashMap size = 4
// Keys inserted: "a", "e", "i", "m", "q", "u"

A 6

B 2

C 4

D 1

💡 Hint

Calculate the sum of ASCII codes for each key and mod by 4.

ASCII values: "a"=97%4=1, "e"=101%4=1, "i"=105%4=1, "m"=109%4=1, "q"=113%4=1, "u"=117%4=1. All keys hash to bucket 1, so 6 entries in bucket 1.

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