Hash Map vs Array vs Linked List for Lookup in DSA Rust - Visual Comparison

Concept Flow - Hash Map vs Array vs Linked List for Lookup

Start Lookup

↓

Choose Data Structure

↓

Array

↓

Index Access

↓

Compare Key

↓

Return Value

↓

End Lookup

Lookup starts by choosing the data structure, then uses index access for arrays, node traversal for linked lists, or hash computation for hash maps to find the value.

Execution Sample

DSA Rust

use std::collections::LinkedList;
use std::collections::HashMap;

let arr = [10, 20, 30];
let list: LinkedList<i32> = [10, 20, 30].into_iter().collect();
let mut map = HashMap::new();
map.insert("a", 10);
map.insert("b", 20);
map.insert("c", 30);

// Lookup 20 in each

This code sets up an array, linked list, and hash map, then looks up the value 20 in each.

Execution Table

Step	Data Structure	Operation	Details	Result	Visual State
1	Array	Index Access	Access index 1	Found 20	[10, 20, 30]
2	Linked List	Traverse Nodes	Check node 10 (no match)	Continue	(10) -> (20) -> (30) -> null
3	Linked List	Traverse Nodes	Check node 20 (match)	Found 20	(10) -> (20) -> (30) -> null
4	Hash Map	Compute Hash	Hash key 'b'	Bucket found	{"a":10, "b":20, "c":30}
5	Hash Map	Lookup Bucket	Check bucket for key 'b'	Found 20	{"a":10, "b":20, "c":30}
6	End	Lookup Complete	All structures searched	Value 20 found in all	Array: [10,20,30], List: (10)->(20)->(30), Map: {a:10,b:20,c:30}

💡 Lookup ends after value 20 is found in all data structures.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Array Index	N/A	1	1	1	1	1	1
Linked List Current Node	Head (10)	10	20	20	20	20	20
Hash Map Key	N/A	N/A	N/A	N/A	'b'	'b'	'b'
Hash Map Bucket	N/A	N/A	N/A	N/A	Bucket for 'b'	Bucket for 'b'	Bucket for 'b'

Key Moments - 3 Insights

Why does array lookup find the value immediately at index 1?

Because arrays allow direct access by index, as shown in execution_table step 1 where index 1 is accessed directly without traversal.

Why does linked list lookup require checking nodes one by one?

Linked lists store elements in nodes linked by pointers, so we must traverse nodes sequentially until the value is found, as seen in steps 2 and 3.

How does the hash map find the value so quickly?

Hash maps compute a hash of the key to find the correct bucket directly, avoiding traversal, as shown in steps 4 and 5.

Visual Quiz - 3 Questions

Look at the execution_table, at which step does the linked list find the value 20?

A Step 2

B Step 4

C Step 3

D Step 1

💡 Hint

Check the 'Result' column for linked list operations in execution_table rows 2 and 3.

According to variable_tracker, what is the 'Array Index' value after step 1?

A 1

B 2

C 0

D N/A

💡 Hint

Look at the 'Array Index' row under 'After Step 1' in variable_tracker.

If the hash map key was changed to 'a', which step in execution_table would change?

A Step 5

B Step 4

C Step 2

D Step 1

💡 Hint

Step 4 shows hash computation for the key; changing the key changes this step.

Concept Snapshot

Lookup in Array: direct index access, O(1) time
Lookup in Linked List: sequential traversal, O(n) time
Lookup in Hash Map: hash computation + bucket access, average O(1)
Arrays are fast but fixed size
Linked Lists allow dynamic size but slower lookup
Hash Maps offer fast lookup with key hashing

Full Transcript

This visual execution compares lookup operations in three data structures: array, linked list, and hash map. Lookup in an array accesses the element directly by index, shown in step 1. Linked list lookup traverses nodes one by one until the value is found, shown in steps 2 and 3. Hash map lookup computes a hash of the key to find the bucket directly, shown in steps 4 and 5. Variable tracking shows how pointers and indices change during lookup. Key moments clarify why arrays are fast for lookup, linked lists require traversal, and hash maps use hashing for quick access. The quiz tests understanding of these steps and variable states. The snapshot summarizes lookup time complexities and characteristics of each data structure.

Practice

1. Which data structure provides the fastest average lookup time for a key-value pair in Rust?

easy

A. Array

B. Vector

C. Linked List

D. Hash Map

Solution

1. Step 1: Understand lookup times for data structures

   Hash Map uses hashing to find keys quickly, usually in constant time O(1).

2. Step 2: Compare with Array and Linked List

   Array and Linked List require searching elements linearly, which is slower (O(n)).

3. Final Answer:

   Hash Map -> Option D

4. Quick Check:

   Fastest lookup = Hash Map [OK]

Hint: Hash Map uses hashing for O(1) lookup, arrays and lists are slower [OK]

Common Mistakes:

• Thinking arrays have O(1) lookup for keys (only for indices)
• Confusing linked list traversal with direct access
• Assuming vector is same as hash map for lookup

2. Which Rust syntax correctly declares a mutable HashMap named map with String keys and i32 values?

easy

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

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

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

D. let map = HashMap::new();

Solution

1. Step 1: Check correct syntax for mutable HashMap declaration

   In Rust, let mut declares a mutable variable. The type is HashMap<String, i32>. The constructor is HashMap::new().

2. Step 2: Identify errors in other options

   let map = HashMap::new(); misses mut. let mut map = HashMap::new(); has wrong generic syntax. let map: HashMap = HashMap::new(); swaps key and value types.

3. Final Answer:

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

4. Quick Check:

   Mutable HashMap syntax = let mut map: HashMap = HashMap::new(); [OK]

Hint: Use let mut with HashMap::new() and correct generics [OK]

Common Mistakes:

• Forgetting mut keyword for mutable map
• Wrong generic syntax with new()
• Swapping key and value types

3. What is the output of this Rust code snippet?

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple", 3);
    map.insert("banana", 2);
    map.insert("orange", 5);

    let lookup = map.get("banana");
    println!("{:?}", lookup);
}

medium

A. None

B. 2

C. Some(2)

D. banana

Solution

1. Step 1: Understand HashMap get method return type

   The get method returns an Option type: Some(&value) if key exists, else None.

2. Step 2: Check if key "banana" exists and its value

   Key "banana" exists with value 2, so get("banana") returns Some(&2). Printing with {:?} shows Some(2).

3. Final Answer:

   Some(2) -> Option C

4. Quick Check:

   HashMap get returns Option = Some(2) [OK]

Hint: HashMap get returns Option; Some(value) if found, else None [OK]

Common Mistakes:

• Expecting direct value instead of Option
• Confusing None with Some
• Printing key instead of value

4. Identify the error in this Rust code that tries to find a value in a linked list:

struct Node {
    value: i32,
    next: Option,
}

fn find(head: &Option, target: i32) -> bool {
    let mut current = head;
    while current.is_some() {
        if current.as_ref().unwrap().value == target {
            return true;
        }
        current = current.unwrap().next;
    }
    false
}

medium

A. Using unwrap() twice causes ownership error

B. Missing mutable keyword for current

C. Incorrect comparison operator in if statement

D. next field should be a reference, not Box

Solution

1. Step 1: Analyze ownership in while loop

   Calling unwrap() on current moves ownership, so current cannot be used again.

2. Step 2: Identify why unwrap() causes error

   Using unwrap() twice consumes current, causing ownership error. Instead, use references or pattern matching.

3. Final Answer:

   Using unwrap() twice causes ownership error -> Option A

4. Quick Check:

   Ownership error due to unwrap() usage [OK]

Hint: unwrap() moves ownership; use references to avoid errors [OK]

Common Mistakes:

• Ignoring ownership rules with unwrap()
• Thinking mutable needed for current here
• Confusing Box with reference types

5. You need to store a large collection of user IDs (integers) and quickly check if a user ID exists. Which data structure is best and why? Choose the best option considering lookup speed and memory efficiency.

hard

A. Hash Map, because it offers average constant time lookup for keys

B. Array, because it provides constant time lookup for any integer key

C. Linked List, because it uses less memory and is easy to implement

D. Vector, because it automatically resizes and supports fast lookup

Solution

1. Step 1: Consider lookup speed for large collections

   Linked List has O(n) lookup, which is slow. Array lookup by index is O(1), but only if keys are indices, not arbitrary integers.

2. Step 2: Evaluate Hash Map and Vector

   Hash Map provides average O(1) lookup for arbitrary keys like user IDs. Vector lookup by index is O(1), but user IDs may not be continuous indices.

3. Final Answer:

   Hash Map, because it offers average constant time lookup for keys -> Option A

4. Quick Check:

   Best lookup for arbitrary keys = Hash Map [OK]

Hint: Use Hash Map for fast lookup of arbitrary keys like user IDs [OK]

Common Mistakes:

• Assuming array lookup works for arbitrary keys
• Choosing linked list for speed
• Confusing vector with hash map for key lookup