文章目录1. 已经有搜索树了为什么还需要哈希表2. 哈希函数怎样选择负载因子又说明什么2.1 整数可以取模其他键先产生哈希值2.2 负载因子衡量拥挤程度3. 线性探测位置被占后按同一条路径继续找4. 删除的难点空位置为什么还要分两种4.1 直接清空会切断查找路径4.2 墓碑能复用但不能让重复键混进来5. 扩容改变了位置规则必须重新安置元素6. 链地址法让同一个桶里的元素连起来7. 复杂度什么时候是 O(1)什么时候会慢下来8. 总结1. 已经有搜索树了为什么还需要哈希表红黑树能把查找控制在 O(log N)同时保留键之间的大小关系。但如果需求只是“给定学号找成绩”“给定单词统计次数”我们并不需要每次都沿着大小关系寻找。回想数组知道下标便能直接访问对应位置。如果键本身就能告诉我们该去哪里就可能省掉逐层比较。假设只统计小写英文字母count[ch - a]就把字符映射到 025。这里要求输入确实属于az对于任意字符直接这样访问会有越界风险。这种直接定址适合键的范围小且集中一个位置对应一个可能的键。但只有一千名学生学号却可能跨越数亿个整数时按学号开数组就很浪费。我们希望只开有限的位置再把大范围的键映射进去。这就是哈希表的出发点。通常可以把定位过程拆成两步键 key ──Hash(key)── 无符号整数哈希值 ──% M── 初始位置 / 桶下标M是当前槽位数或桶数必须大于 0。哈希值不是数组下标只有经过范围压缩才能作为当前表的下标。不同键定位到同一位置称为哈希冲突。键的可能取值远多于位置时不可能让所有不同键都占有独立位置。所以哈希表必须同时解决两个问题尽量分散数据以及发生冲突后仍能正确找到数据。因此查找的完整思路是用哈希确定查找范围再比较键来确认目标。2. 哈希函数怎样选择负载因子又说明什么2.1 整数可以取模其他键先产生哈希值对于非负整数key % M很直观。但在 C 中-1 % 11是-1不能把这个有符号结果直接当数组下标。字符串也不能直接当作整数% M但可以让每个字节参与累积最终仍然形成一个无符号正整数。structStringHash{std::size_toperator()(conststd::stringkey)const{std::size_t value0;for(unsignedcharch:key)valuevalue*131ch;returnvalue;}};以常见字符编码中的ab为例先得到 97再得到97 * 131 98 12805。ba的结果是98 * 131 97 12935。与简单相加相比字符的位置参与了运算因而这两个字符串不再必然冲突。std::size_t是无符号整数算术超出范围时按无符号规则回绕不是有符号溢出。无论选哪种算法必须满足如果两次比较认为键相等它们的哈希值必须相同不同键的哈希值允许相同。键存放在表内期间其哈希结果与相等判断应保持稳定。不能插入时用一种规则查找时随意换另一种。2.2 负载因子衡量拥挤程度设有效元素数为N槽位数或桶数为M负载因子 α N / M代码中若要计算小数需先转成浮点数N / M的整数除法会截断。开放定址法让元素直接占槽位因此N ≤ M。链地址法中的M是链表头指针的数量一个桶可以挂多个结点因此α可以超过 1表示每桶平均元素数不是数组占用率。3. 线性探测位置被占后按同一条路径继续找开放定址法把元素放在同一个槽位数组内。线性探测最容易理解从初始位置出发冲突就往后走一步到末尾后回到 0。初始位置 h Hash(key) % M 探测位置依次为 h, (h 1) % M, (h 2) % M, ...以这组整数键为例暂时固定M 11来观察位置变化不在图中触发自动扩容19, 30, 5, 36, 13, 20, 21, 1219 放到 830 也从 8 开始发现 19 后放到 9。20 从 9 开始绕过 30 后放到 10。21 从 10 开始被 20 挡住回到 0。12 从 1 开始恰好可直接放入。最终数组中的键为下标012345678910键21121336空5空空193020查找也必须沿相同路径前进。例如找 20从 9 出发看到 30 不相等继续到 10 才确认命中。如果查找一个不存在的键遇到从未使用过的空槽就可以停止若该键曾经沿这条路径插入就本应在遇到这个空槽时就存下来不会越过它。线性探测的代价是堆积。连续的一段槽位被占据后起点不同的键也可能汇入同一段进一步拉长连续区域。其他探测策略思路使用时的关键条件二次探测用平方相关的偏移拉开探测位置公式、容量和负载需要配合不能认定任意公式都能走遍所有槽位双重散列用另一个哈希函数决定步长步长非零且与容量互质才能遍历整张表例如容量 12、步长 3从 1 出发只能访问1 → 4 → 7 → 10 → 1其他位置再空也找不到。4. 删除的难点空位置为什么还要分两种4.1 直接清空会切断查找路径仍看上面的表。删除 30 后如果把下标 9 设成EMPTY再找 20起点就是 9程序遇到空槽立即报告不存在。实际上 20 仍在下标 10。解决方法是增加删除标记也叫墓碑状态含义查找时插入时EMPTY在本次建表或重建后从未被占用可以报告未找到可以存放EXIST当前有有效元素比较键不同就继续被占用DELETED曾经被占用现在逻辑删除必须继续探测完成查重后可以复用4.2 墓碑能复用但不能让重复键混进来删除 30 后再插入 20如果看到下标 9 是墓碑就立刻放进去表中就会出现两个 20。可用位置不等于已经证明键不存在。有两种清楚的写法一次探测中记住第一个墓碑继续查重或者先完整查重再寻找可用位置。若插入 41它和 19 一样从 8 开始。查重确认 41 不存在后可以复用下标 9 的墓碑。有效元素数加一墓碑数减一。5. 扩容改变了位置规则必须重新安置元素容量从 11 改成 2319 的初始位置从 8 变为 1930 的初始位置从 8 变为 7。只把数组扩大并保留原下标新查找却按 23 取模双方使用了不同的定位规则这就会导致前后逻辑不一样而错乱。正确步骤是申请新槽位数组遍历旧表只对EXIST元素按新容量重新定位和探测全部完成后交换新旧数组。墓碑不迁移有效元素总数不变。这个过程称为重新散列rehash。它不一定意味着扩容同容量重建也可以用来清理墓碑。开放地址法完整程序6. 链地址法让同一个桶里的元素连起来开放定址让冲突元素继续占其他槽位而链地址法则让每个桶保存一个链表头指针冲突的键都挂在同一条链上。例如容量 11 时19、30、41 都在桶 8。采用头插依次插入后链为buckets[8] → 41 → 30 → 19 → nullptr找 30 时只需遍历桶 8 的链不必去其他桶找。删除时可以真正断链并释放结点不需要墓碑因为查找结束条件是这条链走到空指针。这里要记住两个主体桶数组存的是头指针键值对存在结点里。因此数组容量和元素数量可以不同负载因子也能超过 1。扩容时无需再为每个旧元素new一次。先创建更大的空桶数组再把原结点重新链接过去就可以了。关键顺序是保存旧 next → 计算新桶下标 → 头插到新桶 → 沿保存的 next 继续旧链另一个不容易注意的问题是本次待插入元素的下标如果扩容前算过hash % 旧容量扩容后一定要重新按新容量计算不能继续使用旧下标。比如键 22 在容量 11 时定位到 0容量 23 时应定位到 22。放错桶后查找就会像这个元素不存在一样。链地址完整程序7. 复杂度什么时候是 O(1)什么时候会慢下来讨论复杂度前先假设哈希与比较键的成本是 O(1)分布较好并把负载控制在了合适范围内。操作或场景复杂度与条件链地址查找、删除均匀分布时预期 O(1 α)α 有界时通常写为平均 O(1)线性探测查找、删除分布适当且负载与墓碑受控时预期 O(1)α 接近 1 时探测成本明显上升普通插入不含重建时在上述条件下预期 O(1)扩容重建至少扫描旧表并初始化新表链地址迁移为 O(M旧 M新 N)不计复杂类型的操作成本开放定址重建包含扫描、初始化和重新探测良好分布时约 O(M旧 M新 N)严重冲突时迁入过程可能 O(N²)任一表的单次查找最坏情况可退化为 O(N) 或扫描 O(M) 个槽位不能保证每次常数时间链地址中所有键都进入一个桶时链就退化成线性查找。开放定址中连续占用区域很长时查找也可能检查很多槽位。在分布良好、容量按几何方式增长等条件下扩容总成本可分摊到多次插入插入通常称为均摊预期 O(1)。空间上开放定址需要 O(M) 个槽位本实现每个槽位都构造键值对象链地址需要 O(M N) 空间还多出每个结点的指针、缓存值和单独分配成本。开放定址连续访问通常有较好的局部性链地址修改链接和保留结点地址更方便。红黑树则提供 O(log N) 的查找上界和有序遍历。需要范围查询、有序输出时树结构的能力仍有价值只是按键定位、去重、计数时哈希容器通常会更贴近需求。8. 总结哈希表核心思想通过哈希函数将 key 映射到数组下标实现快速访问时间特性平均期望 O (1)极端哈希冲突下最坏退化为 O (N)两种实现链地址法桶内挂链表负载因子 α 可大于 1删除简单缓存局部性差开放寻址法线性探测等元素直接存入槽位α 一般控制在 0.7 左右空间局部性好负载高时探测成本飙升扩容容量几何倍增扩容代价分摊到多次插入插入操作均摊 O (1)扩容需要重哈希迁移全部元素对比红黑树哈希表无序适合单点查找、去重计数红黑树稳定 O (logN)支持有序遍历与范围查询