Hash Table Concept and Hash Functions in DSA Go

Mental Model

A hash table stores data by turning keys into numbers to find spots quickly. This lets us find things fast without checking everything.

Analogy: Imagine a library where each book has a special code that tells you exactly which shelf and spot it belongs to, so you don't have to look through all shelves to find it.

Index: 0   1   2   3   4   5   6   7
Table: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Key: "cat" -> hash -> 0 -> store at index 0
Key: "dog" -> hash -> 2 -> store at index 2

Dry Run Walkthrough

Input: Insert keys "cat", "dog", "bird" into a hash table of size 8 using a simple hash function

Goal: Show how keys are converted to indexes and stored in the table

Step 1: Calculate hash for "cat" and insert at index

Index: 0   1   2   3   4   5   6   7
Table: [cat] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Why: We convert "cat" to a number and use modulo 8 to find index 0

Step 2: Calculate hash for "dog" and insert at index

Index: 0   1   2   3   4   5   6   7
Table: [cat] [ ] [dog] [ ] [ ] [ ] [ ] [ ]

Why: We convert "dog" to a number and use modulo 8 to find index 2

Step 3: Calculate hash for "bird" and insert at index

Index: 0   1   2   3   4   5   6   7
Table: [cat] [bird] [dog] [ ] [ ] [ ] [ ] [ ]

Why: We convert "bird" to a number and use modulo 8 to find index 1

Result:

Index: 0   1   2   3   4   5   6   7
Table: [cat] [bird] [dog] [ ] [ ] [ ] [ ] [ ]

Annotated Code

DSA Go

package main

import (
	"fmt"
)

// HashTable holds the table and size
type HashTable struct {
	table []string
	size  int
}

// NewHashTable creates a new hash table
func NewHashTable(size int) *HashTable {
	return &HashTable{
		table: make([]string, size),
		size:  size,
	}
}

// simpleHash converts a string key to an index
func (h *HashTable) simpleHash(key string) int {
	sum := 0
	for _, ch := range key {
		sum += int(ch) // add ASCII values
	}
	return sum % h.size // modulo table size
}

// Insert adds a key to the hash table
func (h *HashTable) Insert(key string) {
	index := h.simpleHash(key) // get index from hash
	h.table[index] = key       // store key at index
}

// PrintTable shows the current table
func (h *HashTable) PrintTable() {
	for i, val := range h.table {
		if val == "" {
			fmt.Printf("[%d]: empty\n", i)
		} else {
			fmt.Printf("[%d]: %s\n", i, val)
		}
	}
}

func main() {
	h := NewHashTable(8)
	h.Insert("cat")
	h.Insert("dog")
	h.Insert("bird")
	h.PrintTable()
}

sum += int(ch) // add ASCII values

Calculate sum of character codes to create a number from the key

return sum % h.size // modulo table size

Use modulo to fit the number into the table size as index

index := h.simpleHash(key) // get index from hash

Find the index where the key should be stored

h.table[index] = key // store key at index

Place the key in the table at the calculated index

Output

[0]: cat

[1]: bird

[2]: dog

[3]: empty

[4]: empty

[5]: empty

[6]: empty

[7]: empty

Complexity Analysis

Time: O(1) average because hashing lets us jump directly to the index without searching

Space: O(n) because we store n keys in the table array

vs Alternative: Compared to searching a list (O(n)), hash tables give faster average lookup by using hashing

Edge Cases

Empty key string

Hash function returns 0 index, key stored at index 0

DSA Go

return sum % h.size // modulo table size

Keys that hash to same index (collision)

Current code overwrites existing key at index, no collision handling

DSA Go

h.table[index] = key       // store key at index

Table size zero or negative

Program may panic or behave unexpectedly, no guard in code

DSA Go

return sum % h.size // modulo table size

When to Use This Pattern

When you need very fast lookup by key and can convert keys to numbers, use a hash table with a hash function to jump directly to storage spots.

Common Mistakes

Mistake: Not using modulo to keep index inside table size
Fix: Always use modulo operation on hash value to get valid index

Mistake: Ignoring collisions causing overwrites
Fix: Implement collision handling like chaining or open addressing

Summary

Stores keys by converting them to numbers to find spots quickly.

Use when you want fast access by key without searching all data.

The key insight is turning keys into table indexes using a hash function.

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