本科生姚期智40年前的猜想，哈希表的平均查詢時(shí)間竟與填滿程度無關(guān)

原標(biāo)題：本科生姚期智40年前的猜想，哈希表的平均查詢時(shí)間竟與填滿程度無關(guān)
文章來源：人工智能學(xué)家
內(nèi)容字?jǐn)?shù)：12679字

本科生40年計(jì)算機(jī)科學(xué)猜想

本文報(bào)道了羅格斯大學(xué)本科生Andrew Krapivin圖靈獎(jiǎng)得主姚期智40年前提出的關(guān)于哈希表猜想的故事。這一突破源于Krapivin對(duì)一篇名為“Tiny Pointers”論文的研究，他意外地發(fā)現(xiàn)了一種更快、更有效的哈希表構(gòu)建方法。

1. 哈希表與姚期智猜想

哈希表是計(jì)算機(jī)科學(xué)中廣泛使用的用于存儲(chǔ)和檢索數(shù)據(jù)的工具。其效率取決于查找元素所需的時(shí)間，這與哈希表的填充程度密切相關(guān)。姚期智在1985年的論文《Uniform Hashing Is Optimal》中提出，對(duì)于特定類型的哈希表，在最壞情況下查找元素的時(shí)間與哈希表接近滿的程度（用x表示）成正比。他認(rèn)為，均勻探測(cè)是最佳的搜索方法。

2. Krapivin的突破

Krapivin在研究“Tiny Pointers”論文的過程中，無意中設(shè)計(jì)了一種新的哈希表，其搜索時(shí)間與(log x)2成正比，遠(yuǎn)小于x。這意味著即使哈希表接近滿載，他的新哈希表也能以更快的速度查找元素。他與教授Martín Farach-Colton和卡內(nèi)基梅隆大學(xué)的William Kuszmaul合作，驗(yàn)證了這一發(fā)現(xiàn)。

3. 猜想的證偽及更深層次的發(fā)現(xiàn)

Krapivin的工作直接了姚期智的猜想，證明了(log x)2是該類別哈希表的最佳界限。更令人驚訝的是，他們還證明了姚期智關(guān)于平均查詢時(shí)間的結(jié)論對(duì)于非貪婪哈希表并不適用。他們發(fā)現(xiàn)，對(duì)于非貪婪哈希表，平均查詢時(shí)間是一個(gè)常量，與哈希表的填充程度無關(guān)，這超出了之前的預(yù)期。

4. 研究意義與影響

Krapivin的發(fā)現(xiàn)不僅了一個(gè)長(zhǎng)期存在的猜想，也為哈希表的研究帶來了新的方向。雖然其直接應(yīng)用尚不明確，但對(duì)數(shù)據(jù)結(jié)構(gòu)的更深入理解，有助于未來計(jì)算機(jī)科學(xué)的創(chuàng)新和發(fā)展。計(jì)算機(jī)科學(xué)家們對(duì)這一成果給予了高度評(píng)價(jià)，認(rèn)為它解決了經(jīng)典問題，并可能在未來帶來更多突破。

5. 結(jié)語

Krapivin的故事展現(xiàn)了意外發(fā)現(xiàn)的魅力和基礎(chǔ)研究的重要性。一位本科生在無意中了著名學(xué)者的長(zhǎng)期猜想，這不僅證明了科學(xué)探索的無限可能，也激勵(lì)著更多人投身于計(jì)算機(jī)科學(xué)領(lǐng)域的探索與創(chuàng)新。

聯(lián)系作者

文章來源：人工智能學(xué)家
作者微信：
作者簡(jiǎn)介：致力成為權(quán)威的人工智能科技媒體和前沿科技研究機(jī)構(gòu)