一種減少哈希衝突的哈希查找方法
2023-06-12 05:32:21 1
一種減少哈希衝突的哈希查找方法
【專利摘要】本發明公開了一種減少哈希衝突的哈希查找方法，包括對將要查找哈希值的哈希關鍵碼進行分析，初始哈希關鍵碼所對應的三個哈希值，三個哈希值不相同；輸入要查找的哈希關鍵碼所對應的新的哈希值h1』、h2』、h3』；判斷哈希值h1』、h2』、h3』和哈希值h1、h2、h3是否滿足哈希值h1與新的哈希值h1』相等、哈希值h2與新的哈希值h2』相等並且哈希值h3與新的哈希值h3』相等，在滿足以上關係的情況下，確定新的哈希值h1』、h2』、h3』即為哈希關鍵碼所對應的哈希值。本發明的有益效果為：本改進方法有效解決了哈希查找中發生衝突的情況下，不需要進行關鍵字串的比較查找，而只是進行常數的比較，提高了查找的效率。
【專利說明】一種減少哈希衝突的哈希查找方法
[0001]
【技術領域】
[0002]本發明涉及一種減少哈希衝突的哈希查找方法。
[0003]
【背景技術】
[0004]哈希方法，又名散列算法，哈希方法將任意長度的二進位值映射為較短的固定長度的二進位值，這個小的二進位值稱為哈希值；哈希值是一段數據唯一且極其緊湊的數值表示形式，散列算法一般用於快速查找和加密算法，著名的散列算法有舊他也、幾他也、？了胃 ^^、此？ ^811, 8X1)1？ ^811, 8081 版811、0了8 版吐以及 8？版吐等。
[0005]哈希表(1^18111^1316)，也叫散列表，是根據關鍵碼值(1(67 ^1116)而直接進行訪問的數據結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度；這個映射函數叫做散列函數，存放記錄的數組叫做散列表；給定表1，存在函數？ 0^67)，對任意給定的關鍵字值匕7，代入函數後若能得到包含該關鍵字的記錄在表中的地址，則稱表1為哈希(他也)表，函數？ 0^7)為哈希(他也)函數，若結構中存在關鍵字和1(相等的記錄，則必定存儲在？00的位置上，由此，不需比較便可直接取得所查記錄。這個對應關係？稱為散列函數(他也血此「。!!)，按這個思想建立的表為散列表。
[0006]碰撞或衝突，如果兩個不同的輸入通過散列函數計算得出的結果是一樣的，則稱這兩個串是一個碰撞，即匕71幸匕72，而？ (1^671)寸(^72 )，既然是把任意長度的字符串變成固定長度的字符串，所以必有一個輸出串對應無窮多個輸入串，碰撞是必然存在的。
[0007]哈希衝突:兩個不同的關鍵字，由於散列函數值相同，因而被映射到同一表位置上，該現象稱為衝突((3011181011)或碰撞；發生衝突的兩個關鍵字稱為該散列函數的同義1? (37110117111) 0
[0008]衝突基本上不可避免的，除非數據很少，我們只能採取措施儘量避免衝突，或者尋找解決衝突的辦法。
[0009]影響衝突的因素，衝突的頻繁程度除了與選擇的哈希函數相關外，還與表的填滿程度相關。
[0010]設!II和!1分別表示表長和表中填入的結點數，則將0 =11/111定義為散列表的裝填因子(103(1 ^801:01-) , 3越大，表越滿，衝突的機會也越大；通常取3 ? 1。
[0011]1、現有哈希衝突處理
1)開放尋址法:01=(0(1^67) +(11) 100 111, 1=1, 2,…，匕),其中!為散列函數，III為散列表長，(11為增量序列，可有下列三種取法:
1.1 (11=1, 2，3，…，111-1，稱線性探測再散列；
1.2(11=1-2,-1-2,2-2,-2-2,(3) …，土 (10 ~2，0^=0/2)稱二次探測再散列;
1.3(11=偽隨機數序列，稱偽隨機探測再散列。
[0012]2)再散列法:111=冊1=1,2，…沽冊1均是不同的散列函數，即在同義詞產生地址衝突時計算另一個散列函數地址，直到衝突不再發生，這種方法不易產生「聚集」，但增加了計算時間。
[0013]3)鏈地址法(拉鏈法)，同一個散列值存儲在同一個鍊表。
[0014]4)建立一個公共溢出區
2、現有處理衝突的方法缺點
1)開放尋址法，在衝突發生時，需要進行模運算，極端情況下，將重複多次。
[0015]2)再散列法，在衝突發生時，需要通過另一散列函數進行計算散列值，增加了計算的時間，如果另一散列再次衝突，計算時間再次增加，並且影響性能。
[0016]3)鏈地址法，同一個鍊表中的都是相同的散列表，為了確定查找的串，需要進行串的比較，增加時間。
[0017]4)建立公共溢出區，同樣在衝突時，將在溢出區中進行查找，還是需要進行串的比較。
[0018]綜上所述，現有處理衝突有兩個大的缺點，一是需要超過一次的散列，另一個是要進行串的比較，即散列表的查找過程仍是一個和關鍵字比較的過程，這兩大缺點降低了查找性能。
[0019]針對相關技術中的問題，目前尚未提出有效的解決方案。
[0020]
【發明內容】
[0021]本發明的目的是提供一種減少哈希衝突的哈希查找方法，以克服目前現有技術存在的上述不足。
[0022]本發明的目的是通過以下技術方案來實現:
一種減少哈希衝突的哈希查找方法，包括以下步驟:
對將要查找哈希值的哈希關鍵碼進行分析，初始所述哈希關鍵碼所對應的三個哈希值，其中，所述三個哈希值不相同；
其中，分別通過預先設定的三種哈希運算規則，計算出所述自變量所對應的哈希值匕1、
112,113；
輸入要查找的哈希關鍵碼所對應的新的哈希值卜1』、卜2』、卜3』 ；
判斷所述哈希值111』、112』、113』和所述哈希值111、112、113是否滿足哈希值111與新的哈希值卜1』相等、哈希值卜2與新的哈希值卜2』相等並且哈希值卜3與新的哈希值卜3』相等，在滿足以上關係的情況下，確定所述新的哈希值匕』、!^』、…』即為所述哈希關鍵碼所對應的哈希值。
[0023]進一步的，其中，所述三種哈希運算規則相近但不相同，所述三種哈希運算的具體規則如下:
哈希值卜1向左移5位，然後將經過移位後的數值與原始的哈希值卜1進行加法運算，然後再與預先輸入的關鍵字進行加法運算，經過運算後得到的值等於哈希值卜1，即可計算出所述哈希值&1的具體數值；
哈希值卜2向左移5位，然後經過移位後的數值減去原始的哈希值卜2，經過減法運算後的數值在於預先輸入的關鍵字進行加法運算，經過運算後得到的數值等於哈希值112，即可計算出所述哈希值卜2的具體數值；
哈希值卜3向左移5位，然後與預先輸入的關鍵字進行加法運算，然後將原始的哈希值向右移2位，將經過加法運算後得到的數值與經過向右移位的哈希值進行加法運算，得到的數值等於哈希值…的按位異或值，即可計算出所述哈希值113的具體數值。
[0024]進一步的，所述卜1』、卜2』以及卜3』三個哈希值為常數整形值。
[0025]本發明的有益效果為:本改進方法只需要最初添加關鍵字時的一次散列運算，在衝突發生時，只進行整型比較，降低衝突發生時查找的時間，提高運算性能；有效解決了哈希查找中發生衝突的情況下，不需要進行關鍵字串的比較查找，而只是進行常數的比較，提高了查找的效率。
[0026]
【專利附圖】
【附圖說明】
[0027]為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。
[0028]圖1是根據本發明實施例所述的一種哈希方法的哈希表的表示圖。
【具體實施方式】
[0029]下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員所獲得的所有其他實施例，都屬於本發明保護的範圍。
[0030]如圖1所示，根據本發明實施例的一種減少哈希衝突的哈希查找方法，包括以下步驟:
提供哈希表，所述哈希表包括由一系列哈希關鍵字構成的存儲空間表；
設置一次的散列函數運算，所述散列函數包括第一哈希函數111=0 0^67)、第二哈希函數 112=:^2(1^67)和第三哈希函數 113=:^3(1^67)；
對將要查找哈希值的哈希關鍵碼進行分析，初始所述哈希關鍵碼所對應的三個哈希值，其中，所述三個哈希值不相同；
其中，分別通過預先設定的三種哈希運算規則，計算出所述自變量所對應的哈希值匕1、
112,113；
輸入要查找的哈希關鍵碼所對應的新的哈希值卜1』、卜2』、卜3』 ；
判斷所述哈希值111』、112』、113』和所述哈希值111、112、113是否滿足哈希值111與新的哈希值卜1』相等、哈希值卜2與新的哈希值卜2』相等並且哈希值卜3與新的哈希值卜3』相等，在滿足以上關係的情況下，確定所述新的哈希值匕』、!^』、…』即為所述哈希關鍵碼所對應的哈希值。
[0031]接收哈希關鍵碼匕7，將接收到的哈希關鍵碼匕7帶入上述的散列函數中，得到三個不同的哈希值111、112以及113，將哈希值111作為主哈希值插入哈希表，並將哈希值112和113作為從屬哈希值插入哈希表；
然後採用衝突採用鏈地址方法，同一個哈希值存儲在同一個鍊表，在哈希表中查找時，輸入預先編輯或要輸入的卜1』、卜2』以及卜3』三個哈希值；
根據所述卜1』、卜2』以及卜3』三個新的哈希值確定相對應的關鍵字，當卜1』、卜2』以及匕3』滿足公式卜1 =卜1』 && 112 =卜2』 && 113二鬥3』，即找到了與關鍵碼匕7相對應的關鍵字。
[0032]所述第一哈希函數111=0 (匕丫)、第二哈希函數112寸2 (匕丫)和第三哈希函數113=^3 (1^67)的運算規則相近但不相同。
[0033]其中，所述三種哈希運算規則相近但不相同，所述三種哈希運算的具體規則如下:
=出1〈〈 5 ) + + ^[1]；其含義為:希值卜1向左移5位，其中，向左移5位相當於乘以32，然後將經過移位後的數值與原始的哈希值卜1進行加法運算，然後再與預先輸入的關鍵字進行加法運算，經過運算後得到的值等於哈希值卜1，即可計算出所述哈希值匕1的具體數值；
112 =(112〈〈 5 ) - ！！2 + ^[1]；其含義為:哈希值卜2向左移5位，然後經過移位後的數值減去原始的哈希值卜2，經過減法運算後的數值在於預先輸入的關鍵字進行加法運算，經過運算後得到的數值等於哈希值卜2，即可計算出所述哈希值卜2的具體數值；
！！3 -= ( ( ！！3 -- 5 ) + ^[1] +汨3 -- 2 ))；其含義為:哈希值匕3向左移5位，然後與預先輸入的關鍵字進行加法運算，然後將原始的哈希值向右移2位，將經過加法運算後得到的數值與經過向右移位的哈希值進行加法運算，得到的數值等於哈希值卜3的按位異或值，即可計算出所述哈希值…的具體數值。
[0034]所述卜1』、卜2』以及卜3』三個哈希值為常數整形值。
[0035]具體應用時，通過一次的散列函數運算，一個關鍵字串將得到三個不同的整形散列值。
[0036]散列函數運算之前，根據關鍵字初始化三個不同的哈希值，三個哈希值計算關鍵串的散列值的運算規則相近但不相同，即111=:^1(1^67)、卜2 = (1^67)以及…=￡3(1^67),？1、和為相近但不相同的運算規則，可以在一個遍歷關鍵碼匕7的運算過程中，生成三個哈希值，以4為主哈希值插入哈希表，112和113哈希值作為從屬值插入哈希表。
[0037]衝突採用鏈地址方法，在哈希表查找時，同哈希表插入一樣，一次運算生成卜1』、112』以及卜3』三個新哈希值，在衝突發生時，將不再需要進行串的比較，而只需要進行三個哈希值的比較，即滿足111 =卜1』 && 112 =卜2』 && 113二鬥3』的條件時，就說明我們找到了與關鍵碼匕7相對應的關鍵字。
[0038]通過上述運算方法，可知，本方法通過一次串的編歷運算得到三個哈希值，並且在衝突發生時，只進行三個常數整型值比較，速度極快。
[0039]在發生衝突時，如圖1所不，是一個哈希表的一個表不，左邊第一列灰框是表內的元素，第二列之後的都是衝突的元素。
[0040]當查找時，根據111』首先定位到左邊第一列，根據111/=111 && 112』 =112 && 113？ =113，對查找的匕7按算法生成卜1』、…』、…』，與原有哈希表中的44243進行整數常數比較，不管衝突與否，都能快速確定位置，在刪除關鍵字時也是如此；如果不成立，即為衝突情況，當只有與111相等時，說明衝突了，但是其他兩個沒有；則需遍歷後續元素，後續元素同樣也是常數比較，直到滿足條件，找到相應的關鍵字為止。
[0041]在目前網際網路的流量爆炸性增長的情況下，網絡分析設備、防火牆、嫩I網關等，核心處理模塊都需要用到哈希運算查找，在核心交換機、路由器中，以及0？1設備、網絡分流器，採用本發明中的哈希方法，在不改變系統原有功能的前提下，能降低設備佔用率15%左右，降低了系統的功耗，提高了設備的穩定性。且改進的哈希方法通用性強，目標系統稍微修改就能使用。
[0042]以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。
【權利要求】
1.一種減少哈希衝突的哈希查找方法，其特徵在於，包括以下步驟: 對將要查找哈希值的哈希關鍵碼進行分析，初始所述哈希關鍵碼所對應的三個哈希值，其中，所述三個哈希值不相同； 其中，分別通過預先設定的三種哈希運算規則，計算出所述自變量所對應的哈希值hl、h2、h3 ； 輸入要查找的哈希關鍵碼所對應的新的哈希值hi』、h2』、h3』 ； 判斷所述哈希值hi』、h2』、h3』和所述哈希值h1、h2、h3是否滿足哈希值hi與新的哈希值hi』相等、哈希值h2與新的哈希值h2』相等並且哈希值h3與新的哈希值h3』相等，在滿足以上關係的情況下，確定所述新的哈希值hi』、h2』、h3』即為所述哈希關鍵碼所對應的哈希值。
2.根據權利要求1所述的減少哈希衝突的哈希查找方法，其特徵在於，其中，所述三種哈希運算規則相近但不相同，所述三種哈希運算的具體規則如下: 哈希值hi向左移5位，然後將經過移位後的數值與原始的哈希值hi進行加法運算，然後再與預先輸入的關鍵字進行加法運算，經過運算後得到的值等於哈希值hl，即可計算出所述哈希值hi的具體數值； 哈希值h2向左移5位，然後經過移位後的數值減去原始的哈希值h2，經過減法運算後的數值在於預先輸入的關鍵字進行加法運算，經過運算後得到的數值等於哈希值h2，即可計算出所述哈希值h2的具體數值； 哈希值h3向左移5位，然後與預先輸入的關鍵字進行加法運算，然後將原始的哈希值向右移2位，將經過加法運算後得到的數值與經過向右移位的哈希值進行加法運算，得到的數值等於哈希值h3的按位異或值，即可計算出所述哈希值h3的具體數值。
3.根據權利要求1或2所述的減少哈希衝突的哈希查找方法，其特徵在於，所述hi』、h2』以及h3』三個哈希值為常數整形值。
【文檔編號】G06F17/30GK104504038SQ201410778520
【公開日】2015年4月8日 申請日期:2014年12月15日 優先權日:2014年12月15日
【發明者】白帆, 李燕傑 申請人:北京更快網際網路技術有限公司