Page 25开放地址法的核心思想物理结构不再使用链表作为辅助数据结构。所有数据直接存储在哈希表数组本身。处理碰撞的方式如果计算出的索引i已经被占用就检查下一个槽位i1如果还被占用就继续检查i2直到找到一个空位。这个过程被称为探测Probing。图片含义图的上半部分显示的是键S、E等经过哈希后分散在数组各处下半部分是线性探测的典型状态——数据在数组中形成了一些连续被占用的块Cluster。Page 26插入的物理动作物理步骤插入一个键值对计算哈希值得到起始索引i。从i开始依次检查数组槽位i,i1,i2...到达数组末尾后折回到数组开头0即取模运算(i1) % M。如果找到一个空槽位keys[i] null把键存入keys[i]值存入vals[i]。如果找到一个已存在的、且与当前键相等的键更新该槽位的值覆盖。如果数组已满N M则无法插入需要先扩容再插入。物理前提数组大小M必须大于键值对总数N否则会陷入死循环永远找不到空位。例如假设hash(E)5hash(L)5array[5]null。先插入E则E的位置是array[5]插入L则L的位置本该是array[5]array[5]有元素了就去看array[6]。发现array[6]空着-插入到array[6]发现array[6]也满了-看array[7]。Page 27查找的物理动作物理步骤查找一个键计算哈希值得到起始索引i。从i开始依次检查数组槽位。命中条件如果keys[i]不为null且与目标键相等equals返回true返回对应的vals[i]。未命中条件如果检查到某个槽位keys[i]为null空则立即停止查找并返回null。因为线性探测在插入时总是把键放在第一个遇到的空位。如果这个位置是空的说明目标键在插入时本应在这个空位之前被找到若它不存在那么它一定不存在于后面的任何位置。Page 28为什么数组必须留有空位物理逻辑Search依赖“遇到空位就停止”作为终止条件。如果数组被填满N M那么查找一个不存在的键时会陷入无限循环因为永远遇不到空位。图片含义展示了插入和查找过程中指针的移动轨迹——S放在索引 5E放在索引 8等等。当K的哈希值为 5 时它占用了S旁边的位置这就是探测链的形成过程。Page 29Java 实现骨架物理代码逻辑维护两个平行数组keys[]和vals[]。put方法从哈希值i开始用(i1)%M步进。循环条件keys[i] ! null直到遇到空位。如果找到匹配键更新值并返回。退出循环后将新键值存入该空位。get方法同样从哈希值i开始步进。循环条件keys[i] ! null。如果找到匹配键返回值。遇到null时返回null查找未命中。注意当数组快满时这个循环会非常长因为很难遇到null。所以必须控制负载因子α N/M典型值不超过0.5或0.75。Page 30簇——Cluster物理定义簇是指数组中一段连续的、被占用的槽位没有任何空位间隔。物理问题线性探测导致键倾向于聚集成簇。这是因为如果新的键散列到簇中的任何一个位置它都会被附加到该簇的末尾导致簇不断“膨胀”。这种膨胀会形成“雪崩效应”使查找时间迅速增长。Page 31Knuth 的停车问题——物理模型这是高德纳Knuth用来描述线性探测行为的经典模型。模型假设一条单行道上有M个停车位。每辆车想停在一个随机车位i。如果车位i被占了它就往前开停在第一个空位上。物理对应车 插入的键。随机车位i 哈希值。向前开到第一个空位 线性探测i1i2...。关键结论当停车场半满M/2辆车时平均位移司机停下的位置与想停的位置的距离约为~1.5个车位即只需探测 2-3 次。当停车场全满时平均位移为~√(πM/8)非常大。这证明了线性探测的效率完全取决于负载因子。Page 32性能分析公式核心结论基于均匀哈希假设查找命中Search hit平均探测次数 ≈1/2 * (1 1/(1-α))。查找未命中 / 插入Search miss / Insert平均探测次数 ≈1/2 * (1 1/(1-α)^2)。物理取值Typical choice: α N / M ~ ½.当α 0.5半满时查找命中约需1.5次探测。查找未命中约需2.5次探测。当α 0.9快满时查找未命中约需50次探测指数级增长。工程结论为了保持高效必须在数组接近半满时进行扩容rehash。Page 33实现总结这张表对比了线性探测法与其他实现有序迭代不支持no。和链地址法一样哈希表不保留顺序。平均成本在均匀假设下为~3-5次探测与链地址法性能接近。空间相比链地址法线性探测法的内存更紧凑没有额外的链表节点Node开销因此缓存命中率更高数组是连续内存。总结物理事实线性探测法利用连续内存解决了冲突。插入时沿着数组向后找空位查找时沿着数组向后找键遇到空位即停止。它的性能核心在于控制负载因子α保持数组半满以避免形成长簇导致的雪崩效应。Q我想知道linear probing最差情况为什么是log nA表格里的lg N不是“物理绝对最坏情况”而是“在均匀哈希假设下的高概率最坏情况”。简单说就是“几乎不可能发生的、最极端的那种坏”。1. 物理绝对最坏情况无任何假设假设你的哈希函数烂到家了或者有人故意构造恶意输入导致所有键的哈希值完全一样。对于分离链接法所有键都在一条链表里查找需要遍历N个节点。复杂度是O(N)。对于线性探测法所有键在数组中紧密地挤成一长条连续块查找必须从起始位置一路探测到这个长块的末尾同样需要扫描N个位置。复杂度也是O(N)。这种最坏情况在理论上存在但 PPT 表格中的lg N不是指这种情况。2. 表格里的lg N带星号*的前提表格里的lg N旁边有一个星号*注释写着“在均匀哈希假设下under uniform hashing assumption”。在这个假设下哈希函数是完美随机均匀的——每个键落入每个桶的概率都相等且独立。在这种随机模型下即便你查询的是“最倒霉的那个键”它的探测链链表长度或簇长度也不会无限增长。数学结论概率论在均匀假设下即使是最长的那个链表或最长的连续簇它的长度大概率不会超过Θ(log N / log log N)对于分离链接或者被限制在O(log N)量级。超过c * lg N的概率极小小于1 / N^c。对于N 100万这个概率小到在实际运行中几乎不可能发生。所以PPT 把这种“概率意义上几乎不会出现”的上限标记为lg N作为带星号的保证。3. 为什么线性探测法也在最坏情况写lg N线性探测法发生碰撞时键会连续地占据相邻槽位。在均匀假设下形成极长簇的概率同样是极低的。数学上可以证明这种极长簇的长度受到对数级别的概率限制。表格里的对比逻辑红黑树2lgN是确定性保证无论输入如何高度一定不超过2lgN。哈希表lgN *是概率性保证只要哈希函数是好的输入不是针对你构造的超出lgN的概率可以忽略不计。4. 这和你之前学过的“洗牌”有什么关系这和你之前在快速排序里学到的“随机洗牌”类似快速排序在随机打乱后最坏情况N²发生的概率极低所以我们认为它是NlogN。哈希表在均匀哈希假设下最坏情况N发生的概率极低所以我们认为它是lgN。结论lg N是概率上的保守上界不是物理绝对上界。如果哈希函数失效或遭遇恶意攻击它会退化为O(N)。这就是为什么工业界如 Java 8 的HashMap会在链表过长时自动转换为红黑树以此来防御那 1% 的极端或恶意情况。Page 42哈希表 vs. 平衡搜索树 —— 最终决策指南这一页决定了你在实际项目中该用什么数据结构选哈希表你刚学的键不要求有序不用找最大、最小、范围查询。追求极致的速度平均常数时间。键类型无法直接比较没有compareTo。选红黑树平衡树需要有序性min、max、rank、floor、范围查找。需要确定性的最坏情况保证避免 DoS 攻击或极端输入导致性能雪崩。要求键必须可比较。总结上下文这一节它直接回应了你在第 1-2 页看到的问题——“我们能做得更好吗”回答是能更快哈希表但代价是放弃了有序性引入了安全风险针对公开哈希的攻击且最坏情况会退化为链表。因此工业界通常同时提供两者Java 有HashMap无序、快和TreeMap有序、有保证。补漏1. 补漏一为什么最坏情况写log N解开你的疑惑你问“为什么是log n来着”。这里有一个非常细微的区分平均情况当数组半满负载因子α N/M ≈ 0.5时查找或插入只需要探测约1.5 ~ 2.5次。这是常数时间O(1)不是log N。最坏情况带星号*表格里写的log N指的是在均匀哈希假设下出现“极长簇”的概率极低其长度被限制在O(log N)量级。这不是物理上的绝对最坏情况物理上所有键挤在一起探测次数是O(N)。这是概率上的保证除非哈希函数极差或被恶意攻击否则实际运行中探测次数不会超过log N的常数倍。所以表格里的log N是“防意外的天花板”不是“日常的平均值”。2. 补漏二线性探测中最棘手的操作——删除Delete你漏掉的这个点是线性探测和分离链接法最大的区别。你不能简单地直接把删除位置置为null。物理场景假设三个键A、B、C的哈希值都指向索引5。插入A放在5。插入B5被占放在6。插入C6被占放在7。现在如果你删除B直接把keys[6] null会发生什么你查找C哈希值指向5检查5A不对检查6发现是null。查找算法会认为“遇到空位即终止”于是它报告C不存在。但C明明在7物理解决方案两种常用方式墓碑Tombstone删除时不置null而是置一个特殊标记如DELETED。查找时遇到DELETED不停止继续往后找。插入时可以复用DELETED的位置。缺点长期积累的墓碑会拖慢性能。簇重组Rehashing cluster删除B后把C从7往前移到6填补空缺。这种方法更复杂但保持了簇的连续性PPT 第 40 页暗示了这一点“Q. How to delete?”。3. 补漏三为什么簇会“越长越大”主聚类 Primary Clustering你说“数组半满时每隔几个就有一个空位”是对的但线性探测有一个致命缺陷一旦形成一个簇连续占用的块新键只要散列到这个簇里的任意一个位置都会直接被追加到簇的尾部导致簇不断膨胀。这就是所谓的“雪崩效应”也是为什么要维持α ≤ 1/2的根本原因。
Page 25开放地址法的核心思想物理结构不再使用链表作为辅助数据结构。所有数据直接存储在哈希表数组本身。处理碰撞的方式如果计算出的索引i已经被占用就检查下一个槽位i1如果还被占用就继续检查i2直到找到一个空位。这个过程被称为探测Probing。图片含义图的上半部分显示的是键S、E等经过哈希后分散在数组各处下半部分是线性探测的典型状态——数据在数组中形成了一些连续被占用的块Cluster。Page 26插入的物理动作物理步骤插入一个键值对计算哈希值得到起始索引i。从i开始依次检查数组槽位i,i1,i2...到达数组末尾后折回到数组开头0即取模运算(i1) % M。如果找到一个空槽位keys[i] null把键存入keys[i]值存入vals[i]。如果找到一个已存在的、且与当前键相等的键更新该槽位的值覆盖。如果数组已满N M则无法插入需要先扩容再插入。物理前提数组大小M必须大于键值对总数N否则会陷入死循环永远找不到空位。例如假设hash(E)5hash(L)5array[5]null。先插入E则E的位置是array[5]插入L则L的位置本该是array[5]array[5]有元素了就去看array[6]。发现array[6]空着-插入到array[6]发现array[6]也满了-看array[7]。Page 27查找的物理动作物理步骤查找一个键计算哈希值得到起始索引i。从i开始依次检查数组槽位。命中条件如果keys[i]不为null且与目标键相等equals返回true返回对应的vals[i]。未命中条件如果检查到某个槽位keys[i]为null空则立即停止查找并返回null。因为线性探测在插入时总是把键放在第一个遇到的空位。如果这个位置是空的说明目标键在插入时本应在这个空位之前被找到若它不存在那么它一定不存在于后面的任何位置。Page 28为什么数组必须留有空位物理逻辑Search依赖“遇到空位就停止”作为终止条件。如果数组被填满N M那么查找一个不存在的键时会陷入无限循环因为永远遇不到空位。图片含义展示了插入和查找过程中指针的移动轨迹——S放在索引 5E放在索引 8等等。当K的哈希值为 5 时它占用了S旁边的位置这就是探测链的形成过程。Page 29Java 实现骨架物理代码逻辑维护两个平行数组keys[]和vals[]。put方法从哈希值i开始用(i1)%M步进。循环条件keys[i] ! null直到遇到空位。如果找到匹配键更新值并返回。退出循环后将新键值存入该空位。get方法同样从哈希值i开始步进。循环条件keys[i] ! null。如果找到匹配键返回值。遇到null时返回null查找未命中。注意当数组快满时这个循环会非常长因为很难遇到null。所以必须控制负载因子α N/M典型值不超过0.5或0.75。Page 30簇——Cluster物理定义簇是指数组中一段连续的、被占用的槽位没有任何空位间隔。物理问题线性探测导致键倾向于聚集成簇。这是因为如果新的键散列到簇中的任何一个位置它都会被附加到该簇的末尾导致簇不断“膨胀”。这种膨胀会形成“雪崩效应”使查找时间迅速增长。Page 31Knuth 的停车问题——物理模型这是高德纳Knuth用来描述线性探测行为的经典模型。模型假设一条单行道上有M个停车位。每辆车想停在一个随机车位i。如果车位i被占了它就往前开停在第一个空位上。物理对应车 插入的键。随机车位i 哈希值。向前开到第一个空位 线性探测i1i2...。关键结论当停车场半满M/2辆车时平均位移司机停下的位置与想停的位置的距离约为~1.5个车位即只需探测 2-3 次。当停车场全满时平均位移为~√(πM/8)非常大。这证明了线性探测的效率完全取决于负载因子。Page 32性能分析公式核心结论基于均匀哈希假设查找命中Search hit平均探测次数 ≈1/2 * (1 1/(1-α))。查找未命中 / 插入Search miss / Insert平均探测次数 ≈1/2 * (1 1/(1-α)^2)。物理取值Typical choice: α N / M ~ ½.当α 0.5半满时查找命中约需1.5次探测。查找未命中约需2.5次探测。当α 0.9快满时查找未命中约需50次探测指数级增长。工程结论为了保持高效必须在数组接近半满时进行扩容rehash。Page 33实现总结这张表对比了线性探测法与其他实现有序迭代不支持no。和链地址法一样哈希表不保留顺序。平均成本在均匀假设下为~3-5次探测与链地址法性能接近。空间相比链地址法线性探测法的内存更紧凑没有额外的链表节点Node开销因此缓存命中率更高数组是连续内存。总结物理事实线性探测法利用连续内存解决了冲突。插入时沿着数组向后找空位查找时沿着数组向后找键遇到空位即停止。它的性能核心在于控制负载因子α保持数组半满以避免形成长簇导致的雪崩效应。Q我想知道linear probing最差情况为什么是log nA表格里的lg N不是“物理绝对最坏情况”而是“在均匀哈希假设下的高概率最坏情况”。简单说就是“几乎不可能发生的、最极端的那种坏”。1. 物理绝对最坏情况无任何假设假设你的哈希函数烂到家了或者有人故意构造恶意输入导致所有键的哈希值完全一样。对于分离链接法所有键都在一条链表里查找需要遍历N个节点。复杂度是O(N)。对于线性探测法所有键在数组中紧密地挤成一长条连续块查找必须从起始位置一路探测到这个长块的末尾同样需要扫描N个位置。复杂度也是O(N)。这种最坏情况在理论上存在但 PPT 表格中的lg N不是指这种情况。2. 表格里的lg N带星号*的前提表格里的lg N旁边有一个星号*注释写着“在均匀哈希假设下under uniform hashing assumption”。在这个假设下哈希函数是完美随机均匀的——每个键落入每个桶的概率都相等且独立。在这种随机模型下即便你查询的是“最倒霉的那个键”它的探测链链表长度或簇长度也不会无限增长。数学结论概率论在均匀假设下即使是最长的那个链表或最长的连续簇它的长度大概率不会超过Θ(log N / log log N)对于分离链接或者被限制在O(log N)量级。超过c * lg N的概率极小小于1 / N^c。对于N 100万这个概率小到在实际运行中几乎不可能发生。所以PPT 把这种“概率意义上几乎不会出现”的上限标记为lg N作为带星号的保证。3. 为什么线性探测法也在最坏情况写lg N线性探测法发生碰撞时键会连续地占据相邻槽位。在均匀假设下形成极长簇的概率同样是极低的。数学上可以证明这种极长簇的长度受到对数级别的概率限制。表格里的对比逻辑红黑树2lgN是确定性保证无论输入如何高度一定不超过2lgN。哈希表lgN *是概率性保证只要哈希函数是好的输入不是针对你构造的超出lgN的概率可以忽略不计。4. 这和你之前学过的“洗牌”有什么关系这和你之前在快速排序里学到的“随机洗牌”类似快速排序在随机打乱后最坏情况N²发生的概率极低所以我们认为它是NlogN。哈希表在均匀哈希假设下最坏情况N发生的概率极低所以我们认为它是lgN。结论lg N是概率上的保守上界不是物理绝对上界。如果哈希函数失效或遭遇恶意攻击它会退化为O(N)。这就是为什么工业界如 Java 8 的HashMap会在链表过长时自动转换为红黑树以此来防御那 1% 的极端或恶意情况。Page 42哈希表 vs. 平衡搜索树 —— 最终决策指南这一页决定了你在实际项目中该用什么数据结构选哈希表你刚学的键不要求有序不用找最大、最小、范围查询。追求极致的速度平均常数时间。键类型无法直接比较没有compareTo。选红黑树平衡树需要有序性min、max、rank、floor、范围查找。需要确定性的最坏情况保证避免 DoS 攻击或极端输入导致性能雪崩。要求键必须可比较。总结上下文这一节它直接回应了你在第 1-2 页看到的问题——“我们能做得更好吗”回答是能更快哈希表但代价是放弃了有序性引入了安全风险针对公开哈希的攻击且最坏情况会退化为链表。因此工业界通常同时提供两者Java 有HashMap无序、快和TreeMap有序、有保证。补漏1. 补漏一为什么最坏情况写log N解开你的疑惑你问“为什么是log n来着”。这里有一个非常细微的区分平均情况当数组半满负载因子α N/M ≈ 0.5时查找或插入只需要探测约1.5 ~ 2.5次。这是常数时间O(1)不是log N。最坏情况带星号*表格里写的log N指的是在均匀哈希假设下出现“极长簇”的概率极低其长度被限制在O(log N)量级。这不是物理上的绝对最坏情况物理上所有键挤在一起探测次数是O(N)。这是概率上的保证除非哈希函数极差或被恶意攻击否则实际运行中探测次数不会超过log N的常数倍。所以表格里的log N是“防意外的天花板”不是“日常的平均值”。2. 补漏二线性探测中最棘手的操作——删除Delete你漏掉的这个点是线性探测和分离链接法最大的区别。你不能简单地直接把删除位置置为null。物理场景假设三个键A、B、C的哈希值都指向索引5。插入A放在5。插入B5被占放在6。插入C6被占放在7。现在如果你删除B直接把keys[6] null会发生什么你查找C哈希值指向5检查5A不对检查6发现是null。查找算法会认为“遇到空位即终止”于是它报告C不存在。但C明明在7物理解决方案两种常用方式墓碑Tombstone删除时不置null而是置一个特殊标记如DELETED。查找时遇到DELETED不停止继续往后找。插入时可以复用DELETED的位置。缺点长期积累的墓碑会拖慢性能。簇重组Rehashing cluster删除B后把C从7往前移到6填补空缺。这种方法更复杂但保持了簇的连续性PPT 第 40 页暗示了这一点“Q. How to delete?”。3. 补漏三为什么簇会“越长越大”主聚类 Primary Clustering你说“数组半满时每隔几个就有一个空位”是对的但线性探测有一个致命缺陷一旦形成一个簇连续占用的块新键只要散列到这个簇里的任意一个位置都会直接被追加到簇的尾部导致簇不断膨胀。这就是所谓的“雪崩效应”也是为什么要维持α ≤ 1/2的根本原因。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
