在引入哈希表之前先要介绍哈希函数。哈希函数是哈希表的核心它决定了数据如何映射到存储位置。哈希函数哈希函数的作用是把一个原始数据key映射为一个下标索引即H(key) - 下标最常用的构造方法是除留余数法H(key) key mod M其中 M 为哈希表的长度通常取质数原因是减少数据集聚降低冲突概率若M为合数很容易出现大量key和M有公因数导致哈希结果只落在少数几个桶bucket里。。例如 M 13 时H(27) 27 mod 13 1即 27 存放在下标 1 的位置。哈希函数设计需要满足几点要求计算简单能在常数时间内算出下标否则失去哈希的意义。分布均匀让键尽可能均匀地散落到各个下标上减少冲突。结果稳定同一个 key 每次计算必须得到相同的下标。由于不同的 key 可能映射到同一个下标这种现象称为哈希冲突碰撞。常见的解决方法有链地址法拉链法每个下标挂一条链表冲突的元素依次存入。优点不容易堆积删除方便好写代码缺点需要额外占用一点内存开放定址法开放寻址Open Addressing数组里找空位无链表冲突时按某种规则线性探测、二次探测、再哈希寻找下一个空位。以最常用的线性探测Linear Probing为例线性探测是开放寻址法中最简单的一种冲突解决策略。核心规则一句话位置被占了就往后一个一个找直到找到空位。探测公式令表长M为7输入数据10, 17, 8, 15计算10 % 7 3 → 下标3空位直接放17 % 7 3 → 下标3被占i1(31)%74 → 下标4放178 % 7 1 → 下标1空位直接放15 % 7 1 → 下标1被占i1(11)%72 → 下标2放15下标 0 1 2 3 4 5 6┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │ 空 │ 8 │ 15 │ 10 │ 17 │ 空 │ 空 │ └─────┴─────┴─────┴─────┴─────┴─────┴─────┘优点只用数组不需要列表缺点容易集聚大量元素在一块查找变慢删除麻烦不能直接删要标记二次探测Quadratic Probing当哈希函数计算出的位置已经被占用发生冲突时二次探测不是像线性探测那样逐个向后查找而是按照二次方的步长跳跃式地寻找下一个空槽。公式如下最常见的简化形式举个例子设表长M9设key25H(25)25 mod 97若下标7已经被占则第一次探测(31^2)mod 94第二次探测(32^2)mod 90第三次探测33^2)mod 93…依次尝试桶403…再哈希Rehashing是哈希表在运行过程中扩容并重新分布所有元素的机制通常设定一个负载因子的阈值如 α≥0.5、0.7或 0.75α 越过阈值时触发再哈希。此外墓碑DELETED 标记过多时也常触发再哈希因为墓碑会拖慢查找、浪费空间再哈希可以顺带清理它们过程为分配新表申请一个更大的槽位数组通常是原大小的 2 倍左右或下一个质数。重新计算位置遍历旧表中的所有有效元素用新的表大小重新计算每个键的哈希位置插入新表。释放旧表迁移完成后释放旧数组替换哈希表内部指针。哈希表哈希表Hash Table也叫散列表是基于哈希函数实现的一种数据结构它通过哈希函数映射把查找、插入、删除的平均时间复杂度降到O(1)。哈希表的底层是数组数组里的每一个位置就是一个桶。数组下标0,1,2........ 下标对应的那一块位置就是桶 比如M7那么就是有7个桶桶0到桶6对于不同的哈希方案里桶里装的东西也不一样拉链法链地址法里面放链表头指针比如桶1和桶3中都挂了一个链表每个桶中所有元素都串在这个链表中开放定址法线性探测每个桶里最多放一个key满了就去别的桶找空位。哈希表的基本结构可以理解为下标 0 - [ ] 下标 1 - [key1, value1] - [key3, value3] 下标 2 - [ ] 下标 3 - [key2, value2] ...哈希表的性能取决于哈希函数的质量和负载因子负载因子元素数 / 桶数越大冲突越多性能越差过小则浪费空间。负载因子表中已存在元素个数/哈希表长度M负载因子越大表示表装的约满冲突概率越大一般控制负载因子小于0.75超过就扩容。同时只有使用链表法时负载因子可以大于1哈希函数分布越均匀链表越短查询越接近 O(1)。最坏情况下所有 key 冲突到同一桶退化为 O(n)。总结来说哈希函数负责「把 key 变成下标」哈希表负责「按下标存取数据」二者配合实现了高效的键值查找。注墓碑tombstone也叫 DELETED 标记是开放寻址法哈希表中处理删除的一种机制。它本质上是给槽位打的一个特殊状态标记表示这里曾经有元素、现在已被删除但探测链不能在这里中断。查找逻辑遇到 OCCUPIED键匹配则返回否则继续遇到 DELETED继续探测不终止遇到 EMPTY才终止返回不存在时间复杂度衡量算法运行时间随数据量变大时增长的趋势其中O1是最理想的On是最差的
