面试题：Rust HashMap遍历与高效访问的结合

Question

假设你有一个`HashMap<String, Vec<i32>>`，需要遍历这个HashMap，并且在遍历过程中高效地访问每个`Vec<i32>`中的元素并进行求和操作，写出实现代码，并解释为什么这种方式能保证高效访问。

Answer 1

以下是Rust代码实现：

use std::collections::HashMap;

fn main() {
    let mut map: HashMap<String, Vec<i32>> = HashMap::new();
    map.insert("key1".to_string(), vec![1, 2, 3]);
    map.insert("key2".to_string(), vec![4, 5, 6]);

    for (_, values) in map.iter() {
        let sum: i32 = values.iter().sum();
        println!("Sum for values: {}", sum);
    }
}

这种方式能保证高效访问的原因：

1. HashMap的遍历：HashMap的iter方法可以高效地遍历其键值对。HashMap内部使用哈希表结构存储数据，平均情况下，遍历操作的时间复杂度接近O(n)，其中n是HashMap中元素的数量。
2. Vec的遍历：Vec是连续存储的数组，其iter方法同样高效。连续存储使得在内存中访问元素时可以通过简单的指针偏移直接定位到下一个元素，这在现代CPU缓存机制下能有效减少内存访问延迟。遍历Vec的时间复杂度也是接近O(m)，其中m是Vec中元素的数量。
3. 求和操作：sum方法是基于迭代器的，在迭代过程中直接累加元素值，避免了额外的中间数据结构，进一步提高了效率。