Hash Table Concept and Hash Functions in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Hash Function Modulo Operation

What is the output of the following Go code that simulates a simple hash function using modulo operation?

DSA Go

package main
import "fmt"
func main() {
	keys := []int{10, 22, 31, 4, 15}
	hashTableSize := 10
	for _, key := range keys {
		hash := key % hashTableSize
		fmt.Printf("Key %d hashes to index %d\n", key, hash)
	}
}

A

Key 10 hashes to index 0
Key 22 hashes to index 2
Key 31 hashes to index 1
Key 4 hashes to index 4
Key 15 hashes to index 5

B

Key 10 hashes to index 1
Key 22 hashes to index 2
Key 31 hashes to index 3
Key 4 hashes to index 4
Key 15 hashes to index 5

C

Key 10 hashes to index 0
Key 22 hashes to index 1
Key 31 hashes to index 2
Key 4 hashes to index 3
Key 15 hashes to index 4

D

Key 10 hashes to index 5
Key 22 hashes to index 2
Key 31 hashes to index 1
Key 4 hashes to index 4
Key 15 hashes to index 0

💡 Hint

Remember that modulo (%) gives the remainder after division.

Each key is divided by the hash table size (10), and the remainder is the hash index. For example, 10 % 10 = 0, 22 % 10 = 2, etc.

🧠 Conceptual

intermediate

Understanding Hash Collisions

Which of the following statements best describes a hash collision in a hash table?

A A key is not found in the hash table during search.

B Two different keys produce the same hash index in the hash table.

C The hash function returns a negative number for a key.

D The hash table is empty and has no keys stored.

💡 Hint

Think about what happens when two keys map to the same place.

A hash collision happens when two different keys get the same hash index, causing them to compete for the same slot.

🔧 Debug

advanced

Identify the Error in Hash Function Implementation

What error will occur when running this Go code that tries to compute a hash index for a string key?

DSA Go

package main
import (
	"fmt"
)
func hash(key string, size int) int {
	hashValue := 0
	for i := 0; i < len(key); i++ {
		hashValue += int(key[i])
	}
	return hashValue % size
}
func main() {
	h := hash("abc", 5)
	fmt.Println("Hash index:", h)
}

A No error; output is 'Hash index: 4'

B No error; output is 'Hash index: 1'

C No error; output is 'Hash index: 0'

D No error; output is 'Hash index: 3'

💡 Hint

Sum the ASCII values of 'a', 'b', and 'c' and then modulo by 5.

ASCII values: 'a' = 97, 'b' = 98, 'c' = 99. Sum = 294. 294 % 5 = 4. So output is 'Hash index: 4'.

🚀 Application

advanced

Choosing a Hash Table Size

Why is it recommended to choose a prime number as the size of a hash table when using modulo-based hash functions?

A Prime sizes allow storing only prime number keys efficiently.

B Prime sizes prevent the hash function from producing negative values.

C Prime sizes make the hash table faster to resize dynamically.

D Prime sizes reduce the chance of collisions by distributing keys more evenly.

💡 Hint

Think about how modulo with prime numbers affects key distribution.

Using a prime number as the table size helps spread keys more uniformly, reducing clustering and collisions.

❓ Predict Output

expert

Output of Custom Hash Function with Collision Handling

What is the printed state of the hash table after inserting keys with linear probing collision handling?

DSA Go

package main
import "fmt"
func main() {
	hashTable := make([]int, 7)
	for i := range hashTable {
		hashTable[i] = -1
	}
	keys := []int{10, 20, 15, 7}
	hash := func(key int) int {
		return key % len(hashTable)
	}
	for _, key := range keys {
		index := hash(key)
		for hashTable[index] != -1 {
			index = (index + 1) % len(hashTable)
		}
		hashTable[index] = key
	}
	for i, val := range hashTable {
		fmt.Printf("Index %d: %d\n", i, val)
	}
}

A

Index 0: 7
Index 1: 10
Index 2: 20
Index 3: 15
Index 4: -1
Index 5: -1
Index 6: -1

B

Index 0: 10
Index 1: 20
Index 2: 15
Index 3: 7
Index 4: -1
Index 5: -1
Index 6: -1

C

Index 0: 7
Index 1: 15
Index 2: -1
Index 3: 10
Index 4: -1
Index 5: -1
Index 6: 20

D

Index 0: 10
Index 1: -1
Index 2: 20
Index 3: 15
Index 4: 7
Index 5: -1
Index 6: -1

💡 Hint

Check how linear probing moves to next index when collision occurs.

Keys are inserted using linear probing (no collisions occur here): - 10 % 7 = 3 → placed at 3 - 20 % 7 = 6 → placed at 6 - 15 % 7 = 1 → placed at 1 - 7 % 7 = 0 → placed at 0 Final state: Index 0: 7, 1: 15, 2: -1, 3: 10, 4: -1, 5: -1, 6: 20. Matches option C.

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