Hash Table Concept and Hash Functions in DSA Rust - Execution Trace

Concept Flow - Hash Table Concept and Hash Functions

Start: Insert key-value pair

↓

Compute hash(key)

↓

Map hash to index in array

↓

Check bucket at index

↓

Insert

↓

Done

↓

Done

Shows how a key-value pair is inserted by hashing the key, mapping to an index, and handling collisions if needed.

Execution Sample

DSA Rust

let mut table = HashTable::new(5);
table.insert("cat", 10);
table.insert("dog", 20);
table.insert("act", 30);
println!("{:?}", table);

Inserts three key-value pairs into a hash table of size 5, showing how keys map to indices and how collisions are handled.

Execution Table

Step	Operation	Hash(key)	Index	Bucket State	Visual State
1	Insert ("cat", 10)	hash("cat") = 2	2	Bucket empty	[0: []] [1: []] [2: [(cat,10)]] [3: []] [4: []]
2	Insert ("dog", 20)	hash("dog") = 3	3	Bucket empty	[0: []] [1: []] [2: [(cat,10)]] [3: [(dog,20)]] [4: []]
3	Insert ("act", 30)	hash("act") = 2	2	Collision with (cat,10)	[0: []] [1: []] [2: [(cat,10), (act,30)]] [3: [(dog,20)]] [4: []]
4	Print table	-	-	-	[0: []] [1: []] [2: [(cat,10), (act,30)]] [3: [(dog,20)]] [4: []]
5	End	-	-	-	Insertion complete

💡 All keys inserted; collisions handled by chaining in bucket 2.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
table.size	5	5	5	5	5
table.buckets	[[], [], [], [], []]	[[], [], [(cat,10)], [], []]	[[], [], [(cat,10)], [(dog,20)], []]	[[], [], [(cat,10), (act,30)], [(dog,20)], []]	[[], [], [(cat,10), (act,30)], [(dog,20)], []]

Key Moments - 3 Insights

Why does "act" go to the same bucket as "cat"?

Because the hash function produces the same index (2) for both keys, causing a collision handled by chaining as shown in step 3 of the execution_table.

What happens if the bucket is empty when inserting a key?

The key-value pair is simply added to that bucket as the first element, as seen in steps 1 and 2 where buckets 2 and 3 were empty.

How does the hash function affect the index?

The hash function converts the key into a number, which is then mapped to an index within the table size by modulo operation, ensuring the index fits in the array bounds.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the bucket state at index 2?

A [(cat,10), (act,30)]

B [(dog,20)]

C []

D [(act,30)]

💡 Hint

Check the 'Bucket State' column at step 3 in the execution_table.

At which step does a collision occur during insertion?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look for 'Collision' mentioned in the 'Operation' column in the execution_table.

If the table size was increased to 10, how would the index for "cat" change?

A It would remain 2

B It would be 0

C It would be hash("cat") % 10, possibly different

D It would be 5

💡 Hint

Indexes depend on hash(key) modulo table size, see concept_flow and variable_tracker.

Concept Snapshot

Hash Table stores key-value pairs in an array.
Keys are converted to an index by a hash function.
Collisions happen when different keys map to the same index.
Chaining stores multiple pairs in a bucket list.
Insertion: hash key → find index → add to bucket.
Lookup uses the same hash to find the key quickly.

Full Transcript

A hash table stores data by converting keys into array indexes using a hash function. When inserting, the key is hashed, and the resulting number is mapped to an index in the array. If the bucket at that index is empty, the key-value pair is added directly. If not, a collision occurs, and the pair is added to a list in that bucket. This example inserts three keys: "cat", "dog", and "act". "cat" and "act" collide because their hashes map to the same index, so both are stored in the same bucket list. This method allows fast insertion and lookup by reducing search to a small bucket list instead of the whole array.

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