哈希表(Hash Table)

定义

哈希表（散列表）是一种通过哈希函数把键映射到数组下标，从而实现平均常数时间存取的键值对数据结构。它是 Java 的 HashMap、Python 的 dict 等的底层实现。

原理

哈希函数将键转换为整数下标，理想情况下不同键映射到不同位置。当两个键映射到同一位置即发生哈希冲突，常用两种解决方法：拉链法（每个槽位挂一条链表或红黑树）和开放寻址法（冲突时按探测序列找下一个空槽）。当负载因子（元素数除以桶数）过高时进行扩容并重新散列，以维持性能。

复杂度

• 查找/插入/删除（平均）：O(1)
• 查找/插入/删除（最坏，冲突严重）：O(n)
• 空间复杂度：O(n)

应用场景

• 缓存、字典、去重、计数
• 数据库索引与符号表
• 集合（Set）的实现
• 两数之和等查找类算法的加速