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

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

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

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

1. 姚期智的猜想與均勻探測(cè)

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

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

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

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

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

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

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

5. 對(duì)未來研究的啟示

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

聯(lián)系作者

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