本科生推翻姚期智40年前料想！不测发明新型哈希

明敏 发自 凹非寺量子位 | 大众号 QbitAI姚期智40年前料想被本科买卖外推翻！00后本科生 安德鲁·克拉皮文（Andrew Krapivin，简称小克）发明了一种新型哈希表，数据搜寻速率超越以往全部方式。 要晓得，哈希表由于浅易疾速高机能，被普遍利用于盘算机迷信跟编程中。而这种新型哈希表在最坏情形下的查问跟拔出时光与(log x) ²成正比，远比之前以为的x快。后者恰是姚期智在1985年提出的料想。不只如斯，小克他们还发明非贪心哈希表的均匀查问时光能够到达一个与哈希表x有关的恒定值，这一发明也完整出其不意。网友：这太猖狂了！老是先生们实现了这些猖狂的发明。这一发明对懂得跟改良数据构造至关主要。一场不测的推翻哈希表（Hash table）是依据键而直接拜访在存储器存储地位的数据构造。也就是说，它经由过程盘算一个键值的函数，将所需查问的数据映射到表中一个地位让人来拜访，这放慢了查找速率。这个映射函数被称为哈希函数，寄存记载的数组称作哈希表。更艰深比方，哈希表就比如一个很年夜的文件柜，此中有良多个抽屉（槽）。每个抽屉能够寄存一个文件（数据项）。然而，文件柜很年夜，手动找文件确定很费事。以是，你应用一个 文件编号（哈希函数），它会告知你应当把某个文件放到哪个抽屉里，或许当你要找某个文件时，告知你该去哪个抽屉。 开展全文 比方寄存一个文件，文件名是“苹果”，经由过程文件编号规矩（哈希函数）失掉一个数字，假设是 3，那么就把“苹果”文件放到文件柜的第3个抽屉。 假如两个文件（比方“苹果”跟“喷鼻蕉”）的编号规矩（哈希函数）盘算出来是一样的（比方都被放到抽屉 3），那么就会产生 抵触。为了应答这个成绩，哈希表采取了处置抵触的战略，比方在抽屉里放一个“文件夹”（链表）来寄存全部抵触的文件，或许把文件放到下一个抽屉。 权衡哈希表已应用空间与总空间的比例，被称为 负载因子（Load Factor）。 负载因子(α)=存储元素的数目/哈希表桶的数目=n/m 当负载因子较小时，哈希表的空桶多、抵触少，查找效力较高，但可能挥霍内存。 当负载因子较高时，哈希表抵触增添，查找机能可能降落。 1985年，姚期智在论文 《Uniform Hashing Is Optimal》中提出，在存在特定属性的哈希表中，查找单个元素或空位的最佳方式是平均探测（uniform probing），并且最坏情形的拔出时光与x成正比。 即假如哈希表曾经99%满了，那么须要检查100个差别地位，才干找到一个空位。 此中，x表现哈希表被填满的间隔。 当x=100时，表现哈希表曾经被添补了99%，负载因子为0.99。当x=1000时，表现哈希表被添补了99.9%，负载因子为0.999。 这个料想在2021年被撼动了，不外这所有实在是场不测。 事先正在罗格斯年夜学读本科的小克读了一篇名为 《Tiny Pointers》的论文。 这篇论文提出了tiny pointer的观点，它能指向盘算机内存中的一段信息或一个元素。 读过论文后，小锐意识到有一种方式能够进一步下降tiny pointer内存应用的方式。 为此，他须要应用哈希表来存储tiny pointer指向的数据。 在这个进程中，他发明了一种任务速率更快的哈希表。 即最劣查问跟拔出所需时光与（log x）²成正比，比之前姚期智论文中提出的x快得多。 最开端，小克的导师对这个新发明表现猜忌，究竟哈希表从20世纪50年月出生以来，曾经被研讨得很透辟了。 为了验证这一发明能否准确，导师法拉·科尔顿（Farach-Colton）找到了卡内基梅隆年夜学的威廉姆·库斯莫尔（William Kuszmaul）一同验证。 成果就是库斯莫尔发明，小克不只发明了一个新的哈希表， 更进一步颠覆了40年前的料想。 网友：“不知”反而能够解脱传统门路 为啥小克能轻松推翻料想呢？ 由于他原来压根不晓得姚期智提出的料想，也是一种无意插柳了。 有人因而感叹：翻新的最佳方法老是要疏忽以往的一些门路。当初人们老是轻易堕入后人的头脑形式。 并且独一无二，有人表现一位医学职员再次发明了复合梯形公式。 固然，可能提出新哈希表，也是由于小克自身就很优良。 他本科就读于罗格斯年夜学，双修数学跟盘算机迷信。 他是近十年来罗格斯年夜学新布伦瑞克分校首位拿到剑桥研讨生奖学金的先生。 接上去他将前去剑桥年夜学，攻读盘算机迷信跟哲学硕士学位。 他的教师法拉·科尔顿乃至说，小克是本人在罗格斯年夜学 32年以来见过最优良的本科生。 进修之外，他爱好下象棋、拍照跟诗歌，以及揣摩CPU、GPU、AI处置器等。 值得一提的是，小克的哥哥也是罗格斯年夜学结业。 参考链接：前往搜狐，检查更多