線性探測哈希表新研究成果有望讓計算機更有效地存儲和檢索數(shù)據(jù)

2021-11-22 13:27:45來源：cnBeta.COM 關(guān)鍵詞：存儲數(shù)據(jù)閱讀量：20701

導(dǎo)讀：麻省理工學(xué)院 CSAIL 一項關(guān)于線性探測哈希表的新研究成果，有望讓計算機更有效地存儲和檢索數(shù)據(jù)。

　　麻省理工學(xué)院 CSAIL 一項關(guān)于線性探測哈希表的新研究成果，有望讓計算機更有效地存儲和檢索數(shù)據(jù)。該成果由該校計算機科學(xué)博士生 William Kuszmaul 在內(nèi)的三人研究小組取得，對 1954 年推出的“線性探測哈希表”進(jìn)行了優(yōu)化。

　　“線性探測哈希表”于 1954 年推出，是當(dāng)今最古老、最簡單和最快的數(shù)據(jù)結(jié)構(gòu)之一。數(shù)據(jù)結(jié)構(gòu)提供了在計算機中組織和存儲數(shù)據(jù)的方法，而哈希表是最常用的方法之一。在線性探測哈希表中，可以存儲信息的位置是沿著一個線性陣列。

　　例如，假設(shè)一個數(shù)據(jù)庫被設(shè)計用來存儲 10000 人的身份證號碼，Kuszmaul 建議：“我們?nèi)∧愕纳矸葑C號碼x，然后計算 x 的哈希函數(shù)，h(x)，它給你一個 1 到10000之間的隨機數(shù)。下一步是拿著這個隨機數(shù) h(x)，走到數(shù)組中的那個位置，把 x，即身份證號碼，放到那個位置”。

　　Kuszmaul 說，如果已經(jīng)有東西占據(jù)了那個位置，你只需前進(jìn)到下一個空閑位置并把它放在那里。這就是“線性探測”一詞的由來，因為你一直線性地向前移動，直到找到一個空位。

　　為了以后檢索那個社會安全號碼，x，你只要去指定的位置，h(x)，如果它不在那里，你就向前走，直到你找到 x 或來到一個空閑位置，并得出結(jié)論說 x 不在你的數(shù)據(jù)庫中。

　　對于刪除一個項目，如社會安全號碼，有一個有點不同的協(xié)議。如果你在刪除信息后只是在哈希表中留下一個空位，那么當(dāng)你后來試圖尋找其他東西時就會造成混亂，因為這個空位可能會錯誤地暗示你正在尋找的項目在數(shù)據(jù)庫中無處可尋。為了避免這個問題，Kuszmaul 解釋說，你可以去元素被移除的地方，在那里放一個叫做“墓碑”(tombstone)的小標(biāo)記，表示這里曾經(jīng)有一個元素，但現(xiàn)在已經(jīng)消失了。

　　這個常規(guī)程序已經(jīng)被遵循了半個多世紀(jì)。但在所有這些時間里，幾乎所有使用線性探測哈希表的人都認(rèn)為，如果你允許它們變得太滿，長長的被占點會跑到一起形成"集群"。因此，找到一個空閑位置所需的時間會急劇上升--事實上是四倍--需要如此長的時間，以至于不切實際。因此，人們被訓(xùn)練成在低容量下操作哈希表--這種做法會影響公司必須購買和維護(hù)的硬件數(shù)量，從而造成經(jīng)濟損失。

　　該團隊還設(shè)計了一種新的策略，稱為“墓地散列”(graveyard hashing)，其中包括人為地增加放置在陣列中的墓碑?dāng)?shù)量，直到它們占據(jù)了大約一半的空閑位置。然后，這些墓碑保留了可用于未來插入的空間。

　　Kuszmaul 說，這種方法與人們習(xí)慣上被指示的做法相反，"可以導(dǎo)致線性探測哈希表的最佳性能"?；蛘?，正如他和他的合作者在他們的論文中所堅持的那樣，"精心設(shè)計的墓碑的使用可以完全改變......線性探測的行為方式。"

上一篇：利用人工智能和物聯(lián)網(wǎng)技術(shù)開發(fā)智能家居

下一篇：研究稱奇特的新材料或是兩種超導(dǎo)體的結(jié)合體具有重要的量子計算用途

我要評論

昵稱

匿名

文明上網(wǎng)，理性發(fā)言。（您還可以輸入200個字符)

表情

所有評論僅代表網(wǎng)友意見，與本站立場無關(guān)。

數(shù)字經(jīng)濟民營企業(yè)座談會在福州召開
國家數(shù)據(jù)局將深入貫徹黨中央、國務(wù)院決策部署，強化數(shù)據(jù)要素保障，深化數(shù)據(jù)資源開發(fā)利用和開放共享，推動科技創(chuàng)新和產(chǎn)業(yè)創(chuàng)新深度融合，打造具有國際競爭力的數(shù)字產(chǎn)業(yè)集群，更好激發(fā)數(shù)字經(jīng)濟創(chuàng)新活力。
數(shù)字經(jīng)濟數(shù)據(jù)
2025-05-08 09:57:33
國家數(shù)據(jù)局綜合司關(guān)于征集數(shù)據(jù)基礎(chǔ)設(shè)施建設(shè)優(yōu)秀案例的通知
為落實《國家數(shù)據(jù)基礎(chǔ)設(shè)施建設(shè)指引》（簡稱《建設(shè)指引》）工作部署，加快推進(jìn)數(shù)據(jù)基礎(chǔ)設(shè)施建設(shè)，現(xiàn)組織征集數(shù)據(jù)基礎(chǔ)設(shè)施建設(shè)優(yōu)秀案例，總結(jié)數(shù)據(jù)基礎(chǔ)設(shè)施建設(shè)經(jīng)驗，遴選推廣先進(jìn)做法，供各方借鑒參考。
數(shù)據(jù)基礎(chǔ)設(shè)施
2025-04-28 10:13:06
江波龍2024年營收175億大增72%，凈利潤翻倍
江波龍發(fā)布2024年年報，全年營收174.64億元，同比增長72.48%；凈利潤4.99億元，同比大增160.24%。公司高端存儲產(chǎn)品占比提升帶動毛利率顯著改善，企業(yè)級存儲和Lexar品牌業(yè)務(wù)成為增長新引擎。2025年將重點布局AI服務(wù)器存儲、UFS高端產(chǎn)品及海外市場拓展。
2024年業(yè)績報告存儲
2025-04-01 10:35:36
以高質(zhì)量數(shù)據(jù)促進(jìn)人工智能發(fā)展國家數(shù)據(jù)局將開展四方面工作
近期人工智能技術(shù)發(fā)展出現(xiàn)新的進(jìn)展，引發(fā)全球廣泛關(guān)注。這背后，離不開算法、算力、數(shù)據(jù)的協(xié)同創(chuàng)新。國家數(shù)據(jù)局局長劉烈宏說，高質(zhì)量數(shù)據(jù)與人工智能的結(jié)合，將會進(jìn)一步發(fā)揮數(shù)據(jù)和人工智能的倍增效應(yīng)。
人工智能數(shù)據(jù)
2025-03-30 13:52:34
煙臺：數(shù)據(jù)跨部門調(diào)用 “e拍通”跑出改革加速度
山東堅持分步實施、有序推進(jìn)，在全省范圍大力推行“免證辦事”“一碼通行”，凡是通過電子證照、數(shù)據(jù)共享可以獲取的信息，不再要求企業(yè)和群眾提供相應(yīng)材料。
電子證照數(shù)據(jù)
2025-03-11 11:45:10
聚焦物流行業(yè)發(fā)展問題開展物流數(shù)據(jù)開放互聯(lián)試點工作
隨著數(shù)字經(jīng)濟時代的到來，物流行業(yè)正經(jīng)歷著變革。數(shù)據(jù)作為新的生產(chǎn)要素，正在重塑物流行業(yè)的運營模式和價值鏈。物流業(yè)數(shù)據(jù)融合是指將來自不同來源、不同格式的物流數(shù)據(jù)進(jìn)行整合、處理和分析，以提取有價值的信息和知識的過程。
物流行業(yè)數(shù)據(jù)
2025-02-20 10:24:45

版權(quán)與免責(zé)聲明：

凡本站注明“來源：智能制造網(wǎng)”的所有作品，均為浙江興旺寶明通網(wǎng)絡(luò)有限公司-智能制造網(wǎng)合法擁有版權(quán)或有權(quán)使用的作品，未經(jīng)本站授權(quán)不得轉(zhuǎn)載、摘編或利用其它方式使用上述作品。已經(jīng)本網(wǎng)授權(quán)使用作品的，應(yīng)在授權(quán)范圍內(nèi)使用，并注明“來源：智能制造網(wǎng)”。違反上述聲明者，本站將追究其相關(guān)法律責(zé)任。

本站轉(zhuǎn)載并注明自其它來源（非智能制造網(wǎng)）的作品，目的在于傳遞更多信息，并不代表本站贊同其觀點或和對其真實性負(fù)責(zé)，不承擔(dān)此類作品侵權(quán)行為的直接責(zé)任及連帶責(zé)任。如其他媒體、平臺或個人從本站轉(zhuǎn)載時，必須保留本站注明的作品第一來源，并自負(fù)版權(quán)等法律責(zé)任。如擅自篡改為“稿件來源：智能制造網(wǎng)”，本站將依法追究責(zé)任。

鑒于本站稿件來源廣泛、數(shù)量較多，如涉及作品內(nèi)容、版權(quán)等問題，請與本站聯(lián)系并提供相關(guān)證明材料：聯(lián)系電話：0571-89719789；郵箱：1271141964@qq.com。