Hash Table Concept and Hash Functions in DSA Go - Execution Trace

Concept Flow - Hash Table Concept and Hash Functions

Input: Key

→Apply Hash Function

↓

If Bucket Empty?

Yes→Insert Key-Value Pair

No↓

Handle Collision (e.g., chaining)

→Insert Key-Value Pair in Bucket

↓

Done

The hash table uses a hash function to convert a key into an index. It then stores or retrieves the value at that index, handling collisions if needed.

Execution Sample

DSA Go

hash := func(key string) int {
    sum := 0
    for _, ch := range key {
        sum += int(ch)
    }
    return sum % 5
}

index := hash("cat")

This code calculates a simple hash index for the key "cat" by summing ASCII values and taking modulo 5.

Execution Table

Step	Operation	Key	Sum of ASCII	Hash Code (Index)	Bucket State	Visual State
1	Start hashing	c	99			[ ] [ ] [ ] [ ] [ ]
2	Add ASCII of 'a'	a	99 + 97 = 196			[ ] [ ] [ ] [ ] [ ]
3	Add ASCII of 't'	t	196 + 116 = 312			[ ] [ ] [ ] [ ] [ ]
4	Calculate index		312	312 % 5 = 2		[ ] [ ] [ ] [ ] [ ]
5	Insert key-value pair	cat			Bucket 2: [cat]	[ ] [ ] [cat] [ ] [ ]
6	Insert another key 'dog'	dog	100+111+103=314	314 % 5 = 4	Bucket 4: [dog]	[ ] [ ] [cat] [ ] [dog]
7	Insert key 'bat' causing collision	bat	98+97+116=311	311 % 5 = 1	Bucket 1: [bat]	[ ] [bat] [cat] [ ] [dog]
8	Insert key 'rat' causing collision with 'cat'	rat	114+97+116=327	327 % 5 = 2	Bucket 2: [cat, rat]	[ ] [bat] [cat -> rat] [ ] [dog]
9	End of insertions					[ ] [bat] [cat -> rat] [ ] [dog]

💡 All keys inserted; collisions handled by chaining in buckets.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
sum	0	312	312	312	314	311	327	327
hash_code			2	2	4	1	2	2
buckets	[ ] [ ] [ ] [ ] [ ]	[ ] [ ] [ ] [ ] [ ]	[ ] [ ] [ ] [ ] [ ]	[ ] [ ] [cat] [ ] [ ]	[ ] [ ] [cat] [ ] [dog]	[ ] [bat] [cat] [ ] [dog]	[ ] [bat] [cat -> rat] [ ] [dog]	[ ] [bat] [cat -> rat] [ ] [dog]

Key Moments - 3 Insights

Why do keys 'cat' and 'rat' end up in the same bucket?

Because their hash codes both equal 2 (see execution_table steps 4 and 8), so they map to the same bucket index, causing a collision handled by chaining.

What happens if two keys have the same hash code?

They are stored in the same bucket as a list (chaining). For example, 'cat' and 'rat' are both in bucket 2 (execution_table step 8).

Why do we use modulo operation in the hash function?

Modulo limits the hash code to the number of buckets (5 here), ensuring the index fits within the table size (see execution_table step 4).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the hash code for key 'cat'?

A 4

B 2

C 3

D 1

💡 Hint

Check the 'Hash Code (Index)' column at step 4 in execution_table.

At which step does the bucket 2 first contain more than one key?

A Step 5

B Step 7

C Step 8

D Step 6

💡 Hint

Look at the 'Bucket State' column for bucket 2 in execution_table rows.

If the hash function changed to modulo 3 instead of 5, where would key 'dog' be placed?

A Bucket 2

B Bucket 1

C Bucket 0

D Bucket 4

💡 Hint

Calculate 314 % 3 and check bucket index.

Concept Snapshot

Hash Table stores key-value pairs using a hash function.
Hash function converts keys to bucket indices.
Collisions handled by chaining (linked list in bucket).
Modulo operation limits index to bucket count.
Fast average lookup, insert, delete operations.

Full Transcript

A hash table uses a hash function to convert a key into an index where the value is stored. The hash function sums ASCII values of characters in the key and uses modulo to fit the index within the bucket array size. When two keys produce the same index, a collision occurs, handled by storing multiple key-value pairs in the same bucket using chaining. This allows fast insertion and lookup by directly accessing the bucket via the hash code.

Practice

1. What is the main purpose of a hash function in a hash table?

easy

A. To convert a key into an index for storing data

B. To sort the keys in ascending order

C. To encrypt the data stored in the table

D. To count the number of elements in the table

Solution

1. Step 1: Understand the role of a hash function

   A hash function takes a key and converts it into a number that can be used as an index in the hash table.

2. Step 2: Compare with other options

   Sorting keys, encrypting data, or counting elements are not the main roles of a hash function in a hash table.

3. Final Answer:

   To convert a key into an index for storing data -> Option A

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash function maps keys to indexes quickly [OK]

Common Mistakes:

• Thinking hash function sorts keys
• Confusing hash function with encryption
• Assuming hash function counts elements

2. Which of the following is the correct way to declare and initialize a map[string]int in Go?

easy

A. var m map[string]int

B. m := make(map[string]int)

C. var m = map[int]string{}

D. map m = make(map[string]int)

Solution

1. Step 1: Review Go syntax for map creation

   In Go, the idiomatic way to create a map is using the short declaration with make, like m := make(map[string]int).

2. Step 2: Check other options for correctness

   A declares a nil map without initialization. B uses incorrect types (map[int]string). D is invalid syntax (missing var or :=).

3. Final Answer:

   m := make(map[string]int) -> Option B

4. Quick Check:

   Use make with := for maps in Go [OK]

Hint: Use m := make(map[keyType]valueType) in Go [OK]

Common Mistakes:

• Using var without make correctly
• Incorrect map literal syntax
• Wrong variable declaration order

3. What will be the output of the following Go code?

package main
import "fmt"
func main() {
  m := make(map[string]int)
  m["apple"] = 5
  m["banana"] = 3
  fmt.Println(m["apple"] + m["banana"])
}

medium

A. 0

B. 53

C. 8

D. Compilation error

Solution

1. Step 1: Understand map assignments

   The map m stores integer values for keys "apple" and "banana" as 5 and 3 respectively.

2. Step 2: Calculate the sum printed

   m["apple"] + m["banana"] equals 5 + 3 which is 8.

3. Final Answer:

   8 -> Option C

4. Quick Check:

   5 + 3 = 8 [OK]

Hint: Sum values by accessing keys directly [OK]

Common Mistakes:

• Concatenating numbers as strings
• Assuming default zero for missing keys
• Expecting syntax errors

4. Identify the error in the following Go code that uses a hash map:

package main
import "fmt"
func main() {
  var m map[string]int
  m["key"] = 10
  fmt.Println(m["key"])
}

medium

A. Missing import for map package

B. Key "key" is invalid syntax

C. fmt.Println cannot print map values

D. Map m is declared but not initialized before assignment

Solution

1. Step 1: Check map declaration and initialization

   The map m is declared but not initialized with make, so it is nil and cannot be assigned to.

2. Step 2: Understand runtime error cause

   Assigning m["key"] = 10 on a nil map causes a runtime panic.

3. Final Answer:

   Map m is declared but not initialized before assignment -> Option D

4. Quick Check:

   Maps must be initialized with make before use [OK]

Hint: Always initialize maps with make before adding keys [OK]

Common Mistakes:

• Forgetting to initialize map
• Thinking map keys need special syntax
• Assuming fmt.Println can't print map values

5. You want to store user IDs (integers) mapped to usernames (strings) in Go. Which hash function property is most important to minimize collisions when keys are integers?

hard

A. The hash function should distribute keys uniformly across the table

B. The hash function should always return zero for simplicity

C. The hash function should sort keys before hashing

D. The hash function should convert integers to strings

Solution

1. Step 1: Understand collision in hash tables

   Collisions happen when different keys map to the same index. Minimizing collisions improves performance.

2. Step 2: Identify the best hash function property

   A good hash function distributes keys uniformly to reduce collisions. Returning zero or sorting keys does not help. Converting integers to strings is unnecessary.

3. Final Answer:

   The hash function should distribute keys uniformly across the table -> Option A

4. Quick Check:

   Uniform distribution reduces collisions [OK]

Hint: Uniform key spread reduces collisions in hash tables [OK]

Common Mistakes:

• Choosing constant hash values
• Sorting keys before hashing
• Unnecessary type conversions