Rust中线性Vec搜索与HashMap查找的性能对比

在键值对场景中，HashMap的O(1)平均查找复杂度看起来是最优选择，但哈希计算、哈希冲突处理以及哈希表的缓存不命中开销，会让它在某些场景下输给Vec的线性搜索。以下是具体的适用场景：

• 数据量极小的场景
  当键值对数量在几十甚至更少（比如10-20个以内）时，线性遍历的总耗时会低于哈希计算+哈希表寻址的开销。比如只有5个元素的集合，线性搜索只需要最多5次简单比较，而HashMap要先计算键的哈希值，再定位哈希桶，还要处理可能的冲突，这些步骤的总开销反而更高。

• 键的哈希计算成本极高
  如果键是长字符串、大型二进制数据或者复杂结构体，计算哈希需要遍历大量数据，此时哈希计算的开销会远超过线性搜索的比较成本。比如一个10KB的文本字符串作为键，计算哈希要遍历整个字符串，而线性搜索可能只需要比较前几个字符就能区分不同键，整体耗时更短。

• 键的比较成本极低
  当键是整数、短枚举值这类可以用单周期指令完成比较的类型时，线性搜索的比较操作几乎没有额外开销。相比之下，哪怕是整数哈希也需要一定的计算（比如避免哈希冲突的扰动函数），再加上哈希表的缓存不命中问题，小数据量下Vec的线性搜索会更快。

• 需要频繁遍历全量数据的场景
  Vec的内存是连续存储的，缓存命中率远高于HashMap（HashMap的元素分散在不同的哈希桶中，缓存行利用率低）。如果你的业务需要频繁遍历所有键值对做匹配或处理，Vec的连续内存带来的缓存优势会让线性遍历的速度远超HashMap的遍历操作。

• 内存受限的嵌入式/资源紧张环境
  HashMap需要额外内存存储哈希桶结构、冲突链表或红黑树，内存占用比紧凑存储的Vec高很多。在内存有限的场景中，Vec不仅内存占用更小，连续内存的缓存友好性也会让线性搜索的实际运行速度比HashMap更快。

• 临时小数据集的一次性查询
  对于临时生成、用完即弃的小数据集（比如函数内部临时存储几个配置项），Vec的插入（尾部追加）成本远低于HashMap的插入（哈希计算+冲突处理），加上后续的线性搜索开销，整体的性能表现会优于HashMap。

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