彻底改变哈希表：一名本科生的突破

哈希表是计算机科学中的基本数据结构，是从数据库和缓存系统到编译器和网络路由器等各种应用程序的基本构建块。这些结构擅长有效地存储和检索数据，使其在现代计算中不可或缺。最近，安德鲁·克拉皮文 (Andrew Krapivin) 的开创性工作为哈希表领域注入了活力，挑战了长期以来的假设，为新的效率时代铺平了道路。

突破的起源

Krapivin 的旅程始于对“小指针”的探索，这一概念旨在压缩指针以最大限度地减少内存消耗。计算机系统中的传统指针通常使用固定数量的位来表示内存地址。然而，微小指针采用了一种巧妙的技术来减少所需的位数，从而节省内存空间。如中所述，微小指针通过利用有关指针“所有者”及其使用上下文的信息来实现此目的。这使得它们能够用比传统指针更少的位来表示相同的内存位置。

为了实现这一目标，克拉皮文深入研究了哈希表领域，寻求一种更有效的方法来组织这些指针所指向的数据。这种探索促使他开发了一种新颖的哈希表设计，这种设计超出了预期，在定位和存储数据方面表现出了前所未有的速度。具体来说，Krapivin 开发了一种采用开放寻址的新型哈希表，其中所有元素都直接存储在哈希表本身中。这与单独链接相反，其中具有相同哈希键的元素存储在链接列表中。

挑战长期以来的信念

Krapivin 工作的一个关键方面涉及挑战 Andrew Yao 在 1985 年提出的长期猜想。 Yao 的猜想集中于称为“贪婪”散列表的特定类别的散列表，该散列表尝试将新元素插入表中的第一个可用槽中。这些哈希表优先考虑在插入过程中快速查找空槽，即使这意味着可能会增加将来插入或搜索所需的时间。姚的猜想认为，在这些具有某些属性的贪婪哈希表中，找到元素或空位的最有效方法是通过随机搜索，称为均匀探测。然而，克拉皮文的研究证明了他的新哈希表不依赖统一探测，从而实现了显着更快的搜索时间，从而反驳了这一猜想。

要了解这一突破的重要性，了解如何测量哈希表的“完整度”至关重要。研究人员经常使用一个整数（用“x”表示）来表示哈希表接近 100% 满的程度。例如，如果 x 为 100，则表已满 99%，如果 x 为 1,000，则表已满 99.9%。想象一个有 1,000 个停车位的停车场。如果“x”为 100，则表示 990 个空间已被占用，只有 10 个空间为空。此度量有助于评估执行查询或插入等操作所需的时间。

对于某些常见的哈希表，进行最坏情况插入（填充最后剩余位置）的预期时间与“x”成正比。在我们的停车场类比中，如果“x”为 1,000（意味着停车场已满 99.9%），则平均需要相当长的时间才能找到剩余的空位。 Yao 的猜想表明，“x”和搜索时间之间的这种线性关系是此类插入的最佳速度。然而，Krapivin 的哈希表实现了与 (log x)^2 成正比的最坏情况查询和插入时间，这比“x”快得多。这意味着即使在几乎满了的停车场，克拉皮文的方法也会比以前想象的更快地找到空位。

Krapivin 的哈希表没有依赖统一的探测，而是采用了一种更复杂的方法，涉及使用子数组和特定的插入规则 [4]。基本思想是将哈希表划分为更小的子数组，并使用一组规则来确定在何处插入新元素。这些规则优先考虑平衡子数组中元素的分布，这有助于最大限度地减少未来插入和搜索所需的时间。这种“非贪婪”方法（早期插入可能会稍微昂贵一些）通过使以后的插入和搜索速度显着加快而得到回报，特别是当哈希表填满时。

小指针：效率的关键

“微小指针”的概念在克拉皮文的创新中发挥着举足轻重的作用。这些指针本质上是压缩指针，使用更少的数据来表示相同的概念，从而减少内存消耗[4]。通过将微小指针融入到哈希表的设计中，Krapivin 能够提高所有关键操作的性能 [4]。

为了说明微小指针的工作原理，请考虑多个用户共享数据数组的场景。每个用户都可以请求数组中的一个位置，并且使用一个小指针来跟踪分配的位置。小指针不是直接将完整的内存地址存储在指针中，而是利用哪个用户“拥有”指针和数组结构的知识来用更少的位来表示位置。这类似于特定位置的缩短代码或昵称，仅在特定上下文中有意义。

指针大小的减少意味着显着的内存节省，特别是在使用大量指针的应用程序中。在克拉皮文的哈希表中，微小的指针用于链接子数组内的元素，进一步提高了结构的效率。

影响和应用

这一突破对于利用哈希表的各种应用程序具有深远的影响。这项创新可能产生重大影响的一些关键领域包括：

数据库：哈希表广泛用于数据库中用于索引和检索数据。 Krapivin 的发现可能会导致更快的查询处理并提高整体数据库性能。例如，在拥有数百万条记录的大型数据库中，使用 Krapivin 的哈希表进行索引可以显着减少检索特定记录所需的时间，从而加快数据库查询的响应时间。
缓存系统：缓存依靠哈希表来有效地存储和检索经常访问的数据。 Krapivin 哈希表提供的增强速度可以缩短加载时间并改善 Web 浏览器、操作系统和内容交付网络的用户体验。例如，在网络浏览器中，具有 Krapivin 哈希表的缓存可以更有效地存储经常访问的网站数据，从而加快这些网站的加载时间。
编译器：编译器使用哈希表进行符号表管理，其中涉及存储和检索有关变量、函数和其他程序元素的信息。更快的哈希表可能会加快编译过程，特别是对于大型程序。这对于软件开发尤其有利，因为编译时间可能是生产力的一个重要因素。
网络路由：网络路由器中使用哈希表来有效地转发数据包。 Krapivin 的工作有助于加快路由决策并提高网络性能。在高流量网络中，使用 Krapivin 哈希表的路由器可以更快地决定将数据包发送到何处，从而减少延迟并提高整体网络速度。
密码学：哈希表用于各种密码算法，例如用于数字签名和安全通信的算法。 Krapivin 哈希表提高的效率可能会增强这些算法的性能，从而加快加密和解密过程。

进一步研究和验证

虽然克拉皮文的发现引起了相当大的兴奋，但还需要进一步的研究和验证才能充分了解这一突破的范围和潜力。研究人员目前正在探索这一发现的更广泛的影响，并研究其在不同领域的适用性。这包括探索微小指针在其他数据结构和算法中的使用，以及针对特定应用优化 Krapivin 的哈希表。

结论

Andrew Krapivin 在哈希表方面的工作代表了计算机科学的重大飞跃。通过挑战长期以来的猜想并利用“小指针”的概念，他在这些基本数据结构中解锁了新的效率水平。这一突破有可能彻底改变依赖哈希表的各种应用程序，为更快、更高效的计算系统铺平道路。

克拉皮文的研究不仅仅是渐进式的改进；它从根本上挑战了我们对如何设计和优化哈希表的理解。通过反驳姚的猜想，他为数据结构和算法的研究开辟了新的途径，有可能在未来带来更有效的解决方案。这项工作体现了创新思维的力量以及质疑计算机科学中既定假设的重要性。

关于研究员

这一突破的幕后策划者安德鲁·克拉皮文(Andrew Krapivin)目前是剑桥大学的研究生。他在罗格斯大学读本科时就开始了这项研究，并得到了马丁·法拉赫-科尔顿教授的指导。克拉皮文卓越的才华和奉献精神为他赢得了多项荣誉，包括丘吉尔奖学金和戈德华特奖学金。他与 Martín Farach-Colton 和 William Kuszmaul 合作进行的哈希表工作证明了他的聪明才智以及他为计算机科学领域做出重大贡献的潜力。

参考

原文： https://atlassc.net/2025/02/12/revolutionizing-hash-tables-an-undergraduate-s-breakthrough