Hash Table Concept and Hash Functions in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a hash table (map) in Go that maps strings to integers.

DSA Go

var scores [1]

Drag options to blanks, or click blank then click option'

Astruct{}

B[]int

Cmap[string]int

Dmap[int]string

Attempts:

3 left

💡 Hint

Common Mistakes

Using slice syntax instead of map

Swapping key and value types

Using struct{} which is an empty struct, not a map

In Go, a hash table is called a map. The syntax map[string]int means keys are strings and values are integers.

2fill in blank

medium

Complete the code to insert a key-value pair into the hash table.

DSA Go

scores["Alice"] = [1]

Drag options to blanks, or click blank then click option'

A"Alice"

B100

Cscores

Dmap[string]int{}

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning a string key as value

Assigning the whole map as value

Using incorrect syntax for assignment

To insert a value into a map, assign the value to the key. Here, 100 is the value for key "Alice".

3fill in blank

hard

Fix the error in the hash function that returns the index for a given key.

DSA Go

func hash(key string, size int) int {
    var sum int
    for _, char := range key {
        sum += int(char)
    }
    return sum [1] size
}

Drag options to blanks, or click blank then click option'

A%

B*

C/

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of modulo

Using division which can cause out of range index

Adding size which increases the index

The hash function should use the modulo operator (%) to ensure the index fits within the table size.

4fill in blank

hard

Fill both blanks to complete the function that checks if a key exists in the hash table.

DSA Go

func exists(table map[string]int, key string) bool {
    _, [1] := table[key]
    return [2]
}

Drag options to blanks, or click blank then click option'

Afound

Bvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using the value instead of the boolean found

Using different variable names for the two blanks

Ignoring the second return value

In Go, when accessing a map, the second returned value indicates if the key exists. We store it in a variable (commonly named found) and return it.

5fill in blank

hard

Fill all three blanks to complete the function that deletes a key from the hash table if it exists.

DSA Go

func deleteKey(table map[string]int, key string) {
    _, [1] := table[key]
    if [2] {
        [3](table, key)
    }
}

Drag options to blanks, or click blank then click option'

Afound

Cdelete

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using a wrong function name like remove

Not checking if the key exists before deleting

Using different variable names inconsistently

The second value from map access is stored in 'found'. If found is true, we use the built-in delete function to remove the key.

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