Hash Map vs Array vs Linked List for Lookup in DSA Rust - Trade-offs & Analysis

Mental Model

Lookup means finding a value quickly by its key or position. Different structures store data differently, so lookup speed changes.

Analogy: Imagine finding a book in a library: an array is like books on a shelf in order, a linked list is like books in a chain where you check one by one, and a hash map is like a librarian who knows exactly where each book is.

Array: [0]1 -> [1]2 -> [2]3 -> null
Linked List: 1 -> 2 -> 3 -> null
Hash Map: {key1: val1, key2: val2, key3: val3}

Dry Run Walkthrough

Input: Lookup value 3 in: Array [1, 2, 3], Linked List 1->2->3, Hash Map {1: 'a', 2: 'b', 3: 'c'}

Goal: Show how each structure finds the value 3 or its associated data

Step 1: Check array index 0 for value 3

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

Why: Start at first position to find value 3

Step 2: Check array index 1 for value 3

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

Why: Value not found yet, move to next index

Step 3: Check array index 2 for value 3

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

Why: Found value 3 at index 2

Step 4: Start at linked list head node with value 1

1 -> 2 -> 3 -> null ↑

Why: Linked list lookup starts at head

Step 5: Move to next node with value 2

1 -> 2 -> 3 -> null ↑

Why: Value 3 not found, move forward

Step 6: Move to next node with value 3

1 -> 2 -> [3] -> null

Why: Found value 3 in linked list

Step 7: Use hash function on key 3 to find bucket

{1: 'a', 2: 'b', 3: 'c'}

Why: Hash map uses key to jump directly to value

Step 8: Retrieve value 'c' for key 3

{1: 'a', 2: 'b', 3: 'c'}

Why: Found value quickly without scanning

Result:

Array final: [0]1 -> [1]2 -> [2][3] -> null
Linked List final: 1 -> 2 -> [3] -> null
Hash Map final: {1: 'a', 2: 'b', 3: 'c'} with key 3 -> 'c'

Annotated Code

DSA Rust

use std::collections::HashMap;

// Node for linked list
struct Node {
    val: i32,
    next: Option<Box<Node>>,
}

impl Node {
    fn new(val: i32) -> Self {
        Node { val, next: None }
    }
}

// Linked list lookup function
fn linked_list_lookup(head: &Option<Box<Node>>, target: i32) -> bool {
    let mut current = head;
    while let Some(node) = current {
        if node.val == target {
            return true; // found value
        }
        current = &node.next; // move to next node
    }
    false // not found
}

fn main() {
    // Array lookup
    let arr = [1, 2, 3];
    let target = 3;
    let mut found_in_array = false;
    for &val in arr.iter() {
        if val == target {
            found_in_array = true;
            break; // stop when found
        }
    }

    // Linked list setup: 1 -> 2 -> 3
    let node3 = Box::new(Node::new(3));
    let mut node2 = Box::new(Node::new(2));
    node2.next = Some(node3);
    let mut node1 = Box::new(Node::new(1));
    node1.next = Some(node2);
    let head = Some(node1);

    let found_in_list = linked_list_lookup(&head, target);

    // Hash map lookup
    let mut map = HashMap::new();
    map.insert(1, 'a');
    map.insert(2, 'b');
    map.insert(3, 'c');
    let found_in_map = map.get(&target);

    // Print results
    println!("Array contains {}: {}", target, found_in_array);
    println!("Linked list contains {}: {}", target, found_in_list);
    match found_in_map {
        Some(&ch) => println!("Hash map key {} maps to value '{}': true", target, ch),
        None => println!("Hash map key {} not found: false", target),
    }
}

for &val in arr.iter() { if val == target { found_in_array = true; break; } }

scan array elements until target found or end reached

while let Some(node) = current { if node.val == target { return true; } current = &node.next; }

traverse linked list nodes checking each value

let found_in_map = map.get(&target);

directly access hash map value by key

Output

Array contains 3: true

Linked list contains 3: true

Hash map key 3 maps to value 'c': true

Complexity Analysis

Time: Array: O(n) because we may check each element; Linked List: O(n) for same reason; Hash Map: O(1) average because hashing jumps directly to value

Space: Array: O(n) to store elements; Linked List: O(n) with extra pointers; Hash Map: O(n) with extra space for buckets and pointers

vs Alternative: Hash map lookup is faster than array or linked list because it avoids scanning; arrays are faster than linked lists for lookup due to direct indexing

Edge Cases

Empty array, linked list, or hash map

Lookup returns false or None since no elements exist

DSA Rust

while let Some(node) = current {

Target value not present

Lookup scans entire array or list and returns false; hash map returns None

DSA Rust

if val == target { found_in_array = true; break; }

Single element structures

Lookup checks only one element and returns true if matches

DSA Rust

if node.val == target { return true; }

When to Use This Pattern

When a problem asks for fast lookup by key or index, consider hash maps for O(1) average time, arrays for direct index access, and linked lists when insertion order matters but lookup is slower.

Common Mistakes

Mistake: Using linked list for frequent lookups expecting fast access
Fix: Use hash map or array instead for faster lookup

Mistake: Assuming array lookup by value is O(1)
Fix: Remember array lookup by value is O(n), only index access is O(1)

Summary

Compares how hash maps, arrays, and linked lists find values by key or position.

Use hash maps for fastest key-based lookup, arrays for index-based lookup, and linked lists when order and easy insertion matter more than speed.

Hash maps jump directly to values using keys, arrays use positions, and linked lists scan nodes one by one.

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