数组和哈希表是两种最基础但性能特征截然不同的数据结构。理解它们的差异，能帮助你在实际开发中做出正确的选型决策。
一、核心性能指标对比
1.1 查找/访问性能
数组：按索引访问的时间复杂度为 O(1)，这是数组最核心的优势。因为数组元素在内存中连续存储，通过寻址公式 base_address + index × element_size 可以直接计算出任意元素的内存地址，无论数组多大，访问速度都是恒定的。但注意，如果是按值查找（比如查找数组中是否存在某个数值），则需要遍历数组，时间复杂度为 O(n)；如果数组是有序的，可以用二分查找降为 O(log n)。
哈希表：按键查找的平均时间复杂度也是 O(1)，这是哈希表的核心价值。通过哈希函数将任意类型的键映射到数组索引位置，实现近乎一次定位的查找速度。但在最坏情况下（所有元素哈希到同一个位置，产生严重冲突），查找时间可能退化到 O(n)。
1.2 插入和删除性能
数组：插入和删除操作需要移动大量元素以维持内存连续性。在中间位置插入时，后续所有元素都要后移；在头部插入则需要全部移动。平均时间复杂度为 O(n)。不过有一个优化技巧：如果数组是无序的，可以将目标位置的元素移到末尾，直接把新元素插入目标位置，这样插入复杂度可以降为 O(1)。
哈希表：平均情况下插入和删除的时间复杂度为 O(1)。但在最坏情况下（哈希冲突严重）也会退化为 O(n)。哈希表的插入过程包括：计算哈希值、定位桶位置、处理冲突（链地址法或开放寻址法），如果负载因子过高还需要扩容（rehashing），此时所有元素需要重新哈希，开销较大。
1.3 内存与空间复杂度
数组：空间复杂度为 O(n)，且因为连续存储没有额外指针开销，内存利用率高，对CPU缓存友好（局部性原理）。但数组大小固定，扩容时需要重新分配更大的内存块并复制所有元素。
哈希表：空间复杂度也为 O(n)，但实际内存开销更大，需要额外的桶数组空间和冲突处理结构（如链表节点指针）。哈希表的装载因子（load factor）通常在0.6~0.75之间，意味着有相当比例的空间是预留的，以维持O(1)的平均性能。
二、关键差异对比表
对比维度 | 数组 | 哈希表 |
按索引/键访问 | O(1) （按索引） | O(1) 平均（按键） |
按值查找 | O(n)，有序时可O(log n) | O(1) 平均 |
插入（中间） | O(n) （需移动元素） | O(1) 平均 |
删除（中间） | O(n) （需移动元素） | O(1) 平均 |
最坏情况性能 | 稳定（无退化风险） | 可能退化为O(n) （冲突严重时） |
内存开销 | 低（连续存储，无额外指针） | 高（预留空间+指针+冲突处理结构） |
有序性 | 天然有序 （按索引顺序） | 无序（按哈希分布） |
扩容成本 | 高（重新分配+复制全部元素） | 有（rehashing，但平均摊还较低） |
三、各场景下的性能差异详解
3.1 缓存友好性
数组的连续内存特性使其对CPU缓存极为友好。当访问 arr 时，CPU会将该元素及其相邻元素一起加载到缓存行中，后续对 arr[i+1] 的访问极大概率命中缓存。而哈希表由于节点分散存储（尤其是链地址法），容易产生缓存未命中（cache miss），导致性能下降。
正如微软的性能优化指南所指出的：使用动态分配链表的哈希表，在某些情况下，简单的线性数组搜索甚至可能更快。这是因为指针追逐（pointer chasing）会破坏局部性，导致大量缓存未命中。
3.2 最坏情况下的性能表现
这是数组和哈希表最显著的区别之一：
数组的性能是确定且稳定的，按索引访问永远是O(1)，不存在退化风险。
哈希表的性能依赖于哈希函数的质量和数据的分布。当哈希函数设计不佳或恶意攻击者构造哈希冲突的数据时，查找时间可能退化为O(n)。
3.3 扩容代价
数组需要扩容时（如Java的ArrayList），需要申请更大的连续内存空间并复制所有元素，时间复杂度为 O(n)。哈希表也需要rehashing，但由于每次扩容时元素数量增加一倍，平均每个元素的扩容成本是O(1)（摊还分析），但单次扩容的延迟较高。
四、选型建议
4.1 什么时候用数组？
键是连续的整数：比如存储一个月每天的温度，用 double[31] 就比哈希表高效得多
顺序很重要：你需要按插入顺序遍历，或者按索引范围访问（如取前10个元素）
内存敏感：在嵌入式设备或内存受限的场景下，数组的内存开销更低
对最坏情况性能有要求：实时系统中不能接受性能抖动，需要稳定可预测的访问时间
大量基础类型数据：如传感器数据、统计数值，数组的连续存储更高效
4.2 什么时候用哈希表？
键是非整数或非连续：按字符串、对象等任意类型键查找时，哈希表是首选
需要快速键值查找：如缓存系统、字典、频率统计，平均O(1)的查找速度是杀手级特性
数据量动态变化：哈希表可以较优雅地扩容，而数组扩容成本高
需要快速插入和删除：尤其是当你不需要考虑顺序时，哈希表的插入删除效率远高于数组
4.3 核心选型口诀
按索引查找用数组，按键查找用哈希表；顺序遍历用数组，快速查询用哈希表；内存敏感用数组，动态数据用哈希表；最坏情况要稳定用数组，平均性能要极致用哈希表。
五、总结
数组和哈希表不是谁绝对优于谁的关系，它们各自有适用场景：
数组是“确定性”的王者：性能稳定、内存高效、缓存友好，但灵活性不足
哈希表是“灵活性”的典范：键值映射方便、平均性能优异，但存在退化风险和额外内存开销
在实际项目中，你需要根据数据特征、访问模式、性能要求、内存限制等多个维度综合评估。正如微软的建议：没有一种方法适用于所有场景，尝试多种方案并测量差异才是最佳实践。
下一主题
