HashMap Implementation from Scratch in DSA Go - Deep Dive

Overview - HashMap Implementation from Scratch

What is it?

A HashMap is a data structure that stores key-value pairs. It allows you to quickly find, add, or remove items by using a key. Internally, it uses a function called a hash function to decide where to store each item. This makes searching very fast compared to looking through all items one by one.

Why it matters

Without HashMaps, programs would have to search through lists or arrays to find data, which can be very slow as data grows. HashMaps solve this by giving almost instant access to data using keys. This speed is crucial for many applications like databases, caches, and real-time systems where quick data access matters.

Where it fits

Before learning HashMaps, you should understand arrays and basic data storage. After mastering HashMaps, you can explore more complex structures like Trees, Graphs, and advanced hashing techniques. HashMaps are a foundation for many algorithms and systems.

Mental Model

Core Idea

A HashMap uses a hash function to turn keys into indexes, storing values in buckets for fast access.

Think of it like...

Imagine a library where books are stored by their unique code. Instead of searching every shelf, you use the code to find the exact shelf and spot quickly.

HashMap Structure:

[Key] --hash_function--> [Index in array]

Array (Buckets):
┌─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │ ...
├─────┼─────┼─────┼─────┼─────┤
│ []  │ []  │ []  │ []  │ []  │
└─────┴─────┴─────┴─────┴─────┘

Each bucket holds a list of key-value pairs to handle collisions.

Build-Up - 7 Steps

1

Foundation

Understanding Key-Value Storage

Concept: Learn what key-value pairs are and how they store data.

A key-value pair is like a label and its content. For example, a phone book stores names (keys) and phone numbers (values). You can look up a name to find the number quickly. This simple idea is the base of a HashMap.

Result

You understand that data is stored as pairs, making it easy to find values by keys.

Knowing key-value pairs helps you see why HashMaps focus on keys for fast data retrieval.

2

Foundation

What is a Hash Function?

Concept: Introduce the hash function that converts keys into array indexes.

A hash function takes a key (like a word) and turns it into a number. This number tells us where to store or find the value in an array. For example, hashing 'cat' might give 2, so we store 'cat's value at index 2.

Result

You see how keys become numbers that point to storage locations.

Understanding hashing is crucial because it makes data access fast and direct.

3

Intermediate

Handling Collisions with Buckets

🤔Before reading on: do you think two different keys can share the same storage spot? Commit to yes or no.

Concept: Learn that different keys can hash to the same index, causing collisions, and how to handle them.

Sometimes, two keys produce the same hash number. This is called a collision. To fix this, each array spot (bucket) holds a list of key-value pairs. When adding or searching, we check this list to find the right key.

Result

You understand that buckets store multiple pairs to handle collisions safely.

Knowing collision handling prevents confusion when keys share storage spots.

4

Intermediate

Implementing Basic HashMap Operations

🤔Before reading on: do you think adding a new key-value pair always replaces existing data or adds alongside it? Commit to your answer.

Concept: Learn how to add, get, and remove key-value pairs in a HashMap.

To add: hash the key, go to the bucket, check if key exists, update or add. To get: hash the key, search bucket for key, return value. To remove: hash the key, find and delete the pair from bucket.

Result

You can perform basic operations on a HashMap correctly.

Understanding these operations builds the foundation for using and implementing HashMaps.

5

Intermediate

Resizing the HashMap Dynamically

🤔Before reading on: do you think a fixed-size HashMap works well as data grows? Commit to yes or no.

Concept: Learn why and how to resize the HashMap when it gets full.

When many items fill the HashMap, buckets get crowded, slowing access. To fix this, we create a bigger array and rehash all items into it. This keeps operations fast even as data grows.

Result

You understand dynamic resizing keeps HashMaps efficient.

Knowing resizing prevents performance drops in real applications.

6

Advanced

Choosing and Designing Hash Functions

🤔Before reading on: do you think any function that returns a number can be a good hash function? Commit to yes or no.

Concept: Learn what makes a good hash function and why it matters.

A good hash function spreads keys evenly to avoid collisions. It should be fast and deterministic (same key always same hash). Poor hash functions cause many collisions, slowing down the HashMap.

Result

You can evaluate and design better hash functions.

Understanding hash function quality is key to building efficient HashMaps.

7

Expert

Optimizing Collision Handling Techniques

🤔Before reading on: do you think linked lists are the only way to handle collisions? Commit to yes or no.

Concept: Explore advanced collision handling like open addressing and chaining variations.

Besides linked lists (chaining), collisions can be handled by open addressing, where we find another empty spot in the array. Techniques like linear probing or double hashing help find these spots. Each method has tradeoffs in speed and memory.

Result

You know multiple collision strategies and when to use them.

Knowing collision handling options helps optimize HashMaps for different needs.

Under the Hood

When you add a key-value pair, the hash function converts the key into an index. The HashMap then stores the pair in the bucket at that index. If multiple keys map to the same index, the bucket holds a list of pairs. When searching, the HashMap hashes the key, goes to the bucket, and scans the list to find the matching key. Resizing creates a bigger array and re-inserts all pairs using the hash function again.

Why designed this way?

HashMaps were designed to provide average constant-time access to data. Using a hash function to map keys to indexes avoids slow searches. Handling collisions with buckets or open addressing balances speed and memory. Resizing ensures performance stays good as data grows. Alternatives like trees are slower for average cases, so HashMaps became popular for fast lookups.

HashMap Internal Flow:

[Key] --hash_function--> [Index]
       │
       ▼
┌───────────────┐
│ Array of Buckets│
└───────────────┘
       │
       ▼
┌───────────────┐
│ Bucket (List) │
│ ┌───────────┐ │
│ │(key,value)│ │
│ │(key,value)│ │
│ └───────────┘ │
└───────────────┘

On collision, multiple pairs stored in bucket list.

Myth Busters - 4 Common Misconceptions

Quick: do you think a HashMap always stores keys in the order they were added? Commit to yes or no.

Common Belief: HashMaps keep keys in the order they were inserted.

Reality: HashMaps do not guarantee any order of keys; the order depends on the hash function and collisions.

Why it matters: Assuming order can cause bugs when iterating keys or values, leading to unexpected results.

Quick: do you think a hash function can produce the same index for different keys without causing problems? Commit to yes or no.

Common Belief: If two keys hash to the same index, one will overwrite the other.

Reality: HashMaps handle collisions by storing multiple pairs in the same bucket, so no data is lost.

Why it matters: Not knowing this leads to incorrect assumptions about data loss and incorrect implementations.

Quick: do you think resizing a HashMap happens automatically without any cost? Commit to yes or no.

Common Belief: HashMaps resize instantly and without performance impact.

Reality: Resizing requires rehashing all items, which is costly and can cause delays.

Why it matters: Ignoring resizing cost can cause performance issues in time-critical applications.

Quick: do you think any function that returns a number can be a good hash function? Commit to yes or no.

Common Belief: Any function that returns a number from a key is a good hash function.

Reality: Good hash functions must distribute keys evenly and be fast; poor ones cause many collisions.

Why it matters: Using bad hash functions leads to slow lookups and poor HashMap performance.

Expert Zone

1

The choice between chaining and open addressing affects memory usage and cache performance in subtle ways.

2

Load factor thresholds for resizing balance memory use and speed; tuning them can optimize performance for specific workloads.

3

Hash functions can be tailored to key types (strings, integers) for better distribution and speed.

When NOT to use

HashMaps are not ideal when you need ordered data; use balanced trees or linked hash maps instead. For small datasets or when memory is very limited, simple arrays or lists may be better. When keys are complex objects without good hash functions, consider other data structures like tries or trees.

Production Patterns

In production, HashMaps are often combined with caching layers to speed up repeated queries. They are used in databases for indexing, in compilers for symbol tables, and in web servers for session management. Techniques like concurrent HashMaps allow safe use in multi-threaded environments.

Connections

Trie (Prefix Tree)

Alternative data structure for key-value storage with prefix-based keys.

Understanding HashMaps helps appreciate Tries as they both store key-value pairs but optimize for different key patterns.

Cryptographic Hash Functions

Related concept of hashing but focused on security rather than speed and distribution.

Knowing HashMap hash functions clarifies why cryptographic hashes are slower and designed differently.

Cache Memory in Computer Architecture

Both use hashing and indexing to quickly locate data.

Understanding HashMaps deepens understanding of how caches map memory addresses to cache lines for fast access.

Common Pitfalls

#1 Ignoring collisions and overwriting data.

Wrong approach:

func (h *HashMap) Put(key string, value int) {
index := h.hash(key)
h.buckets[index] = []Pair{{key, value}} // overwrites existing bucket
}

Correct approach:

func (h *HashMap) Put(key string, value int) {
index := h.hash(key)
bucket := h.buckets[index]
for i, pair := range bucket {
if pair.key == key {
bucket[i].value = value
return
}
}
h.buckets[index] = append(bucket, Pair{key, value})
}

Root cause:

Misunderstanding that buckets can hold multiple pairs and collisions must be handled.

#2 Not resizing the HashMap when it gets full.

Wrong approach:

func (h *HashMap) Put(key string, value int) {
index := h.hash(key)
h.buckets[index] = append(h.buckets[index], Pair{key, value})
// no resizing logic
}

Correct approach:

func (h *HashMap) Put(key string, value int) {
if float64(h.size)/float64(len(h.buckets)) > 0.75 {
h.resize()
}
index := h.hash(key)
bucket := h.buckets[index]
for i, pair := range bucket {
if pair.key == key {
bucket[i].value = value
return
}
}
h.buckets[index] = append(bucket, Pair{key, value})
h.size++
}

Root cause:

Not knowing that performance degrades without resizing as load factor grows.

#3 Using a poor hash function causing many collisions.

Wrong approach:

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

Correct approach:

func (h *HashMap) hash(key string) int {
hash := 5381
for _, c := range key {
hash = ((hash << 5) + hash) + int(c) // djb2 algorithm
}
return hash % len(h.buckets)
}

Root cause:

Using naive hash functions that do not distribute keys well.

Key Takeaways

HashMaps store data as key-value pairs using a hash function to find storage locations quickly.

Collisions happen when different keys map to the same spot; handling them properly is essential for correctness.

Resizing the HashMap keeps operations fast as data grows but comes with a performance cost.

Choosing a good hash function greatly affects the efficiency of the HashMap.

Advanced collision handling and tuning make HashMaps powerful tools in real-world systems.

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