算法（40）：separate chaining-12.2-北京尧图网络

Page 17碰撞的现实物理事实即使哈希函数设计得再好碰撞两个不同键算出同一个索引也必然会发生。这是由生日悖论Birthday Problem决定的——当插入的元素数量超过~√(πM/2)时碰撞概率就会显著升高。挑战不能用无限大的数组来避免碰撞浪费空间也不能用线性扫描来解决浪费时间。必须设计一种高效处理碰撞的数据结构。这也引出了后续两种主流的碰撞处理方案。Page 18分离链接法的物理结构这是解决碰撞的最直接思路数组链表。物理布局创建长度为M的数组称为桶数组Bucket Array。数组中的每个槽位不再直接存储键值对而是存储一个链表的头节点指针。当两个键发生碰撞hash(key1) hash(key2)时它们会被放入同一个链表桶中。物理操作插入Insert计算哈希值i。找到第i个桶的头指针。遍历该链表。如果键已存在更新值如果不存在直接在链表头部插入新节点O(1)头插。查找Search计算哈希值i。只遍历第i个桶的链表用equals逐一比对。找到则返回找不到则返回null。内存形态存储是分散的。数组在堆上是连续的一块内存。链表节点分散在堆的其他位置通过 8 字节的next指针串联起来。Page 19-20Java 实现骨架物理代码逻辑内部类Node包含key、val、next指针和你之前学的链表栈/队列结构完全一样。put方法计算哈希定位到桶i。遍历st[i]指向的链表for (Node x st[i]; x ! null; x x.next)。如果找到匹配的key更新x.val并返回。如果遍历完链表都没找到创建一个新节点把新节点的next指向原来的头节点st[i]再把头节点指向新节点头插法。get方法同样的遍历逻辑找到则返回val找不到返回null。PPT 没有显式列出get代码但它逻辑与put的遍历部分完全一致。Page 21性能分析为什么是常数时间物理上这部分基于均匀哈希假设每个键等概率落入任一桶。在这个假设下每个桶的长度链表节点数就是N / M平均负载因子α。根据负载均衡Load Balancing理论当M个桶中投入N个球时最长的链表长度大约为Θ(log M / log log M)非常短。因此查找/插入需要遍历的节点数平均为~N/M。工程权衡如果M太大如M N大量桶为空浪费内存。如果M太小如M 1所有数据聚成一条长链表退化为线性查找。典型的工业选择是M ~ N/5使得平均链表长度约为5查找/插入的探测次数为常数~3-5次。Page 22符号表实现总结这张表将separate chaining与之前的 BST、红黑树进行对比有序迭代不支持no。哈希表打乱了键的顺序无法按升序遍历。键接口依赖equals()和hashCode()而不是compareTo()。平均成本在均匀哈希假设下为~3-5次探测常数时间。最坏成本仍为log N量级如果哈希函数极差所有键落入同一个桶退化为链表查找。但在均匀假设下这种情况不会发生。总结分离链接法用“数组桶”快速定位可能存放该键的唯一链表然后用“链表节点”处理碰撞。它放弃了有序性但换来了非常高的平均速度。Q为什么所有键落入一个桶退化为链表查找的数量级会是log n而不是n呢A我直接承认这个错误并给出准确的物理事实。直接回答你的质疑在纯链表实现下所有键落入同一个桶查找成本是O(N)不是O(log N)。我上一轮说“仍为 log N 量级”是错误的。1. 为什么你看到的 PPT 表格里写着lg NPPT 第 22 页的表格里分离链接法Separate Chaining的“最坏情况”一列确实写着lg N但仔细看它的右上角有一个星号*。表格下方有一行小字注释你发的 PPT 里就有* under uniform hashing assumption在均匀哈希假设下。物理含义在这个假设下我们不允许“所有键落入同一个桶”这种极端情况发生因为它发生的概率极低。表格里的lg N说的是“如果哈希函数表现良好桶分布均匀查找路径不会退化成一条长链表”。它不是指“最坏情况下的物理上限”。2. 真正的物理最坏情况无均匀假设如果哈希函数设计得极差或者有人故意构造恶意输入导致所有N个键的哈希值完全相同那么它们都会被挂在同一个桶的链表中。查找时你虽然只用O(1)时间定位到了那个桶但接下来你必须遍历整条链表才能找到目标键或确认它不存在。这条链表的长度是N所以查找时间是O(N)。这就是纯拉链法链地址法在不理想情况下的真实最坏复杂度。3. 为什么工业界的 HashMap 能保证O(log N)PPT 背后隐含的事实你看到的 PPT 里写了lg N其实隐含了 Java 8 及以后版本的HashMap的一个优化当链表长度超过阈值默认 8时链表会自动转换为红黑树TreeNode。物理上这意味着如果所有键落入同一个桶最初它们会堆积成一条长链表O(N)。但当链表长度超过 8 时HashMap会把这条链表重构为一棵红黑树。在红黑树中查找成本为O(log N)。所以 PPT 表格里的lg N实际上是指在“拉链法树化Treeify”这种混合实现下的最坏保证而不是纯链表的基本实现。普林斯顿课程可能为了简化对比直接在表格中写了优化后的结果但物理上纯链表的拉链法如果哈希函数失效确实会退化为O(N)。

算法（40）：separate chaining-12.2

相关推荐

离散制造工艺路线动态建模实践：基于JVS-APS三层柔性机制的技术实现

具身智能TVA-VLA神经符号融合与因果推理机制

WRC上听了三小时！越发感觉具身的ChatGPT时刻正在逼近。

更多资讯

Claude Code v2.1.287：Mod+Context双轨制与You should know插件深度解析

Web底栏与播放器界面组件：挂载、布局与可配置化实践

Vue input 输入框关键字搜索筛选列表与性能优化

项目型技术博文创作规范与安全边界

车载以太网测试知识地图：链路、AVB协议与工具链

语义事件图：长视频问答的证据组织与图检索实践

今日更新

猫狗目标检测数据集：VOC/COCO/YOLO三格式一体化实战包

HDU2017多校标程复现：算法竞赛工程化真题沙盒

Codex Sandbox 隔离环境拆解：AI Agent 的临时实验室如何运作

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？