title: “HashMap Iteration in Rust - Keys, Values, and Iterator Safety” meta_description: “Implement safe iteration for HashMap in Rust with Iter, Keys, Values, and iterator invalidation rules.” keywords: [“rust hashmap iterator”, “hashmap iteration”, “keys values iterator”, “iterator invalidation”, “hashmap iter”]

🔄 Reinventing from Scratch: Building HashMap

Chapter 5 — “Iteration and Views”

“Iterating a HashMap means visiting a sparse array while pretending it’s dense.”

🧭 5.1. The Challenge

Our HashMap has holes:

[0]: Empty
[1]: ("dog", 20)
[2]: Tombstone
[3]: ("cat", 10)
[4]: Empty
[5]: ("fox", 50)

Goal: Iterate over just the occupied entries:

for (key, value) in &map {
    println!("{} = {}", key, value);
}

// Output:
// dog = 20
// cat = 10
// fox = 50

Challenge: Skip Empty and Tombstone slots efficiently.

🎯 5.2. Basic Iterator Implementation

pub struct Iter<'a, K, V> {
    entries: &'a [Slot<K, V>],
    current: usize,
}

impl<'a, K, V> Iterator for Iter<'a, K, V> {
    type Item = (&'a K, &'a V);
    
    fn next(&mut self) -> Option<Self::Item> {
        // Skip Empty and Tombstone slots
        while self.current < self.entries.len() {
            match &self.entries[self.current] {
                Occupied(entry) => {
                    let result = (&entry.key, &entry.value);
                    self.current += 1;
                    return Some(result);
                }
                _ => {
                    self.current += 1;
                }
            }
        }
        
        None
    }
}

// Add method to MyHashMap
impl<K, V, S> MyHashMap<K, V, S> {
    pub fn iter(&self) -> Iter<K, V> {
        Iter {
            entries: &self.entries,
            current: 0,
        }
    }
}

🔓 5.3. Mutable Iterator

For &mut iteration:

pub struct IterMut<'a, K, V> {
    entries: &'a mut [Slot<K, V>],
    current: usize,
}

impl<'a, K, V> Iterator for IterMut<'a, K, V> {
    type Item = (&'a K, &'a mut V);  // Can mutate values!
    
    fn next(&mut self) -> Option<Self::Item> {
        while self.current < self.entries.len() {
            self.current += 1;
            
            // Need unsafe here to extend lifetime
            match &mut self.entries[self.current - 1] {
                Occupied(entry) => {
                    // SAFETY: We never return the same entry twice
                    // because we increment current before returning
                    let key_ref = unsafe { &*(& entry.key as *const K) };
                    let val_ref = unsafe { &mut *(&mut entry.value as *mut V) };
                    return Some((key_ref, val_ref));
                }
                _ => continue,
            }
        }
        
        None
    }
}

Why unsafe? The borrow checker can’t prove we won’t return the same entry twice, even though our logic guarantees it.

🔑 5.4. Keys-Only Iterator

Sometimes you only want keys:

pub struct Keys<'a, K, V> {
    iter: Iter<'a, K, V>,
}

impl<'a, K, V> Iterator for Keys<'a, K, V> {
    type Item = &'a K;
    
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|(k, _)| k)
    }
}

// In MyHashMap
pub fn keys(&self) -> Keys<K, V> {
    Keys { iter: self.iter() }
}

Usage:

for key in map.keys() {
    println!("{}", key);
}

💎 5.5. Values-Only Iterator

Similarly for values:

pub struct Values<'a, K, V> {
    iter: Iter<'a, K, V>,
}

impl<'a, K, V> Iterator for Values<'a, K, V> {
    type Item = &'a V;
    
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|(_, v)| v)
    }
}

pub struct ValuesMut<'a, K, V> {
    iter: IterMut<'a, K, V>,
}

impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
    type Item = &'a mut V;
    
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|(_, v)| v)
    }
}

🔥 5.6. IntoIter (Consuming Iterator)

For for (k, v) in map (consumes the map):

pub struct IntoIter<K, V> {
    entries: std::vec::IntoIter<Slot<K, V>>,
}

impl<K, V> Iterator for IntoIter<K, V> {
    type Item = (K, V);
    
    fn next(&mut self) -> Option<Self::Item> {
        for slot in &mut self.entries {
            match slot {
                Occupied(entry) => {
                    return Some((entry.key, entry.value));
                }
                _ => continue,
            }
        }
        
        None
    }
}

// Implement IntoIterator trait
impl<K, V, S> IntoIterator for MyHashMap<K, V, S> {
    type Item = (K, V);
    type IntoIter = IntoIter<K, V>;
    
    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            entries: self.entries.into_iter(),
        }
    }
}

⚠️ 5.7. Iterator Invalidation

Critical safety rule: Don’t modify HashMap while iterating!

let mut map = MyHashMap::new();
map.insert("a", 1);
map.insert("b", 2);

for (key, value) in &map {
    map.insert("c", 3);  // ❌ ERROR: Can't mutate while borrowed!
}

Rust’s borrow checker prevents this automatically — that’s why we take &self for iter().

But What About This?

for (key, value) in &mut map {
    *value += 1;  // ✅ OK: Modifying values
}

for (key, value) in &mut map {
    map.insert("new", 99);  // ❌ ERROR: Can't restructure map
}

Rule: You can modify values, but not the table structure.

📏 5.8. Iterator Efficiency

Skip Empty Slots

Our iterator scans linearly, skipping empty slots:

Entries: [_, X, _, X, _, _, X, _]
Steps:    ^  ^  ^  ^  ^  ^  ^  ^
Returned:    X     X        X

Performance: O(capacity), not O(len)!

With load factor 0.75:

• Capacity: 100
• Len: 75
• Iterator scans: ~100 slots (skips ~25 empty)

Still O(n) amortized because capacity ≈ len * 1.33.

🎨 5.9. Iteration Order

Important: HashMap iteration order is arbitrary!

map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);

for (k, v) in &map {
    // Order might be: c, a, b
    // Or: b, c, a
    // Or anything!
}

Why?

• Hash function determines order
• Rehashing changes order
• Robin Hood swaps change order

Never depend on HashMap iteration order!

🧮 5.10. Size Hints

Implement size_hint for better performance:

impl<'a, K, V> Iterator for Iter<'a, K, V> {
    type Item = (&'a K, &'a V);
    
    fn next(&mut self) -> Option<Self::Item> {
        // ... implementation ...
    }
    
    fn size_hint(&self) -> (usize, Option<usize>) {
        // We know exactly how many items remain
        let remaining = self.entries.len() - self.current;
        (0, Some(remaining))  // At most 'remaining' items
    }
}

This helps collect() pre-allocate:

let vec: Vec<_> = map.iter().collect();  // Pre-allocates right size!

🧩 5.11. Implementing IntoIterator Trait

Make our HashMap work with for loops:

// For &HashMap
impl<'a, K, V, S> IntoIterator for &'a MyHashMap<K, V, S> {
    type Item = (&'a K, &'a V);
    type IntoIter = Iter<'a, K, V>;
    
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

// For &mut HashMap
impl<'a, K, V, S> IntoIterator for &'a mut MyHashMap<K, V, S> {
    type Item = (&'a K, &'a mut V);
    type IntoIter = IterMut<'a, K, V>;
    
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

// For HashMap (consuming)
impl<K, V, S> IntoIterator for MyHashMap<K, V, S> {
    type Item = (K, V);
    type IntoIter = IntoIter<K, V>;
    
    fn into_iter(self) -> Self::IntoIter {
        self.into_iter()
    }
}

🧠 5.12. Chapter Takeaways

🚀 5.13. What’s Next

We can now iterate over our HashMap safely.

But there’s one more piece of the puzzle: Entry API.

Next chapter: The Entry API — efficient “get or insert” operations without double lookups.

💡 Exercises

1. Implement all iterators (Iter, IterMut, Keys, Values, IntoIter)
2. Add drain() that empties the map while iterating
3. Implement ExactSizeIterator when no tombstones present
4. Benchmark iteration vs Vec iteration (measure overhead)
5. Test that iterator invalidation is caught at compile time

Next: Chapter 6 — Hasher and DoS Resistance 🔐