目录
- 一、hash查询的核心流程
- 二、哈希表的两个核心设计
- 三、装填因子
- 四、静态哈希表
- 1. 线性探测
- 2. Robin Hood哈希
- 3. Cuckoo 哈希
- 五、动态哈希表
- 1. 链式哈希
- 2. 可扩展哈希
- 3. 线性哈希
- 六、几种方法的比较
- 七、哈希表与B+树的区别
一.hash查询的核心流程
键(key)通过哈希函数计算得到哈希值,然后哈希值通过取模运算映射为具体的桶O(1),然后进行桶内查找找到对应的数据
1.哈希值:哈希值就是把任意长度的数据通过哈希函数计算后得到的固定长度的输出
2.桶:桶就是哈希表中的一个槽位
桶的本质
二.哈希表的两个核心设计
1.哈希函数:负责把任意长度的键转换为整数
好的哈希函数的特点:计算速度快;输出分布均匀;尽量减少冲突;相似输入也可以产生差异较大的结果
2.哈希方案:哈希值最终要映射到有限的槽位,而不同的键可能映射到相同的位置
三.装填因子
装填因子 α = n / m，其中：
n：表中已有的元素总数量
m：哈希表的总长度
影响：
装填因子越大，发生冲突的可能性越高。
装填因子越小，发生冲突的可能性越低，但空间利用率也越低。
四.静态哈希表
1.线性探测
当发生冲突时，依次探测下一个位置（通常为 H(key)+1, H(key)+2, ...），直到找到空闲位置为止。若探测到表尾，则从表首继续探测（循环探测）。
查询也遵循相同过程：
- 计算理想位置。
- 从该位置向后检查。
- 找到目标键则成功。
- 遇到真正的空槽则说明不存在。
删除问题:不能简单把被删除的位置变为空槽,应该设置删除墓碑
缺点:线性探测容易产生连续占用区域,称为聚集,聚集区越长,查询和探测的次数就越多
2.Robin Hood哈希
它会记录每一个元素距离其理想距离有多远:探测位置 = 当前位置 - 理想位置
插入时，如果新元素的探测距离比当前位置元素更大，就交换二者：
距离远的元素获得当前位置
距离近的元素继续向后寻找
3.Cuckoo 哈希
Cuckoo Hashing 为一个键准备多个候选位置，通常使用多个哈希函数：
位置1 = h1(key) 位置2 = h2(key)如果两个位置都被占用：
- 把其中一个旧元素踢出去。
- 新元素占据该位置。
- 被踢出的元素前往自己的另一个候选位置。
- 重复这一过程。
例:
新键 X 想进入 A 的位置 X 踢走 A A 前往自己的另一个位置 A 又可能踢走 B五,动态哈希表
1.链式哈希
Chained Hashing 的每个槽位不只存一个元素，而是指向一个数据集合：
优点：
实现简单
容量可以动态增长
装载因子可以大于1
删除操作比较自然
缺点：
可能产生很长的冲突链
指针和额外桶需要更多空间
随机内存访问对缓存不友好
2.可扩展哈希
Extendible Hashing 使用：
一个目录 Directory:也可说为指针
多个桶 Bucket
全局深度 Global Depth:决定目录使用哈希值的多少位;若为2,则表示使用2个2进制位,目录有2的平方个入口
局部深度 Local Depth:
表示某个桶当前依赖多少个哈希位,多个目录项可以指向同一个桶，因此局部深度可能小于全局深度。
桶满:“桶满”就是指：这个桶里存放的数据条目已经达到了它预设的物理容量上限，再也塞不进新数据了,若桶满了,怎么处理
(1)局部深度小于全局深度
分裂这个桶；
增加它的局部深度；
调整部分目录指针。
(2)局部深度等于全局深度
将目录扩大一倍；
全局深度加1；
分裂溢出的桶；
重新分配桶中的元素。
3.线性哈希
Linear Hashing 不使用可扩展哈希中的显式目录。
它维护：
当前哈希层级；
一个分裂指针；
两组不同范围的哈希函数。
例:
h₀(key) = hash(key) mod N h₁(key) = hash(key) mod 2N桶按照固定次序逐个分裂,每次分裂：
- 分裂指针指向一个旧桶；
- 创建一个新桶；
- 使用更高层哈希函数重新分配该桶的数据；
- 分裂指针前进一步；
- 一轮分裂完成后进入下一个层级。
优点：
- 不需要大型目录
- 渐进式扩容
- 避免一次性重建整张表
缺点：
- 查询逻辑比普通哈希复杂
- 在扩张期间，不同桶可能使用不同层级的哈希函数
- 可能需要临时溢出页
六.几种方法的比较
七.哈希表与B+树的区别
附.