HashMap Implementation from Scratch in DSA Go - Build from Scratch

HashMap Implementation from Scratch

📖 Scenario: Imagine you want to build a simple phone book app that stores names and phone numbers. To do this efficiently, you will create your own version of a HashMap in Go. This will help you understand how data is stored and retrieved quickly.

🎯 Goal: Build a basic HashMap in Go that can store key-value pairs (string keys and string values), add new entries, and retrieve values by key.

📋 What You'll Learn

Create a HashMap struct with buckets

Implement a simple hash function for string keys

Add a method to insert key-value pairs

Add a method to retrieve values by key

Print the stored values to verify correctness

💡 Why This Matters

🌍 Real World

HashMaps are used in many applications like phone books, caches, and databases to store and quickly retrieve data by keys.

💼 Career

Understanding how hash maps work is essential for software developers, especially when optimizing data storage and retrieval in applications.

1

Create the HashMap data structure

Create a struct called HashMap with a field buckets which is a slice of slices of key-value pairs. Define a struct called KeyValue with key and value fields, both of type string. Initialize buckets with 5 empty slices.

DSA Go

type KeyValue struct {
    key string
    value string
}

type HashMap struct {
    buckets [][]KeyValue
}

// Your code here

Hint

Use make([][]KeyValue, 5) to create 5 empty buckets.

2

Add a hash function

Add a method hash to HashMap that takes a key string and returns an int. The method should sum the ASCII values of all characters in the key and return the sum modulo the number of buckets (5).

DSA Go

func (h *HashMap) hash(key string) int {
    // Your code here
    return 0
}

Hint

Loop over each character in the key and add its integer value to sum.

3

Add method to insert key-value pairs

Add a method Put to HashMap that takes key string and value string. Use the hash method to find the bucket index. Append a new KeyValue with the given key and value to the bucket at that index.

DSA Go

func (h *HashMap) Put(key string, value string) {
    // Your code here
}

Hint

Use append to add the new key-value pair to the correct bucket.

4

Add method to get value by key and print results

Add a method Get to HashMap that takes key string and returns string and bool. Use the hash method to find the bucket index. Search the bucket for the key and return the value and true if found. Otherwise, return empty string and false. In main, create a HashMap, add these pairs using Put: "Alice" : "1234", "Bob" : "5678", "Charlie" : "91011". Then print the results of Get("Alice"), Get("Bob"), and Get("Eve").

DSA Go

func (h *HashMap) Get(key string) (string, bool) {
    // Your code here
    return "", false
}

func main() {
    map1 := HashMap{
        buckets: make([][]KeyValue, 5),
    }
    // Your code here
}

Hint

Loop through the bucket to find the key. Print the results exactly as shown.

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