哈希表基础

哈希表解决什么问题？

• 目标: 建立 key 到 value 的映射;
• 能力: 以 O(1) 时间完成查找、插入和删除;
• 对比: 数组按索引访问也是 O(1), 但索引必须是整数且连续, 无法直接表示任意 key;

哈希表的各项操作复杂度是多少？

操作	时间复杂度
查找	O(1)
插入	O(1)
删除	O(1)

• 前提: 哈希函数分布均匀, 且冲突控制在可接受范围;
• 退化: 冲突集中时, O(1) 会退化, 见 哈希冲突;

哈希函数如何把 key 映射到数组下标？

• 桶: 数组的每一个空位, 一个桶存一个键值对;
• 哈希函数: 把较大的输入空间映射到较小的输出空间;
• 哈希计算: 先用哈希函数得到哈希值, 再对数组长度取模;

index = hash(key) % capacity

• 结果: key 落到 [0, capacity) 范围内的某个桶上;

为什么要对数组长度取模？

• 哈希值范围: 远大于数组长度, 不能直接作为下标;
• 取模: 把任意哈希值压缩到数组长度范围内;
• 代价: 压缩把不同的哈希值折到同一个下标, 引入哈希冲突;