[發明專利]一種減少哈希沖突的哈希查找方法

在審

• 申請號: 201410778520.5
• 申請日: 2015-08-03
• 公開（公告）號: CN104504038A
• 公開（公告）日: 2015-07-29
• 發明（設計）人: 白帆;李燕杰
• 申請（專利權）人: 北京更快互聯網技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京紐樂康知識產權代理事務所(普通合伙) 11210
• 代理人: 覃莉

技術領域

本發明涉及一種減少哈希沖突的哈希查找方法。

背景技術

哈希方法，又名散列算法，哈希方法將任意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值；哈希值是一段數據唯一且極其緊湊的數值表示形式，散列算法一般用于快速查找和加密算法，著名的散列算法有RS?Hash、JS?Hash、PJW?Hash、ELF?Hash、BKDR?Hash、SDBM?Hash、DJB?Hash以及BP?Hash等。

哈希表（HashTable)，也叫散列表，是根據關鍵碼值(Key?value)而直接進行訪問的數據結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度；這個映射函數叫做散列函數，存放記錄的數組叫做散列表；給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數后若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數f(key)為哈希(Hash)?函數，若結構中存在關鍵字和K相等的記錄，則必定存儲在f(K）的位置上，由此，不需比較便可直接取得所查記錄。這個對應關系f稱為散列函數(Hash?function），按這個思想建立的表為散列表。

碰撞或沖突,?如果兩個不同的輸入通過散列函數計算得出的結果是一樣的，則稱這兩個串是一個碰撞，即key1≠key2，而f(key1)=f(key2），既然是把任意長度的字符串變成固定長度的字符串，所以必有一個輸出串對應無窮多個輸入串，碰撞是必然存在的。

哈希沖突：兩個不同的關鍵字，由于散列函數值相同，因而被映射到同一表位置上，該現象稱為沖突(collision)或碰撞；發生沖突的兩個關鍵字稱為該散列函數的同義詞(synonym)。

沖突基本上不可避免的，除非數據很少，我們只能采取措施盡量避免沖突，或者尋找解決沖突的辦法。

影響沖突的因素，沖突的頻繁程度除了與選擇的哈希函數相關外，還與表的填滿程度相關。

設m和n分別表示表長和表中填入的結點數，則將α=n/m定義為散列表的裝填因子(load?factor)，α越大，表越滿，沖突的機會也越大；通常取α≤1。

1、現有哈希沖突處理

1）開放尋址法：Hi=(H(key)?+?di)?MOD?m,i=1,2，…，k(k<=m-1），其中H(key）為散列函數，m為散列表長，di為增量序列，可有下列三種取法：

1.1??di=1,2,3，…，m-1，稱線性探測再散列；

1.2??di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）稱二次探測再散列；

1.3??di=偽隨機數序列，稱偽隨機探測再散列。

2）再散列法：Hi=RHi(key),i=1,2，…，k?RHi均是不同的散列函數，即在同義詞產生地址沖突時計算另一個散列函數地址，直到沖突不再發生，這種方法不易產生“聚集”，但增加了計算時間。

3）鏈地址法（拉鏈法），同一個散列值存儲在同一個鏈表。

4）建立一個公共溢出區

2、現有處理沖突的方法缺點

1）開放尋址法，在沖突發生時，需要進行模運算，極端情況下，將重復多次。

2）再散列法，在沖突發生時，需要通過另一散列函數進行計算散列值，增加了計算的時間，如果另一散列再次沖突，計算時間再次增加，并且影響性能。

3）鏈地址法，同一個鏈表中的都是相同的散列表，為了確定查找的串，需要進行串的比較，增加時間。

4）建立公共溢出區，同樣在沖突時，將在溢出區中進行查找，還是需要進行串的比較。

綜上所述，現有處理沖突有兩個大的缺點,?一是需要超過一次的散列，另一個是要進行串的比較，即散列表的查找過程仍是一個和關鍵字比較的過程，這兩大缺點降低了查找性能。

針對相關技術中的問題，目前尚未提出有效的解決方案。

發明內容

本發明的目的是提供一種減少哈希沖突的哈希查找方法，以克服目前現有技術存在的上述不足。

本發明的目的是通過以下技術方案來實現：

一種減少哈希沖突的哈希查找方法，包括以下步驟：

對將要查找哈希值的哈希關鍵碼進行分析，初始所述哈希關鍵碼所對應的三個哈希值，其中，所述三個哈希值不相同；