侵權投訴

關于哈希表沖突解決策略解析

39度創意研究所 ? 2020-10-10 15:57 ? 次閱讀

哈希是一種通過對數據進行壓縮, 從而提高效率的一種解決方法,但由于哈希函數有限,數據增大等緣故,哈希沖突成為數據有效壓縮的一個難題。本文主要介紹哈希沖突、解決方案,以及各種哈希沖突的解決策略上的優缺點。

一、哈希表概述

哈希表的哈希函數輸入一個鍵,并向返回一個哈希表的索引??赡艿逆I的集合很大,但是哈希函數值的集合只是表的大小。

哈希函數的其他用途包括密碼系統、消息摘要系統、數字簽名系統,為了使這些應用程序按預期工作,沖突的概率必須非常低,因此需要一個具有非常大的可能值集合的散列函數。

密碼系統:給定用戶密碼,操作系統計算其散列,并將其與存儲在文件中的該用戶的散列進行比較。(不要讓密碼很容易被猜出散列到相同的值)。

消息摘要系統:給定重要消息,計算其散列,并將其與消息本身分開發布。希望檢查消息有效性的讀者也可以使用相同的算法計算其散列,并與發布的散列進行比較。(不要希望偽造消息很容易,仍然得到相同的散列)。

這些應用的流行哈希函數算法有:

md5 : 2^128個值(找一個沖突鍵,需要哈希大約2 ^ 64個值)

sha-1:2^160個值(找一個沖突鍵,需要大約2^80個值)

二、哈希沖突

來看一個簡單的實例吧,假設采用hash函數:H(K) = K mod M,插入這些值:217、701、19、30、145

H(K) = 217 % 7 = 0

H(K) = 701 % 7 = 1

H(K) = 19 % 7 = 2

H(K) = 30 % 7 = 2

H(K) = 145 % 7 = 5

上面實例很明顯 19 和 30 就發生沖突了。

三、沖突解決策略

除非您要進行“完美的散列”,否則必須具有沖突解決策略,才能處理表中的沖突。

同時,該策略必須允許查找,插入和刪除正確運行的操作!

沖突解決技術可以分為兩類:開散列方法( open hashing,也稱為拉鏈法,separate chaining )和閉散列方法( closed hashing,也稱為開地址方法,open addressing )。這兩種方法的不同之處在于:開散列法把發生沖突的關鍵碼存儲在散列表主表之外,而閉散列法把發生沖突的關鍵碼存儲在表中另一個槽內。

下面介紹業內比較流行的hash沖突解決策略:

線性探測(Linear probing)

雙重哈希(Double hashing)

隨機散列(Random hashing)

分離鏈接(Separate chaining)上面線性探測、雙重哈希、隨機散列都是閉散列法,而分離鏈接則是開散列法。

1、線性探測(Linear probing)

插入一個值

使用散列函數H(K)在大小為M的表中插入密鑰K時:

設置 indx = H(K)

如果表位置indx已經包含密鑰,則無需插入它。Over

否則,如果表位置indx為空,則在其中插入鍵。Over

其他碰撞。設置 indx =(indx + 1)mod M.

如果 indx == H(K),則表已滿!就只能做哈希表的擴容了因此,線性探測基本上是在發生碰撞時對空槽進行線性搜索。

優點:易于實施;總是找到一個位置(如果有);當表不是很滿時,平均情況下的性能非常好。

缺點:表的相鄰插槽中會形成“集群”或“集群”鍵;當這些簇填滿整個陣列的大部分時,性能會嚴重下降,因為探針序列執行的工作實際上是對大部分陣列的窮舉搜索。

簡單例子

如哈希表大小M = 7, 哈希函數:H(K) = K mod M。插入這些值:701, 145, 217, 19, 13, 749

H(K) = 701 % 7 = 1

H(K) = 145 % 7 = 5

H(K) = 217 % 7 = 0

H(K) = 19 % 7 = 2

H(K) = 13 % 7 = 1(沖突) --》 2(已經有值) --》 3(插入位置3)

H(K) = 749 % 7 = 2(沖突) --》 3(已經有值) --》 4(插入位置4)

可見,如果哈希表如果不是很大,隨著數據插入,沖突也會組件發生,探針遍歷次數將會逐漸變低,檢索過程也就成為窮舉。

檢索一個值

如果使用線性探測將鍵插入表中,則線性探測將找到它們!

當使用散列函數 H(K)在大小為N的表中搜索鍵K時:

設置 indx = H(K)

如果表位置indx包含鍵,則返回FOUND。

否則,如果表位置 indx 為空,則返回NOT FOUND。

否則設置 indx =(indx + 1)modM。

如果 indx == H(K),則返回NOT FOUND。就只能做哈希表的擴容了問題:如何從使用線性探測的表中刪除鍵?

能否進行“延遲刪除”,而只是將已刪除密鑰的插槽標記為空?

很明顯,在線性探測很難做到,如果把位置置為空,那么如果后面的值也是哈希沖突,線性探測插入,則再也無法遍歷這些值了。

2、雙重哈希(Double hashing)

線性探測沖突解決方案會導致表中出現簇,因為如果兩個鍵發生碰撞,則探測到的下一個位置對于這兩個鍵都是相同的。

雙重哈希的思想:使偏移到下一個探測到的位置取決于鍵值,因此對于不同的鍵可以不同。

需要引入第二個哈希函數 H 2(K),用作探測序列中的偏移量(將線性探測視為 H 2(K)== 1 的雙重哈希)。

對于大小為 M 的哈希表,H 2(K)的值應在 1到M-1 的范圍內;如果M為質數,則一個常見選擇是 H2(K)= 1 +((K / M)mod(M-1))。

然后,用于雙哈希的插入算法為:

設置 indx = H(K); offset = H 2(K)

如果表位置indx已經包含密鑰,則無需插入它。Over

否則,如果表位置 indx 為空,則在其中插入鍵。Over

其他碰撞。設置 indx =(indx + offset)mod M.

如果 indx == H(K),則表已滿!就只能做哈希表的擴容了

哈希表為質數情況,雙重hash在實踐中非常有效

雙重 Hash 也見:https://blog.csdn.net/chenxuegui1234/article/details/103454285

3、隨機散列(Random hashing)

與雙重哈希一樣,隨機哈希通過使探測序列取決于密鑰來避免聚類。

使用隨機散列時,探測序列是由密鑰播種的偽隨機數生成器的輸出生成的(可能與另一個種子組件一起使用,該組件對于每個鍵都是相同的,但是對于不同的表是不同的)。

然后,用于隨機哈希的插入算法為:

創建以 K 為種子的 RNG。設置indx = RNG.next() mod M。

如果表位置 indx 已經包含密鑰,則無需插入它。Over

否則,如果表位置 indx 為空,則在其中插入鍵。Over

其他碰撞。設置 indx = RNG.next() mod M.

如果已探測所有M個位置,則放棄。就只能做哈希表的擴容了。

隨機散列很容易分析,但是由于隨機數生成的“費用”,它并不經常使用。雙重哈希在實踐中還是經常被使用。

4、分離鏈接(Separate chaining)

在具有哈希函數 H(K)的表中插入鍵K時

設置 indx = H(K)

將關鍵字插入到以 indx 為標題的鏈接列表中。(首先搜索列表,以避免重復。)

在具有哈希函數H(K)的表中搜索鍵K時

設置 indx = H(K)

使用線性搜索在以 indx 為標題的鏈表中搜索關鍵字。

使用哈希函數 H(K)刪除表中的鍵K時

設置 indx = H(K)

刪除鏈接列表中以 indx 為標題的鍵

優點:隨著條目數量的增加,平均案例性能保持良好。甚至超過M;刪除比開放地址更容易實現。

缺點:需要動態數據,除數據外還需要存儲指針,本地性較差,導致緩存性能較差。

很明顯,Java7 的 HashMap 就是一種分裂鏈接的實現方式。

分離鏈哈希分析

請記住表的填充程度的負載系數度量:α = N / M。

其中M是表格的大小,并且 N 是表中已插入的鍵數。

通過單獨的鏈接,可以使 α》 1 給定負載因子α,我們想知道在最佳,平均和最差情況下的時間成本。

成功找到

新鍵插入和查找失?。ㄟ@些相同),最好的情況是O(1),最壞的情況是O(N)。讓我們分析平均情況

分裂鏈接的平均成本

假設負載系數為 α = N / M 的表

在M個鏈接列表中總共分配了N個項目(其中一些可能為空),因此每個鏈接列表的平均項目數為:

如果查找/插入失敗,則必須窮舉搜索表中的鏈表之一,并且表中鏈表的平均長度為α。因此,使用單獨鏈接進行插入或不成功查找的比較平均次數為

成功查找后,將搜索包含目標密鑰的鏈接列表。除目標密鑰外,該列表中平均還有(N-1)/ M個密鑰;在找到目標之前,將平均搜索其中一半。因此,使用單獨鏈接成功找到的比較平均次數為

當α《1時,它們分別小于1和1.5。并且即使當α超過1時,它們仍然是O(1),與N無關。

四、開散列方法 VS 閉散列方法

如果將鍵保留為哈希表本身中的條目,則可以使用線性探測,雙重和隨機哈希。.. 這樣做稱為“開放式尋址”,也稱為“封閉式哈?!?。

另一個想法:哈希表中的條目只是指向鏈表(“鏈”)頭部的指針;鏈接列表的元素包含鍵。.. 這稱為“單獨鏈接”,也稱為“開放式哈?!?。

通過單獨的鏈接,沖突解決變得容易:只要在其鏈表中插入一個鍵,就可以將其插入(為此,可以使用比鏈表更高級的數據結構;但是正如我們將看到的,鏈表在一般情況下效果很好)。

讓下面我們看一下這些策略的時間成本。

開放式地址哈希分析

分析哈希表“查找”或“插入”性能時,一個有用的參數是負載系數 α = N / M。

其中 M 是表格的大小,并且 N 是表中已插入的鍵數負載系數是表滿度的一種度量。

給定負載因子 α ,我們想知道在最佳,平均和最差情況下的時間成本。

成功找到

對所有鍵,最好的情況是O(1),最壞的情況是O(N),新鍵插入和查找失?。ㄟ@些相同),所以讓我們分析平均情況。

我們將給出隨機哈希和線性探測的結果。實際上,雙重哈希類似于隨機哈希;

平均不成功的查找/插入成本

假定負載系數為α= N / M的表??紤]隨機散列,因此聚類不是問題。每個探針位置是隨機且獨立生成的對于每個探針,找到空位置的可能性為(1-α)。查找空位置將停止查找或插入,這是一個伯努利過程,成功概率為(1-α)。該過程的預期一階到達時間為 1 /(1-α)。所以:

使用隨機哈希進行插入或不成功查找的探針的平均數量為

使用線性探測時,探頭的位置不是獨立的。團簇形成,當負載系數高時會導致較長的探針序列??梢宰C明,用于線性探測的插入或未成功發現的探針的平均數量約為

當 α 接近1時,這些平均案例時間成本很差,僅受M限制;但當 α 等于或小于7.75(與M無關)時,效果還不錯(分別為4和8.5)

平均成功查找成本

假定負載系數為 α= N / M 的表??紤]隨機散列,因此聚類不是問題。每個探針位置是隨機且獨立生成的。

對于表中的鍵,成功找到它所需的探針數等于將其插入表中時所采用的探針數。每個新密鑰的插入都會增加負載系數,從0開始到α。

因此,通過隨機散列成功發現的探測器的平均數量為

通過線性探測,會形成簇,從而導致更長的探針序列??梢宰C明,通過線性探測成功發現的平均探針數為

當α接近1時,這些平均案例時間成本很差,僅受M限制;但當α等于或小于7.75時好(分別為1.8和2.5),與M無關。
編輯:hfy

收藏 人收藏
分享:

評論

相關推薦

哈希算法到底是什么?它又是如何運行的?

哈希就是將不同的輸入映射成獨一無二的、固定長度的值(又稱 "哈希值"),是最常見的軟件運算之一。很多....
的頭像 算法與數據結構 發表于 06-28 11:02 ? 603次 閱讀
哈希算法到底是什么?它又是如何運行的?

區塊鏈科普:哈希函數算法

哈希值和哈希函數的概念是初次入門區塊鏈的人常聽到的兩個關鍵詞,而且似乎對安全性來說特別關鍵。(實際上....
的頭像 如意 發表于 06-28 09:25 ? 544次 閱讀
區塊鏈科普:哈希函數算法

哈希函數的概念及結構解析

簡言之,就是設定某一固定函數(hashFunc),通過此函數來使插入元素的值與元素位置相對應,往后我....
發表于 03-11 10:00 ? 303次 閱讀
哈希函數的概念及結構解析

區塊鏈意味著真理?

區塊鏈技術的用途遠不止是作為一種加密貨幣使用,比如比特幣、以太坊(Ethereum)或瑞波幣(rip....
發表于 03-07 14:15 ? 123次 閱讀
區塊鏈意味著真理?

什么是哈希值該如何在區塊鏈中應用

哈希值是將任意長度的輸入字符串轉換為密碼并進行固定輸出的過程。哈希值不是一個“密碼”,我們不能通過解....
發表于 02-11 17:25 ? 461次 閱讀
什么是哈希值該如何在區塊鏈中應用

區塊鏈技術中的哈希函數解析

哈希函數是一種從任何一種數據中創建小的數字指紋的方法。哈希函數把消息或數據壓縮成摘要,使得數據量變小....
發表于 11-27 11:06 ? 282次 閱讀
區塊鏈技術中的哈希函數解析

區塊鏈中的哈希函數你有沒有了解清楚

這數學變換不是任意變換都能被稱之為哈希函數,一個數學變換要升級為哈希函數必須符合三個條件:唯一性、單....
發表于 11-27 09:22 ? 206次 閱讀
區塊鏈中的哈希函數你有沒有了解清楚

哈希函數的特性以及比特幣挖礦的技術原理解析

哈希函數不用知道輸入信息代表的是什么意思,也無所謂信息的長度有多長,只要輸入hash函數出來的都是固....
發表于 10-12 10:49 ? 1132次 閱讀
哈希函數的特性以及比特幣挖礦的技術原理解析

比特幣中的哈希函數是如何工作的

哈希函數是一個只能在一個方向上計算的函數,這保證了區塊鏈世界的清晰性和安全性。這也意味著,如果我們輸....
發表于 10-08 11:46 ? 489次 閱讀
比特幣中的哈希函數是如何工作的

閃電網絡通過形式化驗證結果表明和比特幣一樣安全

迄今為止,閃電網絡尚未在數學上進行過正式的安全測試,這一測試可以建立一個計算機系統在數學上的安全程度....
發表于 09-24 10:29 ? 195次 閱讀
閃電網絡通過形式化驗證結果表明和比特幣一樣安全

比特幣的全網算力上周五超過每秒80EH達到了歷史最高水平

上升的哈希率也意味著網絡更安全,更不容易受到51%的攻擊。計算密集度越高的哈希函數同時被計算,你需要....
發表于 09-04 11:08 ? 241次 閱讀
比特幣的全網算力上周五超過每秒80EH達到了歷史最高水平

Shabal算法的優點和缺點解析

Shabal算法是一種很慢的算法,允許輸入任意長度的有序位序列,甚至是一個空序列。也適應任何長度的字....
發表于 08-16 11:38 ? 1174次 閱讀
Shabal算法的優點和缺點解析

如何使用超級計算機進行比特幣挖礦

超級計算機與比特幣礦機的需求不同,因為他們必須解決其他任務。對于專業的比特幣礦機,使用所謂的ASIC....
發表于 08-15 11:04 ? 752次 閱讀
如何使用超級計算機進行比特幣挖礦

基于一種集去中心化分布式和點對點方法的共享數據協議IPFS介紹

IPFS是實現高吞吐量,低延遲和有效數據分發的通信協議的正確融合之一,它還具有去中心化和高度安全的優....
發表于 06-26 11:31 ? 550次 閱讀
基于一種集去中心化分布式和點對點方法的共享數據協議IPFS介紹

區塊鏈是如何保持數據一致性的

Hash,一般翻譯做“散列”,也有直接音譯為“哈?!钡?,就是把任意長度的輸入(又叫做預映射, pre....
發表于 06-11 14:08 ? 1026次 閱讀
區塊鏈是如何保持數據一致性的

區塊鏈中的不變性是什么意思

如何更好地理解它呢?我們可以將其與谷歌電子表格進行比較。后者具有行和列,您可以隨時添加、編輯或刪除這....
發表于 04-06 09:00 ? 185次 閱讀
區塊鏈中的不變性是什么意思

PoW區塊的確認過程介紹

對于比特幣協議的一個常見擴展是修改其共識機制,使用部分或者完全的權益證明(PoS)或者使用一個權益(....
發表于 03-26 10:32 ? 681次 閱讀
PoW區塊的確認過程介紹

為什么哈希在區塊鏈中如此重要

SHA-1是美國政府Capstone項目的一部分。該算法的最初規范——現在通常稱為SHA-0——由美....
發表于 03-21 13:51 ? 729次 閱讀
為什么哈希在區塊鏈中如此重要

哈希函數的特點及應用介紹

換句話說,哈希函數的回傳結果(稱之為hash value),是一個長度一致,但是數據內容卻是獨一無二....
發表于 03-19 15:25 ? 5928次 閱讀
哈希函數的特點及應用介紹

跨鏈技術將加速驅動區塊鏈應用的真正落地

“共識機制是區塊鏈技術的核心與靈魂,它的演變過程也正是區塊鏈技術的發展過程。從PoW到PoS的演變是....
發表于 03-15 10:26 ? 771次 閱讀
跨鏈技術將加速驅動區塊鏈應用的真正落地

比特幣的基本術語解釋

是一個函數,它使用一個加密鑰匙,把一條信息轉化成一串不可閱讀的看似隨機的字符串,這個流程也是不可逆的....
發表于 03-12 10:19 ? 385次 閱讀
比特幣的基本術語解釋

基于Ulam共識的區塊鏈將是下一代區塊鏈的標準

Ulam是根據節點的幸運值來決定挖礦概率的,不需要進行hash值的計算。每個節點根據幸運值的大小,決....
發表于 03-05 13:46 ? 1150次 閱讀
基于Ulam共識的區塊鏈將是下一代區塊鏈的標準

區塊鏈和數據結構有什么不同

如果我們考慮到目前為止我們對區塊鏈的了解,我們可以說區塊鏈是非常復雜的。然而,歸根結底,它們并沒有那....
發表于 02-26 11:51 ? 860次 閱讀
區塊鏈和數據結構有什么不同

為什么區塊鏈在不同行業中越來越流行被用來改進數據完整性

區塊鏈可能是將數據完整性提高到最高標準的解決方案。通過設計,區塊鏈能夠抵抗數據的修改。區塊鏈分類賬是....
發表于 02-25 11:12 ? 165次 閱讀
為什么區塊鏈在不同行業中越來越流行被用來改進數據完整性

區塊鏈系統中采用密碼學技術是否存在安全威脅

量子計算與區塊鏈是當下兩個熱門技術,二者因為密碼學技術聯系在一起。區塊鏈使用密碼學技術保障系統安全,....
發表于 01-10 14:51 ? 306次 閱讀
區塊鏈系統中采用密碼學技術是否存在安全威脅

如何使用HSM提高區塊鏈錢包的安全性

HSM是一種保護和管理數字密鑰的物理設備或云服務——促進加密、解密、簽名和驗證。HSM背后的動機是提....
發表于 01-10 14:22 ? 405次 閱讀
如何使用HSM提高區塊鏈錢包的安全性

區塊鏈RSA累加器批處理技術解析

自1994年以來,累加器便成為了學術界非常關注的一個話題。其類似于默克爾樹(Merkle Tree)....
發表于 01-09 10:54 ? 868次 閱讀
區塊鏈RSA累加器批處理技術解析

什么是容量挖礦的證明

工作量證明和容量證明都需要使用哈希函數。哈希函數是單向函數,這意味著輸入信息并計算哈希值很容易,但獲....
發表于 01-08 10:29 ? 336次 閱讀
什么是容量挖礦的證明

數字貨幣錢包和硬分叉之間有著怎樣的關聯

數字貨幣錢包按秘鑰由來可以分為兩類。第一類是非確定錢包,以比特幣錢包為例,每個秘鑰都是根據不同的隨機....
發表于 12-17 11:47 ? 1373次 閱讀
數字貨幣錢包和硬分叉之間有著怎樣的關聯

比特幣私鑰公鑰和地址在轉賬中的作用

橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立....
發表于 12-06 13:57 ? 2023次 閱讀
比特幣私鑰公鑰和地址在轉賬中的作用

加密哈希函數與加密貨幣有什么聯系

更具體地講就是,提取任意長度的字母序列作為輸入——我們將其稱為string——然后返回一個固定長度的....
發表于 12-06 11:48 ? 270次 閱讀
加密哈希函數與加密貨幣有什么聯系

隨機性在區塊鏈中的作用

隨機性在隱私技術和密碼學中發揮著重要作用。值得驚嘆的是通過一個隨機值與一條信息就能提供一種簡單而強大....
發表于 10-10 11:35 ? 1012次 閱讀
隨機性在區塊鏈中的作用

哈希函數中的數字簽名技術

回首近幾年,我有幸經歷了兩個相互沖突、卻又令人著迷的時代潮流變遷。第一個潮流變遷是:專家學者們耗費四....
發表于 09-29 11:31 ? 1435次 閱讀
哈希函數中的數字簽名技術

哈希表是什么?哈希表數據結構詳細資料分析

哈希表也稱為散列表,是根據關鍵字值(key value)而直接進行訪問的數據結構。也就是說,它通過把....
的頭像 算法與數據結構 發表于 09-24 10:25 ? 4769次 閱讀
哈希表是什么?哈希表數據結構詳細資料分析

哈希及哈希算法的介紹

聊到區塊鏈的時候也少不了會聽到“哈?!?、“哈希函數”、“哈希算法”,是不是聽得一頭霧水?別急,這一講....
的頭像 算法與數據結構 發表于 05-22 14:11 ? 3172次 閱讀
哈希及哈希算法的介紹

解析加密貨幣中最常用的四種加密哈希函數的特性和差異

比特幣采礦涉及礦工解決復雜的計算難題,以找到一個塊,然后將其附加到比特幣區塊鏈。就是我們經常稱的工作....
的頭像 物聯網芯片 發表于 05-11 16:30 ? 4357次 閱讀
解析加密貨幣中最常用的四種加密哈希函數的特性和差異

基于低密度生成矩陣和哈希函數的安全簽密方案

基于編碼的密碼系統具備抵抗量子計算的天然優勢。針對傳統的基于Goppa碼構造的密碼方案存在密文擴展率....
發表于 12-12 11:06 ? 349次 閱讀
基于低密度生成矩陣和哈希函數的安全簽密方案

周立功來講解哈希表的實現

在該函數的實現中,需要釋放程序中分配的所有空間,主要包括添加記錄時分配的結點空間,鏈表頭結點數組空間....
的頭像 周立功單片機 發表于 09-30 06:02 ? 3712次 閱讀
周立功來講解哈希表的實現

算法與數據結構——哈希表

周立功教授數年之心血之作《程序設計與數據結構》以及《面向第三章為算法與數據結構,本文為3.5 哈希表....
的頭像 ZLG致遠電子 發表于 09-25 11:37 ? 2851次 閱讀
算法與數據結構——哈希表

Delphi:高效的哈希函數

本內容詳細介紹了Delphi:高效的哈希函數view plaincopy to clipboardp....
發表于 06-07 11:32 ? 899次 閱讀
Delphi:高效的哈希函數
山东十一选五彩乐乐