Why HashMap Implementation from Scratch in DSA Go?

The Big Idea

What if you could find any piece of data instantly, no matter how big your collection is?

The Scenario

Imagine you have a huge collection of books and you want to find a specific book quickly. Without any system, you would have to look through every book one by one.

This is like trying to find data manually in a big list without any order or quick access.

The Problem

Searching for an item manually in a big list is slow and tiring. It takes a lot of time because you check each item one after another.

Also, if you want to add or remove items, it can be confusing and error-prone because you have to shift things around.

The Solution

A HashMap uses a smart way to store data so you can find it almost instantly. It uses a special function called a hash to decide where to keep each item.

This means you don't have to look through everything; you jump directly to the place where the item is stored.

Before vs After

✗ Before

func findValue(key string, data []string) string {
    for _, item := range data {
        if item == key {
            return item
        }
    }
    return "Not found"
}

✓ After

type KeyValue struct {
    Key   string
    Value string
}

type HashMap struct {
    buckets [][]KeyValue
}

func hash(key string) int {
    h := 0
    for _, c := range key {
        h = 31*h + int(c)
    }
    if h < 0 {
        h = -h
    }
    return h
}

func (h *HashMap) Get(key string) (string, bool) {
    index := hash(key) % len(h.buckets)
    for _, kv := range h.buckets[index] {
        if kv.Key == key {
            return kv.Value, true
        }
    }
    return "", false
}

What It Enables

HashMaps let you store and find data super fast, even when you have tons of information.

Real Life Example

Think about a phone contact list where you want to find a friend's number quickly by their name. A HashMap helps your phone do this instantly.

Key Takeaways

Manual searching is slow and tiring for large data.

HashMaps use hashing to jump directly to data location.

This makes storing and finding data very fast and efficient.

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