哈希和数组那个速度快

补充

补充：数组 vs 哈希表的对比：

数组

  • 优点：按下标访问 O(1)；连续内存，CPU 缓存友好，遍历快；空间紧凑。
  • 缺点：按下标插入/删除 O(n)（需搬移元素）；按下标查找需要二分才 O(log n)；按内容查找 O(n)；大小固定（动态数组按倍数扩容）。

哈希表

  • 优点：按 key 增删查平均 O(1)，非常快。
  • 缺点：哈希函数开销、需要解决冲突、负载因子高时扩容；key 无序（无法直接做范围查询）；哈希分布不均时性能退化；不可遍历全部（除非另存结构）；哈希内容占用额外空间。

"哈希比数组快"的说法只在按 key 增删查的场景下成立。如果涉及范围扫描、按下标访问或遍历所有元素，连续内存的数组往往因为缓存命中率高反而更快。

来源整理自：我的有道云笔记