迪士尼彩乐园哪个是真 本科生推翻姚期智40年前的算计，提倡哈希表算法阻挠搜索效果极限
哈希表（hash table）是运筹帷幄机科学中最基础也最要紧的数据结构之一迪士尼彩乐园哪个是真，它的历史不错回想到 20 世纪 50 年代早期。哈希表的中枢想想是通过一个，将自便界限的键值映射到一个固定大小的数组空间中。
这种数据结构就像一个高大的抽屉柜，每个数据皆不错被赶紧放入某个抽屉中，并在需要时快速取出。但当抽屉柜接近装满时，找到相宜的空抽屉就变得越来越辛苦。
国铁广州局集团公司有关负责人表示，铜吉铁路建成后，将成为连接沪昆高铁和张吉怀高铁的重要纽带，彻底打通铜仁高铁的“断头路”，形成贵阳至郑州（武汉）间的高铁新通道，实现昆明、贵阳至张家界高铁直达。（完）
也即是说，当一个接近装满时（比如说也曾占用了 99% 的空间），要在剩余空间中找到一个空位至少需要进行与填充率成正比的次数搜索。这就意味着，如若哈希表也曾 99% 满了，那么在最坏情况下，需要大致 100 次尝试能力找到一个空位。这个表面限制就像物理学中的光速极限雷同，被以为是不能起始的。
1985 年，图灵奖得主在其具有里程碑意思意思的论文 Uniform Hashing is Optimal 中提倡在具有特定属性的哈希表中，速即遴荐抽屉的形态，即均匀探伤（uniform probing）是最优的遴荐。
近 40 年来，运筹帷幄机科学家们渊博以为姚期智的这个算计是正确的。这种共鸣不仅影响了数据库系统的蓄意，也深刻影响了宽阔依赖高效数据存储的当代应用递次。关联词，这个看似坚不能摧的表面堡垒，最近被一位年青的本科生撼动了。
这个阻挠性的发现源于一个看似无意的契机。2021 年秋天，罗格斯大学的本科生 Andrew Krapivin 在浏览学术论文时，发现了一篇名为 Tiny Pointers 的著述。这篇论文探讨了一种新式的数据指针技能，粗略大幅减少运筹帷幄机内存的使用。当时候 Krapivin 并莫得想太多，但两年后，当他果然动手深入参谋这篇论文时，他意志到这里面荫藏着更多的可能性。
Tiny Pointers 这篇论文探讨了一个看似简单但意思意思长远的问题：若何用更少的比特位来存储运筹帷幄机中的指针。传统的指针需要 log n 个比特能力在 n 个位置中定位一个元素。但这篇论文提倡了一个玄妙的想路：如若咱们事先知谈指针属于哪个用户，那么就不错诳骗这个非常信息来压缩指针的大小。
恰是这种压缩指针的想路启发了 Krapivin 对哈希表的新理会，在哈希表搜索历程中，咱们其实也不错诳骗之前探伤赢得的信息来指点后续的搜索。
比拟之下，传统方律例假定每次探伤皆是孤独的、均匀速即的。而 Krapivin 莫得被这一种相貌所抑止，其实也只是因为他并不知谈这种形态。
他用 Tiny Pointers 进行的探索导致了一种新式的哈希表——一种不依赖于均匀探伤的哈希表。对于这种新的哈希表，最坏情况下的查询和插入所需的时候与 (log x)2 成正比——比 x 快得多。这一收尾平直反驳了姚期智的算计。
当 Krapivin 向他的前教学、Tiny Pointers 的共同作家 Martín Farach-Colton 展示这个蓄意时，后者最初显得相等怀疑。这种严慎是不错赓续的：哈希表是运筹帷幄机科学中参谋最充分的数据结构之一，紧要阻挠似乎不太可能。但当论文的另一位协作家、卡内基梅隆大学的 William Kuszmaul 仔细谛视这项责任时，他意志到了其翻新性意思意思。
“你并不是只是发明了一个新的哈希表，”Kuszmaul 对 Krapivin 说，“你实质上十足推翻了一个存在了 40 年的算计！”
最终，他们共同协作，完成了这篇论文。
康奈尔理工学院的 Alex Conway 评价谈：“这是一项草创性的责任。尽管哈希表也曾有着悠久的历史，但对于它们的责任旨趣，咱们仍然有好多需要了解的所在。这篇论文以令东谈主惊诧的相貌回复了其中的几个根人道问题。”
要赓续这项责任的草创性，咱们需要先明确传统哈希名义临的根人道挑战。
在传统的绽开寻址哈希表中，当咱们需要插入一个新元素时，会按照某个预界说的探伤序列一一检讨位置，直到找到第一个空位。这种形态就被称为“决议计谋”，因为它老是急于禁受第一个可用的位置。姚期智在 1985 年的论文中施展，在这种决议计谋下，当哈希表接近满载时（比如说留有δ比例的空位），最坏情况下需要 O(δ^-1) 次探伤能力找到一个空位。况且他算计这个界限对于任何决议计谋皆是最优的。
关联词，Krapivin 的责任施展，如若咱们称心毁掉决议计谋，实质上不错赢得显赫更好的性能。参谋提倡了一种新的哈希表构造形态，定名为“弹性哈希”（Elastic Hashing），获胜杀青了均派探伤复杂度 O(1) 的最优解，同期使得最坏情况的探伤复杂度降至 O(log δ⁻¹)。这一参谋不仅推翻姚期智的算计，还在不依赖重排操作的前提下，初次施展了更优的探伤复杂度下界。
就像 Tiny Pointers 通过诳骗非常的荆棘文信息来减少存储支拨，弹性哈希通过相聚更多的探伤信息来作念出更灵验的扬弃决策。其中枢想想是将通盘哈希表分袂为多个子数组，并通过一种二元探伤结构进行索引。
在该模子中，哈希表被拆分为一系列大小指数递减的子数组，举例 A₁、A₂、...、A_⌈log n⌉，其中 |Aᵢ₊₁| = |Aᵢ|/2 ± 1。这种档次结构为非决议探伤提供了可能，使得插入操作不错优先在负载较低的区域进行，同期保证查找历程的高效性。参谋者引入了一个特定的映射 φ(i,j)，使得二维探伤序列 hᵢ,ⱼ (x) 不错映射到一维探伤序列 hφ(i,j)(x)，其中 φ(i,j) ≤ O(i·j²)。该映射的蓄意确保了在插入历程中，较早被打听的探伤位置粗略更高效地找到空槽，从而裁减举座探伤复杂度。
具体来说，弹性哈希收受分批次插入计谋，以确保各个子数组的负载水平得到合理分派。起始，迪士尼彩乐园骗我钱在开动批次 B₀中，哈希表的第一个子数组 A₁ 被填充至约 75% 的负载。随后，在后续的批次 Bᵢ 中，插入操作东要发生在 Aᵢ和 Aᵢ₊₁ 之间，确保每个子数组的负载保合手在合理界限内。
插入历程中，如若某个子数组仍有较多可用槽位（空位比例高于 δ/2），新元素将尝试在该子数组内找到相宜的位置。而当子数组接近满载时，插入算法会自动转向下一级子数组，以普及存储效果。此外，在最坏情况下，即通盘子数组的空位皆格外有限时，算法会璧还到均匀探伤计谋，但这种情况的概率极低，确保了举座复杂度的优化。
数学分析标明，该形态粗略显赫裁减均派探伤复杂度和最坏情况探伤复杂度。起始，在均派探伤复杂度方面，参谋者施展了弹性哈希的平均探伤次数为 O(1)，这意味着大多量操作只需要常数次探伤就能完成。远优于均匀探伤的 O(log δ⁻¹)。其根蒂原因在于，弹性哈希将大多量插入操作限制在负载较低的子数组中，使得多量元素粗略在一丝探伤后获胜存储。
其次，在最坏情况探伤复杂度方面，参谋标明在无重排的情况下，任何绽开寻址哈希的最坏情况探伤复杂度必须至少达到 Ω(log δ⁻¹)，而弹性哈希杀青了这一下界的最优匹配。
在弹性哈希形态的基础上，参谋者进一步提倡了一种新的决议绽开寻址（Open Addressing）计谋，定名为“漏斗哈希”（Funnel Hashing）。通过构造一种层级结构的哈希表，该形态杀青了最坏情况的盼愿探伤复杂度 O(log²δ⁻¹)，况且施展了这一界限的最优性。
漏斗哈希的基本想想是在哈希表中引入多级结构，使得元素在不同负载水平的区域之间进行分层存储，从而裁减高负载情况下的探伤次数。具体而言，哈希表被分袂为多个层级，每一层里面进一步分为几许个等大小的子数组，通盘子数组的大小按几何级数递减。假定哈希表的总容量为 n，参谋者起始将其分袂为两部分，其中一部分（记为A_α+1）的大小约为 δn，用于存储最难插入的元素，而剩余部分（记为 A'）再细分为 α 个子数组 A₁、A₂、...、Aα。这些子数组的大小递减探讨骄傲 |Aᵢ₊₁| ≈ 3|Aᵢ|/4，况且每个 Aᵢ 进一步分袂为几许个小块，每个小块的大小设定为 β，其中 β 取 O(logδ⁻¹)。
在插入历程中，每个元素起始会尝试插入最表层的子数组A₁，如若失败则挨次尝试 A₂, A3,……直到获胜找到空位或最终插足特意的存储区 A_α+1。在每一层的插入尝试中，元素会速即遴荐一个子块，并挨次扫描该子块中的位置以寻找空槽。这种分层探伤计谋确保了大多量插入操作不错在前几层完成，而仅有极少数插入会插足最底层的存储区域。
数学分析标明，漏斗哈希的最坏情况盼愿探伤复杂度为 O(log²δ⁻¹)，显赫优于均匀探伤的 O(δ⁻¹)。其中枢施伸开荒在以下几个舛误法子之上。
起始，参谋者施展了每个子数组在一定插入次数后皆会达到接近弥漫的现象，即子数组里面空槽的数目受严格律例。这意味着即使在较高负载的情况下，仍然不错保证大多量插入操作在 O(logδ⁻¹) 次探伤内获胜。其次，通过分析插入元素在不同层级上的散播，参谋者施展了即使在最坏情况下，元素也只需资格 O(log²δ⁻¹) 次探伤，即可找到一个可用的位置。此外，参谋者还施展了这一界限的最优性，标明任何决议绽开寻址哈希表皆无法阻挠 Ω(log²δ⁻¹) 的最坏情况探伤复杂度。
除了在盼愿探伤复杂度上的优化，漏斗哈希还具备精深的高概率最坏情况保证。参谋者进一步施展，在绝大多量情况下（即以1-1/poly(n) 的概率），自便一个元素的最坏情况探伤复杂度不会高出 O(log²δ⁻¹ + log log n)。这意味着即使在极点负载的情况下，该形态仍然粗略保合手较为踏实的性能，而不会出现大幅度退化的情况。
总之，这一形态的提倡不仅解答了姚期智在 1985 年提倡的未贬贬低题，即最坏情况的盼愿探伤复杂度是否不错低于 O(δ⁻¹)，还施展了均匀探伤在决议算法框架下并非最优。对于决议哈希表，最坏情况下的探伤复杂度不错裁减到 O(log²δ⁻¹)，而对于非决议哈希表，平均查询时候以致不错十足孤独于负载因子 δ。
“这只是一个常数，与哈希表是否满无关”，Farach-Colton 说。岂论哈希表是否满，查询的平均时候皆不错达到常数级别，这个发现以致出乎参谋者我方的猜度。
即便当今该参谋可能不会立即带来工业界的应用，但赓续数据结构的基础表面格外要紧，因为“你永久不知谈这么的收尾什么时候会解锁某种新的阻挠，让实质应用变得愈加高效。”Conway 暗示。
参考贵府：
1.https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/
2.https://doi.org/10.1145/3828.3836
3.https://arxiv.org/abs/2501.02305
4.https://arxiv.org/abs/2111.12800