Rust实现无重复最长子串时HashMap为何比String.find性能差

核心原因分析 #

• 短字符串下线性遍历开销远低于哈希表固定开销
  你的暴力双循环实现中，每次内层循环遍历的无重复子串长度通常很短，尤其是测试用例包含大量短无重复子串场景时，String.find的线性遍历只需要几次比较就能出结果。而HashMap的查找需要先对字符做哈希计算、处理可能的哈希冲突、再访问散列存储的内存，固定开销远高于几次简单的CPU比较，反而会更慢。
• 缓存命中率差距大
  String存储是连续的内存块，find操作访问的是连续地址，CPU缓存命中率极高。而HashMap是散列存储，数据分散在不同内存地址，缓存命中率很低，频繁访问的开销会被放大。
• HashMap实现存在冗余操作
  你只需要判断字符是否存在，不需要存储字符对应的索引，完全可以用HashSet替代HashMap减少存储开销，但就算换用HashSet也解决不了哈希计算的固定开销问题。同时你每次外层循环都要清空HashMap，频繁的修改操作也会带来额外性能损耗。
• Rust标准库的str::find做了高度优化
  对于ASCII占比高的测试用例，find会直接走SIMD优化的快速匹配逻辑，性能远高于普通的哈希表查找。

优化方向 #

你当前的两个实现都是O(n²)时间复杂度的暴力解法，想要大幅提升性能可以换成滑动窗口的O(n)实现：如果只处理ASCII字符可以用长度128的数组充当存在标记，完全规避哈希表开销，性能会比当前两个版本高一个数量级。
示例简化实现：

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut last_occur = [-1; 128];
        let mut left = 0;
        let mut max_len = 0;
        for (right, c) in s.bytes().enumerate() {
            let c = c as usize;
            left = left.max(last_occur[c] + 1);
            max_len = max_len.max(right as i32 - left + 1);
            last_occur[c] = right as i32;
        }
        max_len
    }
}

如果需要支持Unicode字符，可以换用非加密哈希实现的FxHashSet配合滑动窗口实现，也能大幅提升性能。

内容的提问来源于stack exchange，提问作者Sylver