哈希表概念
哈希表是一种基于数组 + 哈希函数实现的数据结构，用于快速存储和查找数据。它的核心思想是：
通过 key 来快速找到对应的 value。
查找操作在理想情况下可以达到O(1)的时间复杂度。
哈希表也叫散列表，核心组成部分包括：
哈希函数 (Hash Function)
将 key 映射成数组的索引 (0 到 N-1)
公式：
index=hash(key)%table_size
数组
存放数据的容器，每个索引称为一个桶。
冲突解决策略
不同 key 可能映射到相同的索引 →哈希冲突
常见策略：
拉链法：每个桶用链表存储所有冲突元素
开放地址法：冲突元素在表内寻找下一个空位置（线性探测、二次探测、双重哈希）
哈希函数设计
哈希函数决定了哈希表性能的好坏。设计原则：
均匀分布：尽量让 key 均匀分布到各个桶
高效：计算要快，避免性能瓶颈
确定性：相同 key 必须映射到相同位置
常见哈希函数：
整型 key：直接取模
int hash(int key) { return key % table_size; }字符串 key：常用多项式滚动哈希
hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] index = hash % table_size;冲突解决策略详解
拉链法
每个桶存储一个链表或其他数据结构（如平衡树）。
插入时将元素加入链表尾部或头部。
查找时在链表中遍历。
优点：实现简单，删除方便。
缺点：最坏情况退化为链表，查找 O(n)。
开放地址法
所有元素存储在数组中，不用链表。
冲突时通过探测找到下一个空槽。
常用探测策略：
线性探测
index = (hash(key) + i) % table_size
i = 0,1,2,...
二次探测
index = (hash(key) + i^2) % table_size
哈希表操作复杂度
| 操作 | 理想情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 插入 | O(1) | O(1) | O(n) |
| 查找 | O(1) | O(1) | O(n) |
| 删除 | O(1) | O(1) | O(n) |
哈希表的应用场景
字典/映射结构：C++unordered_map、JavaHashMap
去重：用 Set 保存唯一值计数统计：频率统计问题
缓存实现：如 LRU Cache 的快速访问
查找优化：通过 key 快速查找复杂对象
