哈希表是软件工程中使用最频繁的数据结构。理解其内部原理——哈希函数、冲突处理和扩容——将只会调API的人与真正理解数据结构的人区分开来。
解释核心思想：哈希函数将键映射到数组索引，实现平均 O(1) 访问。
讨论冲突解决：链地址法（每个桶用链表）vs 开放寻址法（线性探测、二次探测、双重散列）。
讲负载因子和动态扩容：负载因子超过阈值时，数组翻倍并重新哈希所有条目。
提到好的哈希函数特性：确定性、均匀分布、计算快速。
哈希表通过计算键的哈希值确定数组索引来存储键值对。核心操作是 index = hash(key) % array_size，平均 O(1) 访问。不同键哈希到相同索引时产生冲突。我用链地址法处理——每个桶存一个链表——或开放寻址法，探测下一个空槽。链地址法更简单且退化平缓；开放寻址法缓存性能更好但实现更复杂，尤其是删除操作。我维护负载因子（条目数/桶数），超过0.75时数组翻倍并重新哈希所有条目——这种摊销代价保持操作在 O(1)。好的哈希函数均匀分布键；字符串可用多项式滚动哈希。我的设计会用链地址法的桶数组，跟踪负载因子，0.75时扩容，并实现正确的相等性检查，因为不同对象可能有相同哈希码。
了解链地址法和开放寻址法的区别——以及各自的适用场景。
理解为什么扩容是摊销 O(1)——面试官常问此问题。
准备好讨论 Java HashMap 或 Python dict 的冲突处理机制（Java 8+ 桶大小超过8时转红黑树）。
O(n)，当所有键哈希到同一个桶时。这就是为什么均匀分布的好哈希函数至关重要。
链地址法在每个桶用链表存储冲突项。开放寻址法通过探测序列在数组中找下一个空槽。链地址法更简单，开放寻址法更缓存友好。
负载因子(n/m)衡量表的满度。高负载因子增加冲突概率，降低性能。0.75时扩容在空间和速度之间取得平衡。