美国留学

2024年10月，刚刚成为剑桥大学研究生的安德鲁·克拉平金（Andrew Krapivin）与两名合作者发表了一篇论文，推翻了关于哈希表的计算机科学的40年猜想。哈希表是计算机最常用的数据结构之一，它们设计的新哈希表*降低了复杂性。这项成就通过了1985年的图灵奖奖得主Yao Qizhi的经典理论，重新定义了哈希表的性能限制，并为数据结构设计开辟了新的想法。 |撰写Chen Qingyang

介绍在2021年秋天，罗格斯大学的大二学生安德鲁·克拉皮文（Andrew Krapivin）不小心阅读了他的算法老师MartnFarach-Colton，Tiny Pointers [1]。受论文的启发，克拉平金（Krapivin）在两年后设计了一张新的哈希餐桌，并最终与他的老师马丁·法拉赫·科尔顿（MartnFarach-Colton）和卡内基·梅隆大学（Carnegie Mellon University）的老师马丁·法拉赫·科尔顿（MartnFarach-Colton）和威廉·库斯玛（William Kuszmau）在2024年IEEE计算机科学基础（FOCS）会议上的论文中发表了论文。本文在计算机领域重新审查了一个长期存在的问题：开放解决方案表的检测复杂性[2]。早在1985年，中国计算机科学家Yao Qizhi就已经回答了这个问题[3]。在接下来的40年中，直到克拉平金（Krapivin）的这篇论文，似乎没有人质疑他看似正确的结论。 Krapivin等。提出了一个新的哈希表，并在分析了新的哈希表之后，发现得出结论的结论可能不完整。本文将简要介绍哈希表的基本原理，并为试图进一步探索主题的读者提供一些背景知识。

图1安德鲁·克拉平金（Andrew Krapivin）于2024年获得丘吉尔奖学金，他即将上剑桥大学攻读硕士学位。

在计算机科学中，哈希表的起源（哈希表，也被翻译为哈希表）是最重要，最常用的数据结构之一。提议解决“查找问题”。所谓的搜索问题是查询是否从一堆数据中存在特定数据；如果存在，是否与特定值相关联。在计算机应用程序中，搜索问题无处不在。毫不夸张地说，我们手机和计算机上的所有常用软件每次使用时都涉及各种搜索。他们中的许多人都在搜索程序中的内部数据，许多人与用户直接相关，例如基于微信找到朋友，根据银行应用程序中的用户ID找到他们的帐户余额，找到某个页面的资源是否在浏览器中缓存等等。那么计算机系统如何实现搜索？就像我们人类在图书馆中寻找书籍并在Express货架上的Express交付方式一样，搜索计算机的最简单方法实际上是一个一个搜索：从数据启动的位置，直到数据结束，请一一比较，以查看他们是否正在寻找。当数据没有太多的数据时，一个一个一个一个搜索就没有问题，甚至很快。我们经常在生活中寻找这样的事情。但是，当数据量很大时，遍历搜索的效率不高。请想象，如果我们想在一个带有100万个快速交付物品的巨大且无序的仓库中找到自己的一个，那就就像在干草堆里寻找针头一样。计算机也是如此。即使现代计算机非常快，当数据量很大时，这种线性搜索过程可能会成为整个程序的性能瓶颈。提出了哈希表以更有效地启用计算机中的搜索。与上述线性搜索（或一对一的遍历）相比，使用哈希表搜索要快得多。实际上，使用哈希表可以在恒定时间内完成搜索。所谓的恒定时间意味着搜索时间也不会随数据的量增加——，即使数据量变大，搜索也可以快速完成。哈希桌是由IBM工程师汉斯·彼得·卢恩（Hans Peter Luhn）发明的。卢恩（Luen）于1896年出生于德国的班登（Bamen）。他早年在印刷和纺织工业工作。他知识渊博，热爱发明。他知识渊博，擅长登山，食物和景观绘画。在1930年代，Lun已经拥有了许多专利，包括可折叠的雨衣和“鸡尾酒甲骨文”（指南，告诉用户可以使用现有食材饮用的饮料）。卢恩（Luen）对文本信息的存储，沟通和检索特别感兴趣，他最终加入了IBM进行相关研究[4]。在1950年代，计算机技术正在蓬勃发展，计算机处理的数据量越来越大，线性搜索方法不再适用于巨大的数据量。 1953年1月，卢恩（Luen）撰写了内部IBM备忘录，该备忘录使用链接的哈希方法来执行更有效的数据检索，这是当今哈希表的原型。

哈希表的基本思想。为了更好地阐明哈希表的想法和原理，我们首先将简要了解计算机的操作模型，中央处理单元（CPU），内存和编程（或“编程”）之间的关系。 CPU是计算机的核心，它可以执行各种算术，逻辑操作或有条件的跳跃指令； CPU内部的数据很少，数据主要存储在内存中。 CPU支持随机内存访问，并可以执行指令以读取或写任何内存地址。一系列CPU指令形成了一个计算机程序，该程序将按顺序连续执行。因此，可以考虑典型计算机程序的工作流量如下：1）从内存到CPU的数据读取数据； 2）完成CPU内的各种计算； 3）计算后，数据将通过CPU写入内存中。可以重复此过程，直到完成任务为止。与快速交付站的示例相比，内存就像明确的机柜或架子，包装在其中存储； CPU是车站的一名员工，负责存储明确交付和执行操作；该计划是车站的老板，负责设计由员工实施的快递和提款的策略或方法。现在，我们可以找到明确的交付，也就是说，找到了问题。假设我们有一个可以将键映射到值的表，并且表格中不能有重复的键。这里的键和值可以是任何类型的，代表任何类型，并且为了理解，我们假设键和值是整数。对于这样一个想象中的表，我们定义了三个操作：

put（键，值）：添加一个新条目将键映射到值；如果密钥已经存在，请用新值覆盖原始值。获取（键）：获取与密钥相对应的值，即“查找”操作。删除（键）：删除与密钥相对应的条目。这样的表也称为字典或关联的数组。一开始，表是空的，假设我们按以下顺序进行以下操作：

put（1045，1）put（1056，2）put（1067，3）完成上述操作后，表的状态应为如下[每行称为键值对]。与快速交付方案相对应，密钥可以代表物流公司的快递订单编号，并且该值是用户ID。现在，我们要收集三个快递。

在计算机中实现此表的最简单方法是：当操作操作时，这些键值对依次写入相邻的内存地址，也就是说，它们被存储在数组中（数组是存储器中的数据结构，代表连续的内存空间，并且可以动态扩展大小，如下表所示）。数组中的每个元素都是键值对；在搜索时，即进行GET操作时，阵列从头到尾都线性地扫描，并且每个元素都会按顺序读取，并将其关键部分与目标密钥进行比较。如果两者都相同，则搜索结束，并且返回数据的值部分，否则将扫描下一个元素。

对于较小的数据量，上面提到的遍历方法实际上并不慢，甚至可以说是最有效的。在计算机科学中，人们使用时间复杂性（在我们的文章中称为复杂性）来正式测量算法的效率或速度。它描述了计算机完成算法所需的基本操作的步骤数（或指令）如何随着算法流程的增加而增加。假设输入数据的大小为n（在搜索问题中，n表示表中的条目总数），那么时间复杂性分析试图回答：计算机要求完成算法和N所需的基本操作步骤数量是什么？它与n（线性生长）成正比吗？它与n（指数增长）的指数成正比吗？还是与N的对数成正比？即使，它也可能不取决于n。让我们以线性搜索为例，并尝试分析所需的操作步骤数与输入大小n之间的关系。假设所有密钥都有相同的概率搜索，那么在最快的情况下，搜索只需要搜索一次，也就是说，密钥是第一个条目。在最坏的情况下，它需要搜索n次，也就是说，关键是最后一个条目。平均而言，您需要搜索

然后，随着n，o（n）的增加，步骤数增加的方式代表输入的线性增加。因此，我们在线性搜索之前说过“较慢”。现在，我们可以使用特定的符号来指示它的慢性，也就是说，o（n）。因此，有什么方法可以更快地进行搜索，甚至一口气找到它？读者可能会认为，当键是整数（实际上可以将其他类型的密钥转换为整数）时，该值可以直接写入与密钥相对应的数组下标。对于键- 值对（1045，1），然后在数组地址1045上写入值1。这样，在搜索时，您无法根据密钥直接定位相应的值吗？这只需要一步。当钥匙值的可能范围相对较小时，我们可以做到这一点。此一步搜索操作的复杂性表示为O（1）。 o（1）并不一定意味着只需要一个步骤，可能是两，三甚至一百个步骤。这意味着该算法的复杂性与输入大小n无关。该方法最初开发了哈希表的概念，但它存在致命的问题：通常，钥匙的价值范围可能非常大，例如0到1000亿。为了节省所有可能的密钥，即使实际使用了一小部分数数，我们也需要创建一个大小为1000亿的数组。这样的方法非常耗尽内存，即使是内存容量本身也不足以构建如此大的数组。一些读者可能此时再次想到它，因此他们应该在钥匙上执行模量操作！假设数组的大小仅为100，我们将值存储在（密钥mod 100）的地址，即[键mod 100]=值。对于钥匙值（1045，1），数组地址为45（即1045 mod 100=45），并且值1在此处存储。这是否可以解决不足记忆大小的问题？但是，出现了一个新问题：两个不同的键可能对应于调节后相同的地址，而1045和2045都是调节100，这会造成冲突。实际上，当我们到达这里时，我们进入了哈希表的世界。哈希表采用类似的想法，使用哈希函数（或哈希函数）来计算每个键的哈希值，然后模拟数组的大小。由于数组的大小有限，冲突实际上会发生，而且良好的哈希功能会使冲突降低。如何解决冲突是哈希表设计中的核心问题。

解决哈希表冲突的第一个方法称为链接，其基本原理是使用数组来存储内存地址（也称为“ Pointers”）。请注意，这里的数组不存储键值对（元素），而是指向内存中某个空间的地址。真正的键值对本身存储在数组之外的其他内存区域中，它们的内存地址可能是随机的。每当添加新元素时，系统都将申请新的存储区域，以存储下一个元素的数据键，值和内存地址（即指针）。如果不存在下一个元素，则指针的内容为空，并在图2中显示为斜线。每个数组插槽的起始状态为空。由于第一个元素是在此插槽上（并存储在内存的块中），因此数组插槽本身已更新为元素所在的内存地址。如果将另一个新元素放在同一插槽上，则其指针指向插槽中的原始元素，同时让插槽本身指向新元素。因此，具有相同哈希值的元素通过这样的链结构链接。就像在快递柜中一样，每个软件包都表示下一个软件包存储的地址。基于此地址，您可以关注地图并找到下一个软件包。依此类推，这些软件包等效于“链接”。同时，我们还可以看到，如果所有元素均已在相同的插槽上进行，也就是说，使用了整个阵列中的一个插槽，则找到特定元素的复杂性为o（n）（假设总共有n个元素），因为链接的列表的长度为n，并且此时为链接方法，目前是链接方法，我们以前提到了链接搜索。这也说明了良好的哈希功能的重要性，这将使这些元素更加分散，减少冲突的频率并提高搜索效率。

图2：基于链接方法，具有相同哈希值的元素由指针链接。资料来源：《算法导论》（第四版）[5]。假设我们的哈希功能将相对均匀地散布元素，那么链接列表方法的效率有多高？首先，插入新元素相对快速，可以直接插入链结构的前部（链接列表）。该过程可以在恒定时间内完成，并表示为O（1），即操作速度不由n确定。 o（1）这里还包含计算哈希值的时间。对于搜索案例，我们考虑在两种不同情况下的时间复杂性：密钥已经存在（已成功搜索）并且不存在密钥（未成功搜索）。对于不存在密钥的情况，搜索需要穿越相应插槽的整个链接列表。此过程的速度取决于链接列表的长度。假设表中的条目或元素的总数为n，

因素）;在O（1+）时间内可以完成失败的搜索。实际上，可以证明成功搜索的复杂性也是O（1+）。这种复杂性意味着，当N和M大小相等时，O（1+）=O（1），也就是说，搜索可以在恒定时间内完成，这比上一个线性搜索中O（N）的复杂性要快得多。 （但应注意的是，这里的速度越快。当n足够大时，o（1）越快；在实际应用中，o（1）的步骤可能非常大，n的步骤很小，而N足够小。目前，线性搜索O（n）是较轻的。但是，链接方法也有其自身的问题：从记忆使用的角度来看，链接不足，链接不足。由于元素的内存位置不是连续的，并且需要额外的空间将指针存储到下一个元素上，因此访问连续的内存地址比访问随机的非贴上地址更有效。因此，在实际应用中，使用另一种方法来解决冲突，称为公开寻址，这也是我们一开始提到的新论文中讨论的主题。打开寻址的想法很简单：将数据本身直接存储在插槽中。如果我们发现已经使用了一个插槽，那么我们将暂定查看是否可以使用附近的一些插槽。如果可以使用它们，请将其放入其中。实际上，开放的寻址方法将根据某个预设规则尝试一系列位置，直到找到空位置为止。这样的位置称为探针序列。当我们想找到一个元素时，系统将根据与元素相对应的检测顺序一个一个一个搜索，直到找到元素本身或不存在为止。最简单的检测顺序是一个一个一个搜索，这也称为线性探测。另外，还有二次探测，即检测序列是检测数i的二次函数。在打开的地址中，由于数据放置在数组本身中，因此不使用其他内存空间，内存地址访问更加连续，因此更有效。早在1954年，IBM Engineer Gene Amdahl和他的同事使用了IBM 701计算机上的开放式散布表。此外，苏联计算机科学家兼编程语言的先驱安德烈·埃斯霍夫（Andrey Ershov）也独立提出了线性检测的想法。从那时起，开放式寻址已成为哈希表实现的经典方法。 1985年，Yao Qizhi提供了一个证明，无论使用哪种检测顺序，找到现有密钥的开放寻址方法的最佳时间复杂性是

这里代表载荷因子或哈希表的全载量和1。从那时起，这个结论似乎已成为学术界的共识。因此，当Krapivin拿到Hash桌子时，他设计自己是为了找到算法老师，并声称他的搜索效率比Yao Qizhi的结论更有效，他的老师持怀疑态度。

图3在1954年，IBM工程师Gene Amdahl和他的同事在IBM 701计算机上使用了打开的地址散布桌子。

开放式地址的过程以更好地解释开放式寻址的时间复杂性，我们首先解释了开放式寻址的基本操作过程，即它如何实现，获取和删除操作。正如我们之前所说，开放的寻址方法还采用一个数组，并将数据（键值对）直接存储到数组中。除了数据本身外，数组还存储每个插槽的状态，并且有三个可能的状态：“空”，“二手”和“删除”。假设数组命名为A，其大小为M，并且使用线性探测使用开放地址。 PUT和获取的实现方法如下：PUT（键，值）计算密钥的哈希值，并调节M以获得H。检查插槽a [h]，a [h+1]，a [h+2] .依次。如果插槽的状态为“空”，或“使用”状态，并且其元素的相应键与我们想要的相同，则将我们的密钥和价值写入此插槽并将其状态更新为“已使用”（如果使用原始状态，是否使用了是否需要更新），否则请继续搜索。以上过程考虑了两种情况：如果密钥已经存在，我们会发现它的插槽；如果不存在，将找到第一个空插槽。获取过程相似，也需要此搜索过程。完整的步骤如下：get（键）:计算键的哈希值，并调节m以获得h。检查插槽a [h]，a [h+1]，a [h+2]…又依次。如果插槽状态为“空”，则它将返回“找不到”；如果插槽状态被“使用”，并且其元素的相应密钥与我们想要的相同，则它将返回插槽元素的值，否则继续搜索。

注意：这里的看台和获得实现结合了成功的搜索和失败的搜索，也就是说，相同的方法可以处理键的存在和不存在密钥。在复杂性分析中，为了简化分析，我们将分别分析成功搜索和失败搜索的复杂性。

删除过程还需要搜索，并且还需要使用第三个插槽状态：“删除”。为什么不能将搜索插槽的状态直接设置为“空”？因为在使用和获取搜索元素的过程中，只要遇到空插槽，搜索结束。因此，如果删除将插槽的状态设置为空，则可能会导致元素在其之后存在，但搜索却尽早结束。换句话说，放置并获得不再正常运行，并且在某些情况下，元素实际上存在，但get操作返回不存在。如果删除将插槽的状态更新为“已删除”，则不会影响元素搜索过程和put和获得的正常操作，也就是说，在遇到“删除”后继续搜索。删除的完整步骤如下：删除（键）:计算键的哈希值，并调节M以获得H。检查插槽a [h]，a [h+1]，a [h+2]……依次，如果插槽状态为“空”，则返回“找不到”；如果“使用”插槽状态，并且其元素的相应密钥与我们正在寻找的键相同，请将插槽状态更新为“删除”，然后返回“成功删除”，否则继续搜索。最后，让我们看看一个具体的例子。假设哈希函数返回密钥本身，数组大小为100，然后我们依次执行以下操作：

put（1045，1）1045的模量为100至45，将元素写入数组插槽45，并将插槽状态更新为“使用”； put（1056，2）1056的模量为100至56，将元素写入数组插槽56，并将插槽状态更新为“使用”； put（1067，3）1067的模量为100至67，将元素写入数组插槽67，并将插槽状态更新为“使用”； PUT（2045，4）2045的模量为100至45，发现插槽45的状态已“使用”，因此跳过45；检测插槽46并发现其状态是空的，然后将元素写入数组插槽46，并将其插槽状态更新为“使用”；删除（1056）1056的模量为100至56，发现插槽56的状态被“使用”，并且存储的元素的键等于1056，则数据已成功删除，插槽状态已更新为“删除”；哈希表的状态将如下：

最后，我将为读者留下一个小练*。如果我们要操作put（3045，5），则将此元素放置在哪里？桌子状态会变成什么样？如果再次获得（3045）会发生什么？使用打开寻址的效率取决于负载因子（即表占用）和探测顺序。想象一下，如果占用表中的一半插槽，并且检测顺序将使每个插槽平均检测到平均而言，则需要两个检测才能找到一个空插槽。这有点像在停车场寻找停车位。如果50的停车位已经满，我们的搜索也是如此。平均而言，需要进行两次试验才能找到一个停车位。更广泛的是，在独立统一的置换散列的情况下，即，与每个密钥相关的检测顺序是所有哈希表索引的随机排列{0、1、2，…，…，N-1}，所有排列均匀分布，所有排列都是均匀分布的，平均检测数量的平均检测数（例如，找到一个空槽（例如，搜索或插入了新的elements）。如果负载因子平均为90，则需要10个检测。可以看出，随着负载因子接近1，所需检测的数量将*增加。因此，在实际的哈希表实现中，当负载因子超过一定阈值（常用的阈值值为2/3）时，将触发容量的扩展，即创建一个较大的表，然后将所有条目重新将所有条目重新置于新表中，以便后续插入或搜索可以固定。

[3]）。该结果意味着，当哈希表的一半已满时，成功搜索所需的平均检测数量仅为1.387；当哈希表满90时，平均检测数量仅为2.559。 Yao Qizhi在1985年的纸张统一散列中是最佳的，证明了Hash的独立和均匀排列的假设（即我们上面的结论），并且成功搜索（记录检索）所需的检测复杂性是最佳的，也就是说，无论发现现有的Hash功能和检测序列，都使用了什么，找到了现有的Hash功能和检测时间的时间，则是找到Keys的时间的复杂性。

在Krapivin等人的新论文中，作者首先回顾了这个问题的历史背景，然后得出结论：

在没有重新排序的情况下（考虑非怪兽策略），开放式解决哈希表可以实现与成功搜索和失败搜索（或插入）的时间复杂性相对应的O（1）的预期探针的相同摊销。作者还指出，为了达到比Yao Qizhi的结论较低的复杂性，非怪兽策略是关键。

对于使用贪婪策略打开解决方案的哈希表，Yao Qizhi证明了成功搜索的最佳复杂性；但是，证明了插入ZHI的猜测已被证明。我们将不再讨论本文的具体内容。想要深入了解的读者可以自己阅读。

结论计算机科学是一个充满惊喜的领域，甚至几十年前似乎完全解决的问题仍然可能掩盖未发现的真相。安德鲁·克拉平金（Andrew Krapivin）的研究提醒我们，科学进步并不总是沿着既定的曲目移动，有时有些好奇和深入思维会导致新的突破。更重要的是，这种突破不仅是高级研究人员的专利，而且本科生也可以取得——的成就。只要您有勇气挑战权威，敢于提出问题，并愿意花时间探索答案。也许下一个重写教科书的下一个发现来自您的屏幕前面！

参考文献[1]微小的指针，迈克尔·A·班德（Michael A. Bender），亚历克斯·康威（Alex Conway），马丁·法拉赫·科尔顿（MartnFarach-Colton），威廉·库斯马尔（William Kuszmaul），吉多·塔格里亚（Guido Tagliavini），2021 [2]最佳范围[2]无需重新排序的开放式寻址范围卢恩（Luhn）和哈希算法的诞生，哈拉姆·史蒂文斯（Hallam Stevens）[5]算法概论，第四版，C.L.R.S.2022年

特殊提示1。在“ Bi Pu”的微信官方帐户的底部输入“精品列”菜单，以查看有关不同主题的一系列流行科学文章。 2。“返回pu”提供了每月搜索文章的功能。遵循官方帐户并回复四位数的年+一个月，例如“ 1903”，您可以获得2019年3月的文章索引，依此类推。版权声明：欢迎个人转发。未经授权，不得复制或摘录媒体或机构的形式。要重印授权，请联系“ Bi Pu”微信官方帐户中的后端。