算法（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)。