面试题：Rust 集合迭代器模式之自定义迭代器与优化

Question

自定义一个实现 `Iterator` 特质的结构体，该结构体用于生成斐波那契数列。数列从 0 和 1 开始，每次生成下一个数是前两个数之和。同时，在使用这个自定义迭代器对一个 `HashMap<String, i32>` 进行遍历，当遇到 `i32` 值等于当前斐波那契数时，将对应的 `String` 键收集到一个 `HashSet<String>` 中并返回。请详细写出 Rust 代码，并说明在实现过程中如何考虑性能优化，比如减少不必要的内存分配等。

Answer 1

use std::collections::{HashMap, HashSet};

// 自定义斐波那契数列迭代器
struct FibonacciIterator {
    a: i32,
    b: i32,
}

impl FibonacciIterator {
    fn new() -> Self {
        FibonacciIterator { a: 0, b: 1 }
    }
}

impl Iterator for FibonacciIterator {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        let result = self.a;
        self.a = self.b;
        self.b = result + self.a;
        Some(result)
    }
}

fn collect_keys_with_fibonacci_value(hashmap: &HashMap<String, i32>) -> HashSet<String> {
    let mut fibonacci_iter = FibonacciIterator::new();
    let mut result = HashSet::new();

    for (key, value) in hashmap {
        let fibonacci_num = fibonacci_iter.next().unwrap();
        if *value == fibonacci_num {
            result.insert(key.clone());
        }
    }

    result
}

性能优化说明

1. 斐波那契数列迭代器：
   • 使用结构体 FibonacciIterator 实现 Iterator 特质，在 next 方法中通过简单的变量交换和加法运算生成下一个斐波那契数，避免了复杂的递归调用，从而减少了栈空间的使用和函数调用开销。
2. 遍历 HashMap 并收集键：
   • 在 collect_keys_with_fibonacci_value 函数中，直接在 for 循环中获取下一个斐波那契数并与 HashMap 中的值进行比较，避免了预先生成大量斐波那契数占用内存。
   • 使用 HashSet 来收集符合条件的键，HashSet 的插入操作平均时间复杂度为 O(1)，相比于其他集合类型，如 Vec，在查找和插入操作上更高效，减少了整体的时间复杂度。同时，HashSet 不会存储重复的键，符合题目要求且避免了不必要的重复存储。