（本文作者张晓泉配资炒股配资公司专业，清华大学经管学院 Irwin and Joan Jacobs讲席教授）
支撑现代技术几十年的假设被推翻的情况并不常见，但最近一篇基于一名本科生及其两位合著者的研究成果的论文却做到了这一点。
该研究涉及哈希表，以及20世纪80年代研究成果的一个猜想。
一个长达40年的猜想
哈希表自20世纪50年代就已存在，它是计算机科学中的基本数据结构，也是数据库、缓存系统、编译器和网络路由器等众多应用的重要构建模块。这些结构在高效存储和检索数据方面表现出色，是现代计算不可或缺的一部分。
哈希表的数据结构就像一个巨大的抽屉柜，数据被存放在某个抽屉中，并在需要时快速取出。问题在于，随着哈希表被填满，为新数据找到空位变得愈发困难，从而导致性能下降。
要理解这一点，首先要明白哈希表的填满程度是如何衡量的。研究人员通常用一个整数x来表示哈希表接近100%满的程度。
例如，如果x为100，则表示哈希表已满99%，如果x为1000，则表示已满99.9%。想象一个有1000个车位的停车场。x为100，说明990个车位已被占用，只有10个空着。这种衡量方式有助于评估诸如查询或插入等操作所需的时间。
1985年，著名计算机科学家及图灵奖得主姚期智提出了一个猜想，该猜想对几乎填满的哈希表找到空位的速度设定了一个限制。
他认为，对于某些常见的哈希表，最坏情况下的插入操作（填满最后一个空位）的预期时间与“x”成正比。换句话说，在特定属性的哈希表中，找到单个元素或空位的最佳方法是随机遍历潜在空位，这种方法叫做均匀探测（uniform probing）。
在停车场例子中，如果x为1000（停车场已满99.9%），那么平均而言，找到那个唯一的空位会花费相当长的时间。
姚期智的猜想表明，这种x与搜索时间之间的线性关系是此类插入操作的最佳速度。几十年来，几乎没有人对此提出质疑。
直到有人因为不知道这一猜想，意外地实现了突破。
偶然地突破
这一突破源于一名叫做Andrew Krapivin的本科生偶然看到了一篇名为《Tiny Pointers》的论文，讲的是一种旨在压缩指针以减少内存消耗的概念。
计算机系统中的传统指针通常使用固定数量的位来表示内存地址。然而，微型指针采用了一种巧妙的技术来减少所需的位数，从而节省内存空间。这在Krapivin的创新中起着关键作用。
要理解微型指针的工作原理，可以设想多个用户共享一个数据数组的情况。
每个用户都可以请求数组中的一个位置，而微型指针用于跟踪已分配的位置。微型指针并不直接存储完整的内存地址，而是利用知道哪个用户“拥有”该指针以及数组的结构，用更少的位来表示位置。
这就好比为一个特定位置设定了一个简化的代码或昵称，而这个代码或昵称只有在特定上下文中才有意义。
指针大小的缩减意味着显著的内存节省，尤其是在大量使用指针的应用中。
为了进一步探索内存的优化，Krapivin深入研究了哈希表，试图找到一种更高效的方式来组织这些指针所指向的数据。
这一探索促使他开发出了一种新颖的哈希表设计，其性能超乎寻常，在数据查找和存储方面展现出了前所未有的速度。
具体来说，Krapivin开发了一种采用开放寻址法的新型哈希表，将所有元素都直接存储在哈希表本身中。这与分离链接法形成了鲜明对比，在分离链接法中，具有相同哈希键的元素存储在一个链表中。
与依赖统一探测不同，Krapivin的哈希表采用了一种更复杂的策略，包括子数组的使用以及特定的插入规则。
其基本思路是将哈希表划分为更小的子数组，并使用一组规则来确定新元素的插入位置。这些规则优先考虑平衡元素在子数组之间的分布，这有助于最大限度地减少未来插入和搜索所需的时间。这种“非贪婪”的方法，虽然早期插入的成本可能略高，但后期插入和搜索的速度却明显加快，尤其是当哈希表逐渐填满时。
Krapivin的哈希表实现了最坏情况下的查询和插入时间与(log x)²成正比，比x要快得多。
这一突破最大的意义在于，Krapivin的研究并非只是渐进式的改进；而是从根本上挑战了我们对于哈希表如何设计和优化的理解。通过推翻姚氏猜想，他为数据结构和算法的研究开辟了新的途径，未来可能会带来更高效的解决方案。
影响与应用
Krapivin的突破对利用哈希表的各种应用具有深远的影响。这一创新可能产生重大影响的一些关键领域包括：
数据库：哈希表在数据库中被广泛用于索引和检索数据。Krapivin的发现可能会加快查询处理速度，并提升数据库的整体性能。
缓存系统：缓存依靠哈希表来高效地存储和检索频繁访问的数据。Krapivin的哈希表带来的速度提升可能会使网络浏览器、操作系统和内容分发网络的加载时间更快，从而改善用户体验。
编译器：编译器使用哈希表进行符号表管理，这涉及存储和检索有关变量、函数和其他程序元素的信息。更快的哈希表有可能加快编译过程，特别是对于大型程序而言。这在软件开发中尤其有益，因为编译时间可能是影响生产力的一个重要因素。
网络路由：哈希表在网络路由器中用于高效转发数据包。Krapivin的工作有助于加快路由决策并提升网络性能。在高流量网络中，采用更快哈希表的路由器能够更快地决定将数据包发送到何处，从而降低延迟并提高整体网络速度。
密码学：哈希表被用于各种密码学算法中，例如用于数字签名和安全通信的算法。更快的哈希表所提供的效率提升有可能增强这些算法的性能，从而加快加密和解密的过程。
尽管Krapivin的研究成果令人振奋，但要全面了解这一突破的范围和潜力，还需要进一步的研究和验证。研究人员目前正在探索这一发现的更广泛影响，并研究其在不同领域的适用性。包括探索在其他数据结构和算法中使用微型指针，以及针对特定应用优化Krapivin的哈希表。
Krapivin的创新性研究，表明了科学研究有时候需要一种「无知」的探索精神与好奇心，所谓的「标准答案」或「正确解法」可能成为创新的桎梏，而「无畏」的探索反而能够能刺破认知的茧房。正如爱因斯坦所言：“想象力比知识更重要。”
如今的AI行业也是如此，都在研究大语言模型，都知道尺度定律（Scaling Law）的存在，于是科技巨头们专注于砸钱、堆芯片、比参数、拼算力，而DeepSeek另辟蹊径实现弯道超车，虽然没有完全颠覆尺度定律，但也说明了方法创新的重要性。
在遇到瓶颈或接近极限时，跳出路径依赖，也许能找到新的解法。改变游戏规则，才能提供另一种选项。
未来，当更多研究者敢于质疑“不可逾越”的极限时，我们或许会发现：那些曾被奉为圭臬的“真理”，不过是等待被刷新的起点。
本文仅代表作者观点。
张晓泉
相关阅读
李彦宏“推翻过去”背后：百度业绩承压，智能云成增长亮点一切为了用户增长。
596 02-18 18:34
蔚来马麟回应“券商猜想”：纯属虚构！蔚来马麟回应“券商猜想”：纯属虚构！
16 01-18 21:19
AI制药：革新医药产业，引领未来健康之路AI制药行业正展现出前所未有的广阔发展前景，其重要性及影响力在医药领域内日益凸显。通过整合大数据与机器学习算法，AI制药正全面推动药物研发流程的加速，为医药产业的革新与发展注入了新的活力。
21 01-15 14:22
经典再现，音乐剧《悲惨世界》23年后重返上海2025年11月4日至12月28日，该剧将重访上海大剧院。
235 2024-12-24 20:45
叙反对派武装发表电视声明：已进入大马士革并推翻阿萨德政权据媒体8日报道配资炒股配资公司专业，叙利亚国家军队说，叙总统巴沙尔·阿萨德政权已经结束。
161 2024-12-08 14:25 一财最热 点击关闭文章为作者独立观点，不代表联华证券_实盘炒股配资_专业配资股票平台观点
