目录一、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树的区别附.