Hash Table Concept and Hash Functions in DSA Go - Build from Scratch

Hash Table Concept and Hash Functions

📖 Scenario: Imagine you are organizing a small library. You want to quickly find books by their titles. To do this, you decide to use a simple hash table where each book title is linked to its shelf number.

🎯 Goal: You will create a hash table using a Go map, write a simple hash function to convert book titles into shelf numbers, and then store and retrieve books using this hash function.

📋 What You'll Learn

Create a map called library to store book titles as keys and shelf numbers as values

Create a hash function called simpleHash that takes a string and returns an integer

Use the simpleHash function to assign shelf numbers to books

Print the library map to show the stored books and their shelf numbers

💡 Why This Matters

🌍 Real World

Hash tables help quickly find data like books in a library or contacts in a phone.

💼 Career

Understanding hash tables and hash functions is important for software developers working with fast data lookup and storage.

1

Create the library map

Create a map called library that stores strings as keys and integers as values. Add these exact books with their shelf numbers: "Go Programming": 0, "Data Structures": 0, "Algorithms": 0.

DSA Go

library := map[string]int{"Go Programming": 0, "Data Structures": 0, "Algorithms": 0}
// Your code here

Hint

Use map[string]int to create the map and add the books with shelf number 0 for now.

2

Create the simple hash function

Create a function called simpleHash that takes a string parameter key and returns an integer. The function should sum the ASCII values of all characters in key and return the sum modulo 10.

DSA Go

package main

import "fmt"

func main() {
    library := map[string]int{"Go Programming": 0, "Data Structures": 0, "Algorithms": 0}
}

func simpleHash(key string) int {
    // Your code here
}

Hint

Use a for loop to go through each character in the string and add its integer value to sum. Then return sum % 10.

3

Assign shelf numbers using the hash function

Use a for loop with variable title to iterate over library. For each title, update its shelf number in library by calling simpleHash(title).

DSA Go

package main

import "fmt"

func main() {
    library := map[string]int{"Go Programming": 0, "Data Structures": 0, "Algorithms": 0}
    // Your code here
}

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

Hint

Use for title := range library to loop over keys and update each value with simpleHash(title).

4

Print the library map

Write fmt.Println(library) to print the library map showing book titles and their assigned shelf numbers.

DSA Go

package main

import "fmt"

func main() {
    library := map[string]int{"Go Programming": 0, "Data Structures": 0, "Algorithms": 0}
    for title := range library {
        library[title] = simpleHash(title)
    }
    // Print the library map
    // Your code here
}

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

Hint

Use fmt.Println(library) to display the map.

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