Hash Table Concept and Hash Functions in DSA Rust

Mental Model

A hash table stores data by turning keys into numbers to find values quickly.

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

Keys: [apple, banana, cherry]
Hash function: key -> number
Table: [0] -> null
       [1] -> null
       [2] -> null
       [3] -> null
       [4] -> null

Dry Run Walkthrough

Input: Insert keys 'apple', 'banana', 'cherry' into a hash table of size 5 using a simple hash function: sum of letters' positions mod 5.

Goal: Show how keys are placed in the table using the hash function.

Step 1: Calculate hash for 'apple' and insert at that index

[0] -> apple
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: We convert 'apple' to a number to find its place quickly.

Step 2: Calculate hash for 'banana' and insert at that index

[0] -> apple
[1] -> null
[2] -> null
[3] -> banana
[4] -> null

Why: Hash function gives a different index for 'banana' to avoid confusion.

Step 3: Calculate hash for 'cherry' and insert at that index

[0] -> apple
[1] -> null
[2] -> cherry
[3] -> banana
[4] -> null

Why: Each key gets its own spot using the hash function.

Result:

[0] -> apple
[1] -> null
[2] -> cherry
[3] -> banana
[4] -> null

Annotated Code

DSA Rust

struct HashTable {
    buckets: Vec<Option<String>>,
}

impl HashTable {
    fn new(size: usize) -> Self {
        Self {
            buckets: vec![None; size],
        }
    }

    fn hash(&self, key: &str) -> usize {
        // Simple hash: sum of letters' positions mod buckets size
        let sum = key.chars().map(|c| (c as u8 - b'a' + 1) as usize).sum::<usize>();
        sum % self.buckets.len()
    }

    fn insert(&mut self, key: String) {
        let index = self.hash(&key); // get index to place key
        self.buckets[index] = Some(key); // place key in bucket
    }

    fn print(&self) {
        for (i, bucket) in self.buckets.iter().enumerate() {
            match bucket {
                Some(key) => println!("[{}] -> {}", i, key),
                None => println!("[{}] -> null", i),
            }
        }
    }
}

fn main() {
    let mut table = HashTable::new(5);
    table.insert("apple".to_string());
    table.insert("banana".to_string());
    table.insert("cherry".to_string());
    table.print();
}

let sum = key.chars().map(|c| (c as u8 - b'a' + 1) as usize).sum::<usize>();

Calculate numeric value of key by summing letter positions

sum % self.buckets.len()

Use modulo to fit sum into bucket index range

let index = self.hash(&key);

Find bucket index for key

self.buckets[index] = Some(key);

Insert key into calculated bucket

Output

[0] -> apple

[1] -> null

[2] -> cherry

[3] -> banana

[4] -> null

Complexity Analysis

Time: O(1) average because hash function directly computes index without scanning all keys

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

vs Alternative: Compared to searching a list (O(n)), hash tables give faster lookups by using direct indexing

Edge Cases

Inserting keys that hash to the same index (collision)

Current code overwrites existing key; real hash tables use collision handling

DSA Rust

self.buckets[index] = Some(key);

Empty key string

Hash function returns 0, key stored at index 0

DSA Rust

let sum = key.chars().map(|c| (c as u8 - b'a' + 1) as usize).sum::<usize>();

When to Use This Pattern

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

Common Mistakes

Mistake: Not using modulo to keep hash index within bucket range
Fix: Always apply modulo with bucket size to hash value

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

Summary

Stores data by converting keys to indexes for quick access

Use when you want fast search, insert, and delete by key

The key insight is turning keys into numbers to jump directly to data

Practice

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

easy

A. To sort the keys in ascending order

B. To convert a key into an index for storing values

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: Identify the correct purpose

   This index helps to quickly find where the value related to the key is stored.

3. Final Answer:

   To convert a key into an index for storing values -> Option B

4. Quick Check:

   Hash function = key to index [OK]

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

Common Mistakes:

• Thinking hash functions sort keys
• Confusing hashing with encryption
• Believing hash functions count elements

2. Which of the following is the correct way to declare a hash map in Rust?

easy

A. let mut map = HashMap::new();

B. let map = new HashMap();

C. HashMap map = new HashMap();

D. var map = HashMap();

Solution

1. Step 1: Recall Rust syntax for hash maps

   In Rust, hash maps are created using HashMap::new() and usually declared mutable with let mut.

2. Step 2: Check each option

   let mut map = HashMap::new(); uses correct Rust syntax. Options A, B, and C use syntax from other languages or incorrect Rust syntax.

3. Final Answer:

   let mut map = HashMap::new(); -> Option A

4. Quick Check:

   Rust hash map creation = let mut map = HashMap::new() [OK]

Hint: Rust uses HashMap::new() with let mut [OK]

Common Mistakes:

• Using syntax from other languages like Java or JavaScript
• Forgetting to make the map mutable
• Missing the HashMap:: prefix

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

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple", 3);
    map.insert("banana", 2);
    map.insert("apple", 5);
    println!("{:?}", map.get("apple"));
}

medium

A. Error: duplicate key

B. Some(3)

C. None

D. Some(5)

Solution

1. Step 1: Understand insert behavior in HashMap

   In Rust's HashMap, inserting a value with an existing key replaces the old value.

2. Step 2: Trace the inserts and get

   First insert: "apple" -> 3, second insert: "banana" -> 2, third insert: "apple" -> 5 replaces 3. So map.get("apple") returns Some(5).

3. Final Answer:

   Some(5) -> Option D

4. Quick Check:

   Last insert replaces value = Some(5) [OK]

Hint: Last insert with same key overwrites value [OK]

Common Mistakes:

• Assuming duplicate keys cause error
• Thinking old value remains after insert
• Expecting None for existing key

4. Identify the error in this Rust code snippet using a hash map:

use std::collections::HashMap;

fn main() {
    let map = HashMap::new();
    map.insert("key", 10);
    println!("{:?}", map.get("key"));
}

medium

A. HashMap is not imported

B. get method does not exist

C. map is immutable but insert is called

D. Missing semicolon after insert

Solution

1. Step 1: Check mutability of map

   The map is declared with let (immutable) but insert tries to modify it.

2. Step 2: Identify the error cause

   In Rust, to modify a HashMap, it must be declared mutable with let mut.

3. Final Answer:

   map is immutable but insert is called -> Option C

4. Quick Check:

   Insert needs mutable map [OK]

Hint: Use let mut for hash maps you modify [OK]

Common Mistakes:

• Forgetting to import HashMap
• Assuming get method is missing
• Thinking semicolon is missing

5. You want to create a hash function for strings that sums the ASCII values of characters and then takes modulo with table size. Which of these Rust functions correctly implements this?

hard

A. fn hash(key: &str, size: usize) -> usize { key.bytes().map(|b| b as usize).sum::<usize>() % size }

B. fn hash(key: &str, size: usize) -> usize { key.len() % size }

C. fn hash(key: &str, size: usize) -> usize { key.chars().count() % size }

D. fn hash(key: &str, size: usize) -> usize { key.as_bytes().len() % size }

Solution

1. Step 1: Understand the required hash function

   The function must sum ASCII values of all characters and then take modulo with size.

2. Step 2: Analyze each option

   fn hash(key: &str, size: usize) -> usize { key.bytes().map(|b| b as usize).sum::<usize>() % size } sums bytes (ASCII values) and mods by size correctly. Options A, B, and D only use length or count, not sum of ASCII values.

3. Final Answer:

   fn hash(key: &str, size: usize) -> usize { key.bytes().map(|b| b as usize).sum::<usize>() % size } -> Option A

4. Quick Check:

   Sum ASCII bytes then mod size = fn hash(key: &str, size: usize) -> usize { key.bytes().map(|b| b as usize).sum::<usize>() % size } [OK]

Hint: Sum bytes, then modulo table size for hash [OK]

Common Mistakes:

• Using length instead of sum of ASCII values
• Using chars count instead of bytes
• Forgetting to modulo by table size