Hash Table Concept and Hash Functions in DSA Rust - 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 hash table, which helps you store and find books fast using a special code called a hash.

🎯 Goal: You will create a simple hash table using a Rust Vec to store book titles. You will write a hash function to convert book titles into numbers that tell you where to store each book in the table.

📋 What You'll Learn

Create a vector called hash_table with 10 empty slots (each slot is an empty vector of strings).

Create a hash function called simple_hash that takes a string and returns a number between 0 and 9.

Use the hash function to find the correct slot for a book title and add the title to that slot.

Print the entire hash table to see where each book is stored.

💡 Why This Matters

🌍 Real World

Hash tables are used in many applications like databases, caches, and programming language implementations to quickly find data by keys.

💼 Career

Understanding hash tables and hash functions is important for software developers, especially those working with data storage, retrieval, and optimization.

1

Create the hash table structure

Create a variable called hash_table that is a Vec with 10 empty Vec<String> slots.

DSA Rust

# Create the hash_table with 10 empty vectors
# Your code here

Hint

Use vec![Vec::new(); 10] to create 10 empty vectors inside the main vector.

2

Write the hash function

Write a function called simple_hash that takes a &str called key and returns a usize. The function should add the ASCII values of all characters in key and return the sum modulo 10.

DSA Rust

fn main() {
    let mut hash_table: Vec> = vec![Vec::new(); 10];
}

// Write the simple_hash function below
// Your code here

Hint

Loop over each character in the string, convert it to a number, add it to a sum, then use % 10 to keep the result between 0 and 9.

3

Add book titles to the hash table

Inside main, create a vector called books with these exact titles: "Rust Book", "Data Structures", "Algorithms". Use a for loop with variable book to iterate over books. For each book, find the index by calling simple_hash(book) and push the book.to_string() into hash_table[index].

DSA Rust

fn main() {
    let mut hash_table: Vec> = vec![Vec::new(); 10];
    // Create the books vector
    // Your code here

    // Add each book to the hash_table using simple_hash
    // Your code here
}

fn simple_hash(key: &str) -> usize {
    let mut sum = 0;
    for c in key.chars() {
        sum += c as usize;
    }
    sum % 10
}

Hint

Use vec![...] to create the books list. Then loop over it, get the index from simple_hash, and push the book string into the correct slot.

4

Print the hash table

Add a for loop with variables index and slot using hash_table.iter().enumerate(). Inside the loop, print the index and the slot vector using println!("Slot {}: {:?}", index, slot).

DSA Rust

fn main() {
    let mut hash_table: Vec> = vec![Vec::new(); 10];
    let books = vec!["Rust Book", "Data Structures", "Algorithms"];

    for book in books {
        let index = simple_hash(book);
        hash_table[index].push(book.to_string());
    }

    // Print the hash_table slots
    // Your code here
}

fn simple_hash(key: &str) -> usize {
    let mut sum = 0;
    for c in key.chars() {
        sum += c as usize;
    }
    sum % 10
}

Hint

Use enumerate() to get the index and iter() to loop over the hash_table. Print each slot with its index.

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