本科生姚期智40年前猜想，證明哈希表查詢效率可達常數(shù)級別

原標(biāo)題：本科生姚期智40年前猜想，證明哈希表查詢效率可達常數(shù)級別
文章來源：夕小瑤科技說
內(nèi)容字?jǐn)?shù)：3692字

哈希表：本科生顛覆四十年的計算機科學(xué)猜想

哈希表，作為計算機科學(xué)的基石數(shù)據(jù)結(jié)構(gòu)，其重要性不言而喻。它廣泛應(yīng)用于數(shù)據(jù)庫、網(wǎng)絡(luò)路由器以及編程語言底層實現(xiàn)等領(lǐng)域。然而，一項由羅格斯大學(xué)本科生Andrew Krapivin領(lǐng)導(dǎo)的研究，意外地顛覆了計算機科學(xué)泰斗、圖靈獎得主姚期智教授四十年前提出的一個重要猜想，引發(fā)了學(xué)術(shù)界的巨大震動。

1. 姚期智的猜想與均勻探測

1985年，姚期智教授在其論文《Uniform Hashing is Optimal》中提出一個猜想：在開放尋址哈希表中，均勻探測是解決沖突的最佳方法。然而，在負(fù)載系數(shù)較高的情況下，查詢時間的下界將線性增長，與負(fù)載系數(shù)x成正比。這意味著，當(dāng)哈希表接近飽和時，插入和查詢操作的平均時間復(fù)雜度會顯著增加。

2. Krapivin的突破性發(fā)現(xiàn)

Krapivin在閱讀一篇關(guān)于“微型指針”（Tiny Pointers）的論文后受到啟發(fā)。他意識到，更小的指針可能需要全新的數(shù)據(jù)組織策略，從而重新設(shè)計哈希表。通過巧妙的設(shè)計，他發(fā)明了一種非貪婪哈希表，其平均查詢時間竟然達到了常數(shù)級別，不受哈希表填充程度的影響！這直接挑戰(zhàn)了姚期智教授的理論。

3. 非貪婪哈希表與時間復(fù)雜度

傳統(tǒng)開放尋址哈希表的最壞情況查詢和插入時間復(fù)雜度為O(x)，其中x為負(fù)載系數(shù)。而Krapivin團隊提出的非貪婪哈希表，即使在接近滿載的情況下，其時間復(fù)雜度僅為O((log x)2)，遠優(yōu)于之前的O(x)。他們證明了，通過引入非貪婪插入策略，可以突破姚期智教授提出的O(log x)的理論下限，實現(xiàn)常數(shù)級別的平均查詢時間。

4. 學(xué)術(shù)界的驗證與震驚

Krapivin的導(dǎo)師和卡內(nèi)基梅隆大學(xué)的專家對這一發(fā)現(xiàn)進行了嚴(yán)格驗證，最終確認(rèn)了其正確性。這一結(jié)果震驚了學(xué)術(shù)界，因為哈希表是計算機科學(xué)領(lǐng)域研究最透徹的技術(shù)之一，如此重大的突破實屬罕見。 Krapivin的研究不僅了持續(xù)40年的猜想，更重塑了學(xué)界對計算最優(yōu)性的認(rèn)知。

5. 對未來研究的啟示

Krapivin的研究表明，即使在看似成熟的基礎(chǔ)算法領(lǐng)域，性能極限的邊界仍充滿未知的可能性。 他的突破性工作不僅終結(jié)了一個長達四十年的理論猜想，更重要的是，它提醒我們，那些被視為完美的經(jīng)典算法，或許正等待著被重新解構(gòu)和優(yōu)化。這為未來的計算機科學(xué)研究指明了新的方向，也展現(xiàn)了年輕一代科研人員的創(chuàng)新活力。

聯(lián)系作者

文章來源：夕小瑤科技說
作者微信：
作者簡介：低負(fù)擔(dān)解碼AI世界，硬核也可愛！聚集35萬AI發(fā)燒友、開發(fā)者和從業(yè)者，廣泛覆蓋互聯(lián)網(wǎng)大廠中高管、AI公司創(chuàng)始人和機構(gòu)投資人。一線作者來自清北、國內(nèi)外頂級AI實驗室和大廠，兼?zhèn)涿翡J的行業(yè)嗅覺和洞察深度。商務(wù)合作：zym5189