哈希數據存儲方法和裝置的製作方法

2023-05-25 00:56:46

專利名稱：哈希數據存儲方法和裝置的製作方法
技術領域：
本發明涉及通信技術，尤其涉及一種哈希數據存儲方法和裝置。
背景技術：
散列(Hash)算法通常也稱之為哈希算法，通過hash算法將任意長度的輸入變換成固定長度的輸出，該輸出便是散列值。這種轉換是一種壓縮映射，即散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，因此不可能通過散列值來唯一確定輸入值。哈希算法可以用於多種操作，如身份驗證、通信領域中的目的地址匹配等過程。根據設定的哈希函數和衝突處理方法將一組關鍵字映射到一個有限的地址區間上，並以關鍵字在地址區間中的象作為記錄在表中的存儲位置，這種表稱為哈希表或散列，其中的存儲位置稱為哈希地址或散列地址。哈希表作為一種線性數據結構，與表格和隊列相比，查找
速度較快。現有技術中存在各種各樣的哈希算法，可以優化數據查找速度；然而，現有技術中的哈希算法通常存在哈希衝突，無法有效減少哈希衝突，從而影響資源的使用效率。

發明內容
本發明提供一種哈希數據存儲方法和裝置，有效減少哈希衝突，提高資源的使用效率。本發明的第一個方面是提供一種哈希數據存儲方法，包括採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取所述待存儲數據的至少兩個哈希值，各哈希值分別與各哈希算法相對應；當所述待存儲數據的各存儲位置中存在空閒的存儲位置時，將所述待存儲數據存儲在一個空閒的存儲位置中；其中，所述待存儲數據的各存儲位置為所述待存儲數據的至少兩個哈希值分別對應的存儲位置；當所述待存儲數據的各存儲位置均不空閒時，根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理；其中，所述第一已存儲數據的其他存儲位置為所述第一已存儲數據的其他哈希值對應的存儲位置。本發明的另一個方面是提供一種哈希數據存儲裝置，包括哈希處理模塊，用於採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取所述待存儲數據的至少兩個哈希值，各哈希值分別與各哈希算法相對應；第一存儲模塊，用於當所述待存儲數據的各存儲位置中存在空閒的存儲位置時，將所述待存儲數據存儲在一個空閒的存儲位置中；其中，所述待存儲數據的各存儲位置為所述待存儲數據的至少兩個哈希值分別對應的存儲位置；第二存儲模塊，用於當所述待存儲數據的各存儲位置均不空閒時，根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理；其中，所述第一已存儲數據的其他存儲位置為所述第一已存儲數據的其他哈希值對應的存儲位置。本發明的技術效果是通過採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取待存儲數據的至少兩個哈希值，當待存儲數據的各存儲位置中存在空閒的存儲位置時，將待存儲數據存儲在一個空閒的存儲位置中，當待存儲數據的各存儲位置均不空閒時，根據待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對待存儲數據進行迭代遞歸存儲處理；本發明利用多種哈希算法來生成待存儲數據的多個存儲位置，從而可以有效減少哈希衝突，提高了資源的使用效率。


圖I為本發明哈希數據存儲方法實施例一的流程圖；圖2為本發明哈希數據存儲方法實施例二的流程圖；圖3為本發明哈希數據存儲方法實施例二中的數據存儲過程示意圖一；圖4為本發明哈希數據存儲方法實施例二中的數據存儲過程示意圖二 ；圖5為本發明哈希數據存儲方法實施例二中的數據存儲過程示意圖三；圖6為本發明哈希數據存儲裝置實施例一的結構示意圖；圖7為本發明哈希數據存儲裝置實施例二的結構示意圖。
具體實施例方式圖I為本發明哈希數據存儲方法實施例一的流程圖，如圖I所示，本實施例提供了一種哈希數據存儲方法，可以具體包括如下步驟步驟101，採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取所述待存儲數據的至少兩個哈希值。本實施例為了有效減少哈希衝突，利用多種哈希算法來對數據進行存儲。本步驟為採用至少兩種哈希算法分別對待存儲數據進行哈希處理，此處的至少兩種哈希算法可以具體採用現有的各種哈希算法，通過至少兩種哈希算法對待存儲數據進行哈希處理，分別得到待存儲數據的至少兩個哈希值，此處的各哈希值分別與各哈希算法相對應。即通過一個哈希算法計算得到待存儲數據的一個哈希值，通過至少兩個哈希算法計算得到待存儲數據的至少兩個哈希值，具體每個哈希算法的哈希處理過程可以採用該哈希算法的現有哈希機制，此處不再一一贅述。對於已有的各哈希算法來說，可能不同哈希算法具體適用於不同的應用場景中，每個哈希算法在某個應用場景中可能有較好的散列效果，但其在其他應用場景中散列效果則較差，因此，本實施例綜合多種哈希算法的優勢來分別獲取各哈希算法對應的哈希值。步驟102，當所述待存儲數據的各存儲位置中存在空閒的存儲位置時，將所述待存儲數據存儲在一個空閒的存儲位置中。由於通過上述步驟獲取到了該待存儲數據的多個哈希值，每個哈希值在存儲空間中對應一個存儲位置，因此待存儲數據在存儲空間中存在可以存儲的多個存儲位置。採用不同哈希算法對待存儲數據進行哈希處理得到的不同哈希值，可能與其他已存儲在存儲空間中的已存儲數據的哈希值相同，若兩個數據的兩個哈希值相同，則二者在存儲時出現哈希衝突。為了避免這種哈希衝突，在本實施例中，在對每一個待存儲數據進行存儲時，均需要對該待存儲數據的各存儲位置進行哈希衝突判斷，此處的待存儲數據的各存儲位置為所述待存儲數據的至少兩個哈希值分別對應的存儲位置。在本實施例中，一個存儲空間中包含有多個存儲位置，通過哈希處理得到的各哈希值與這些存儲位置具有對應關係，對應關係具體可以為哈希值與存儲位置的序號的對應關係，二者可以相同，即哈希值代表存儲位置的序號，例如，哈希值為2對應於存儲空間中的第二個存儲位置。當待存儲數據的各存儲位置中存在一個或多個空閒的存儲位置時，可以將該待存儲數據存儲在其中一個空閒的存儲位置中。在本實施例中，當存儲空間中的某個存儲位置未存儲有數據，則表明該存儲位置空閒；當存儲空間中的某個位置存儲有數據，則表明該存儲位置不空閒。在對待存儲數據進行存儲時，由於每個待存儲數據均包含至少兩個存儲位置，則可以依次判斷這些存儲位置是否空閒，當某個存儲位置空閒時，便可以直接將該待存儲數據存儲在該存儲位置，其他存儲位置可以暫不用判斷。如果待存儲數據為第一個需要存儲在存儲空間中的數據，則在該待存儲數據存儲之前，該存儲空間中的各存儲位置均空閒，可以將該待存儲數據存儲在其中任意一個存儲位置。如果待存儲數據不是第一個需要存儲在存儲空間中的數據，則在該待存儲數據存儲之前，需要先判斷當前存儲空間中其他
數據的存儲位置是否與其存儲位置發生衝突。步驟103，當所述待存儲數據的各存儲位置均不空閒時，根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理。當所述待存儲數據的各存儲位置均不空閒時，根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理。通過對待存儲數據的各存儲位置進行上述判斷後，當該待存儲數據的各存儲位置均不空閒時，即各存儲位置中均被其他數據佔據，此時則根據該待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況，對該待存儲數據進行遞歸存儲處理。此處的遞歸存儲處理可以具體為以待存儲數據為遞歸存儲過程中的第I層級的數據，通過哈希處理得到待存儲數據的各存儲位置，若待存儲數據的各存儲位置均不空閒，則獲取到各存儲位置當前存儲的第一已存儲數據；該第一已存儲數據即為遞歸存儲過程中的第2層級的數據，再獲取對第一已存儲數據進行哈希處理得到的各存儲位置，若第一已存儲數據的各存儲位置均不空閒，則獲取到各存儲位置當前存儲的第二已存儲數據；該第二已存儲數據為遞歸存儲過程中的第3層的數據，若第二已存儲數據的各存儲位置也均不空閒，則可以將第二已存儲數據作為上述第一已存儲數據，繼續獲取下一層級的數據，並查找下一層級的數據的各存儲位置；依次類推，對遞歸存儲過程中各層級的數據的存儲位置進行查找判斷，最終將待存儲數據存儲在存儲空間中。在本實施例中，為了提高數據存儲效率，可以對整體遞歸次數進行限定，如設置遞歸次數閾值，若上述遞歸次數達到預設的遞歸次數閾值，則不再進行下一層級的查找判斷，直接將該待存儲數據進行丟棄處理。當然也可以不限定遞歸此時，則當存儲空間中已不存在空閒的存儲位置，則不管查找到哪個層級，均無法對數據進行移動，則將該待存儲數據進行丟棄處理。其中，第一已存儲數據的其他存儲位置為第一已存儲數據的其他哈希值對應的存儲位置，此處的第一已存儲數據具體指待存儲數據的存儲位置中已存儲的數據，其只是為了與後續第二已存儲數據作區分，並沒有特別的含義。在本實施例中，存儲在存儲空間中的已存儲數據也是採用上述過程進行存儲的，即每個已存儲數據在存儲之前也需要採用至少兩個哈希算法進行哈希處理，得到至少兩個哈希值。具體地，本步驟為根據第一已存儲數據的其他存儲位置的存儲情況，來存儲該待存儲數據，第一已存儲數據的其他存儲位置為，第一已存儲數據的各存儲位置中除其當前的存儲位置之外的其他存儲位置，存儲情況具體指這些存儲位置為空閒或不為空閒的情況。具體地，本實施例中的上述步驟103具體可以包括下述各個步驟當所述待存儲數據的各存儲位置均不空閒時，依次判斷所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置中是否存在空閒的存儲位置；若所述待存儲數據的各存儲位置中一個或多個第一已存儲數據的其他存儲位置中存在空閒的存儲位置，則將一個第一已存儲數據遷移到所述第一已存儲數據的空閒的存儲位置，將所述待存儲數據存儲在所述第一已存儲數據的原存儲位置；若所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置均不空閒，則根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理。 更具體地，本實施例中的上述根據所述各第一已存儲數據的其他存儲位置中各第
二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理的步驟可以具體包括如下步驟依次判斷所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置中是否存在空閒的存儲位置；若所述各第一已存儲數據的各存儲位置中一個或多個第二已存儲數據的其他存儲位置中存在空閒的存儲位置，則將一個第二已存儲數據遷移到所述第二已存儲數據的空閒的存儲位置，將所述第二已存儲數據對應的第一已存儲數據遷移到所述第二已存儲數據的原存儲位置，將所述待存儲數據存儲在所述第一已存儲數據的原存儲位置。更進一步地，本實施例中的上述根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理的步驟還可以包括如下步驟若所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置均不空閒，則將所述第二已存儲數據作為第一已存儲數據，遞歸執行所述根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理的步驟，上述遞歸次數達到預設的遞歸次數閾值為止。更進一步地，本實施例提供的哈希數據存儲方法在上述步驟103之後，還可以包括如下步驟採用數據存儲時所使用的多個哈希算法分別對待查詢數據進行哈希處理，獲取所述待查詢數據的多個哈希值，各哈希值分別與各哈希算法相對應；在所述待查詢數據的各哈希值對應的存儲空間中的存儲位置分別查詢所述待存儲數據。本實施例提供了一種哈希數據存儲方法，通過採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取待存儲數據的至少兩個哈希值，當待存儲數據的各存儲位置中存在空閒的存儲位置時，將待存儲數據存儲在一個空閒的存儲位置中，當待存儲數據的各存儲位置均不空閒時，根據待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對待存儲數據進行遞歸存儲處理；本實施例利用多種哈希算法來生成待存儲數據的多個存儲位置，從而可以有效減少哈希衝突，提高了資源的使用效率。圖2為本發明哈希數據存儲方法實施例二的流程圖，如圖2所示，本實施例提供了一種哈希數據存儲方法，可以具體包括如下步驟步驟201，採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取所述待存儲數據的至少兩個哈希值。本步驟為採用至少兩種哈希算法分別對待存儲數據進行哈希處理，分別得到待存儲數據的至少兩個哈希值，此處的各哈希值分別與各哈希算法相對應。對於已有的各哈希算法來說，可能不同哈希算法具體適用於不同的應用場景中，每個哈希算法在某個應用場景中可能有較好的散列效果，但其在其他應用場景中散列效果則較差，因此，本實施例綜合多種哈希算法的優勢來分別獲取各哈希算法對應的哈希值。假設採用兩種哈希算法A、B對待存儲數據進行哈希處理，此處以待存儲數據為IP位址為例進行說明，以IP位址作為哈希算法的鍵值(key)，採用A算法、B算法分別對IP位址進行哈希處理，可以得到對應的哈希值，從而根據哈希值進行存儲和查找。假設分別有兩個不同的IP位址P和Q需要存儲在存儲空間中；IP位址P經過A算法的哈希處理後得到哈希值為xl，經過B算法的哈希處理
後得到哈希值為x2，即IP位址P的哈希值表示為(xl，x2) ；IP位址Q經過A算法的哈希處理後得到哈希值為yl，經過B算法的哈希處理後得到哈希值為y2，即IP位址Q的哈希值表示為(yl, y2)0步驟202，判斷待存儲數據的各存儲位置中是否存在空閒的存儲位置，如果是，則執行步驟203，否則執行步驟204。在獲取到待存儲數據的各哈希值後，由於本實施例中哈希值與存儲空間中的存儲位置相對應，則可以根據待存儲數據的哈希值對該待存儲數據進行存儲處理。在進行待存儲數據的存儲之前，先判斷待存儲數據的各存儲位置中是否存在空閒的存儲位置，空閒的存儲位置為存儲空間中當前未存儲數據的位置，如果該待存儲數據的各存儲空間中存在一個或多個空閒的存儲位置，則執行步驟203，否則執行步驟204。具體可以按照待存儲數據的哈希值的順序進行查找判斷，依次判斷各存儲位置是否為空閒。此處的待存儲數據的存儲位置為待存儲數據的哈希值對應的存儲位置，如圖3所示為本發明哈希數據存儲方法實施例二中的數據存儲過程示意圖一，圖中節點P(x，y)表示數據P經過哈希算法的計算後得到的兩個哈希值分別為X和y，這兩個哈希值X和I分別與序號為X和I的存儲位置相對應。本實施例中哈希值與存儲位置的對應關係可以表現為，哈希值可以表示該數據在存儲空間中可以存儲的存儲位置的序號，如圖3中數據A的哈希值為I和5，則該數據A可以存儲在序號為I或5的存儲空間中。步驟203，將待存儲數據存儲在一個空閒的存儲位置中，並返回步驟201。經過查找判斷，若待存儲數據的各存儲位置中存在一個或多個空閒的存儲位置，則將該待存儲數據存儲在其中一個空閒的存儲位置中，並結束該待存儲數據的存儲流程，並返回步驟201，對下一個待存儲數據進行存儲處理。如圖3所示，假設待存儲數據為C，通過上述步驟201獲取到待存儲數據C的哈希值為(1，3)，當前存儲空間中已經在序號為I、2、4、5的四個存儲位置存儲有數據A(l，5)、數據B (2，7)、數據D (4，9)、數據E (5，12)，以待存儲數據C的哈希值的順序進行查找判斷，發現待存儲數據C的哈希值「I」對應的存儲位置已被數據A佔據，則此次查找存儲失敗；再查找哈希值「3」對應的存儲位置，發現哈希值「3」對應的存儲位置處於空閒狀態，則可以將待存儲數據C直接存儲在序號為3的存儲位置，此次查找存儲成功，並返回步驟201，對下一個待存儲數據進行存儲處理。
步驟204，依次判斷待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置中是否存在空閒的存儲位置，如果是，則執行步驟205，否則執行步驟206。經過查找判斷，若待存儲數據的各存儲位置均不空閒，即待存儲數據的各哈希值對應的各存儲位置均被其他數據佔據，則依次判斷待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置中是否存在空閒的存儲位置，如果是，則執行步驟205，否則執行步驟206。其中，第一已存儲數據的其他存儲位置為第一已存儲數據的其他哈希值對應的存儲位置，此處的第一已存儲數據具體指待存儲數據的存儲位置中已存儲的數據，其只是為了與後續第二已存儲數據作區分，並沒有特別的含義。圖4為本發明哈希數據存儲方法實施例二中的數據存儲過程示意圖二，如圖4所示，當存儲完數據C後，對待存儲數據F進行存儲，經過上述步驟201的計算獲取到待存儲數據F的哈希值為(3，4)，依照上述過程，先對哈希值「3」對應的存儲位置進行查找判斷，發現該存儲位置已被數據C(l，3)佔據，此次查找存儲失敗；繼續對哈希值「4」對應的存儲位置進行查找判斷，發現該存儲位置已被數據D(4, 6)佔據，此次查找存儲也失敗。此時，依次判斷待存儲數據F (3，4)的各存儲位置中各第一已存儲數據，即C(l，3)和D (4，6)，的其他存儲位置是否存在空閒的存儲位置，如果存
在，則執行步驟205，否則執行步驟206。步驟205，將一個第一已存儲數據遷移到所述第一已存儲數據的空閒的存儲位置，將所述待存儲數據存儲在所述第一已存儲數據的原存儲位置，並返回步驟201。若待存儲數據的各存儲位置中一個或多個第一已存儲數據的其他存儲位置中存在空閒的存儲位置，則將其中一個第一已存儲數據遷移到第一已存儲數據的空閒的存儲位置，將待存儲數據存儲在第一已存儲數據的原存儲位置，並返回步驟201，對下一個待存儲數據進行存儲處理。在本實施例中，可以按照順序對各第一已存儲數據的其他存儲位置進行查找判斷，當查找到其中某一個第一已存儲數據的其中一個其他存儲位置空閒時，便可以將該第一已存儲數據從原存儲位置遷移到該空閒的存儲位置，而無需再對該第一已存儲數據的其他存儲位置以及其他第一已存儲數據的其他存儲位置進行查找判斷。繼續參照上述圖4，先對數據C(l，3)的其他存儲位置進行查找判斷，發現序號為3的存儲位置已被自身佔據，則無法進行數據移動；在對數據0(4，6)其他存儲位置進行查找判斷，發現序號為6的存儲位置為空閒，則將數據D (4，6)從其原存儲位置前移到序號為6的存儲位置，然後便可以將待存儲數據F (3，4)存儲到數據0(4，6)的原存儲位置，此次查找存儲成功，並返回步驟201，對下一個待存儲數據進行存儲處理。步驟206，依次判斷各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置中是否存在空閒的存儲位置，如果是，則執行步驟207，否則執行步驟208。經過上述對各第一已存儲數據的其他存儲位置的查找判斷，若該待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置均不空閒，即各第一已存儲數據的其他存儲位置也已被其他數據佔據，則繼續嘗試移動第一已存儲數據的存儲位置中的第二已存儲數據，即依次判斷各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置中是否存在空閒的存儲位置，如果是，則執行步驟207，否則執行步驟208。其中，第二已存儲數據的其他存儲位置為第二已存儲數據的其他哈希值對應的存儲位置，此處的第二已存儲數據具體指上述第一已存儲數據的存儲位置中已存儲的數據，其只是為了與上述第一已存儲數據作區分，並沒有特別的含義。圖5為本發明哈希數據存儲方法實施例二中的數據存儲過程示意圖三，如圖5所示，當完成數據C和數據F的存儲後，對待存儲數據G進行存儲，經過上述步驟201的計算獲取到待存儲數據G的哈希值為(4，2)，依照上述過程，先對哈希值「4」對應的存儲位置進行查找判斷，發現該存儲位置已被數據F(3，4)佔據，此次查找存儲失敗；繼續對哈希值「2」對應的存儲位置進行查找判斷，發現該存儲位置已被數據B(2, 7)佔據，此次查找存儲也失敗。此時，依次判斷待存儲數據G (4，2)的各存儲位置中各第一已存儲數據，即F (3，4)和B (2，7)，的其他存儲位置是否存在空閒的存儲位置；先對第一已存儲數據F(3，4)的其他存儲位置進行查找判斷，發現序號為4的存儲位置被其自身佔據，此次查找存儲失敗；再對第一已存儲數據B (2，7)的其他存儲位置進行查找判斷，發現序號為7的存儲位置被數據H(8，7)佔據，此次查找存儲失敗。此時則遞歸嘗試移走第一已存儲數據的存儲位置中的第二已存儲數據，即依次判斷各第一已存儲數據F(3，4)和B(2, 7)的其他存儲位置中各第二已存儲數據的其他存儲位置中是否存在空閒的存儲位置，其中，第一已存儲數據F (3，4)的各存儲位置中的第二已存儲數據為其自身，第一已存儲數據B(2，7)的各存儲位置中的第二已存儲數據還包括H (8，7)，則現在只需第二已存儲數據H (8，7)的其他存儲位置中是否存在空閒的存儲位置，判斷如果是，則執行步驟207，否則執
行步驟208。步驟207，將一個第二已存儲數據遷移到第二已存儲數據的空閒的存儲位置，將第二已存儲數據對應的第一已存儲數據遷移到第二已存儲數據的原存儲位置，將待存儲數據存儲在第一已存儲數據的原存儲位置，並返回步驟201。若一個或多個第一已存儲數據的其他存儲位置中一個或多個第二已存儲數據的其他存儲位置中存在空閒的存儲位置，則將一個第二已存儲數據遷移到第二已存儲數據的空閒的存儲位置，將第二已存儲數據對應的第一已存儲數據遷移到第二已存儲數據的原存儲位置，將待存儲數據存儲在第一已存儲數據的原存儲位置，並返回步驟201，繼續對下一個待存儲數據進行存儲處理。繼續參照上述圖5，待存儲數據G (4，2)的存儲位置中的第一已存儲數據F(3，4)的其他存儲位置中不包含第二已存儲數據，待存儲數據G (4，2)的存儲位置中的第一已存儲數據B(2，7)的其他存儲位置中的第二已存儲數據為H (8，7)，通過查找判斷，第二已存儲數據H (8，7)的其他存儲位置存在空閒的存儲位置，即序號為8的存儲位置，此時則先將該第二已存儲數據H (8，7)遷移到該空閒的存儲位置，即序號為8的存儲位置，然後將對應於該第二已存儲數據H (8，7)的第一已存儲數據B(2，7)遷移到第二已存儲數據H (8，7)的原存儲位置，即序號為7的存儲位置，再將待存儲數據G (4，2)存儲到第一已存儲數據B (2，7)的原存儲位置，即序號為2的存儲位置，此次查找存儲成功，並返回步驟201，對下一個待存儲數據進行存儲處理。步驟208，丟棄所述待存儲數據，並返回步驟201。本實施例以進行兩次遞歸查找和移動為例對本發明的方案進行說明，即若各第一已存儲數據的各存儲位置中各第二已存儲數據的其他存儲位置均不空閒，表明當前存儲空間可能已滿或接近滿，同時為了避免因遞歸查找次數多導致查找存儲的性能降低，則不再繼續移動第二已存儲數據的各存儲位置中的已存儲數據，可以直接丟棄該待存儲數據。進一步地，當通過上述各個步驟完成對各待存儲數據的存儲後，本實施例還可以包括在已存儲有數據的存儲空間中查找待查詢數據的步驟。具體地，在進行數據查詢時，先採用上述步驟201中數據存儲時所使用的多個哈希算法分別對待查詢數據進行哈希處理，獲取待查詢數據的多個哈希值，各哈希值分別與各哈希算法相對應。然後直接在該待查詢數據的各哈希值對應的存儲空間中的存儲位置分別查詢待存儲數據，若在各存儲位置查詢到待存儲數據，則表明數據查詢成功，否則數據查詢失敗。在上述數據存儲過程中，對於每個待存儲數據來說，其只可能存儲在其哈希值對應的存儲位置，因此在後續查詢過程中只需在其對應的存儲位置進行查找，無需查找其 他位置，因此可以提高數據查找速度。本實施例提供了一種哈希數據存儲方法，通過採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取待存儲數據的至少兩個哈希值，當待存儲數據的各存儲位置中存在空閒的存儲位置時，將待存儲數據存儲在一個空閒的存儲位置中，當待存儲數據的各存儲位置均不空閒時，根據待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對待存儲數據進行遞歸存儲處理；本實施例利用多種哈希算法來生成待存儲數據的多個存儲位置，當其存儲位置與已存儲數據的存儲位置出現衝突，通過迭代查找和數據移動來克服出現的衝突，從而可以有效減少哈希衝突，提高了資源的使用效率。本領域普通技術人員可以理解實現上述各方法實施例的全部或部分步驟可以通過程序指令相關的硬體來完成。前述的程序可以存儲於一計算機可讀取存儲介質中。該程序在執行時，執行包括上述各方法實施例的步驟；而前述的存儲介質包括R0M、RAM、磁碟或者光碟等各種可以存儲程序代碼的介質。圖6為本發明哈希數據存儲裝置實施例一的結構示意圖，如圖6所示，本實施例提供了一種哈希數據存儲裝置，可以具體執行上述方法實施例一中的各個步驟，此處不再贅述。本實施例提供的哈希數據存儲裝置可以具體包括第一哈希處理模塊601、第一存儲模塊602和第二存儲模塊603。其中，第一哈希處理模塊601用於採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取所述待存儲數據的至少兩個哈希值，各哈希值分別與各哈希算法相對應。第一存儲模塊602用於當所述待存儲數據的各存儲位置中存在空閒的存儲位置時，將所述待存儲數據存儲在一個空閒的存儲位置中；其中，所述待存儲數據的各存儲位置為所述待存儲數據的至少兩個哈希值分別對應的存儲位置。第二存儲模塊603用於當所述待存儲數據的各存儲位置均不空閒時，根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行存儲處理；其中，所述第一已存儲數據的其他存儲位置為所述第一已存儲數據的其他哈希值對應的存儲位置。圖7為本發明哈希數據存儲裝置實施例二的結構示意圖，如圖7所示，本實施例提供了一種哈希數據存儲裝置，可以具體執行上述方法實施例二中的各個步驟，此處不再贅述。本實施例提供的哈希數據存儲裝置在上述圖6所示的基礎之上，第二存儲模塊603可以具體包括判斷單元613、第一存儲單元623和第二存儲單元633。其中，判斷單元613用於當所述待存儲數據的各存儲位置均不空閒時，依次判斷所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置中是否存在空閒的存儲位置。第一存儲單元623用於若判斷單元613的判斷結果為所述待存儲數據的各存儲位置中一個或多個第一已存儲數據的其他存儲位置中存在空閒的存儲位置，則將一個第一已存儲數據遷移到所述第一已存儲數據的空閒的存儲位置，將所述待存儲數據存儲在所述第一已存儲數據的原存儲位置。第二存儲單元633用於若判斷單元613的判斷結果為所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置均不空閒，則根據所述各第一已存儲數據的各存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行存儲處理。
具體地，本實施例中的第二存儲單元633可以具體包括判斷子單元6331和第一存儲子單元6332。其中，判斷子單元6331用於依次判斷所述各第一已存儲數據的各存儲位置中各第二已存儲數據的其他存儲位置中是否存在空閒的存儲位置。第一存儲子單元6332用於若所述判斷子單元的判斷結果為所述各第一已存儲數據的各存儲位置中一個或多個第二已存儲數據的其他存儲位置中存在空閒的存儲位置，則將一個第二已存儲數據遷移到所述第二已存儲數據的空閒的存儲位置，將所述第二已存儲數據對應的第一已存儲數據遷移到所述第二已存儲數據的原存儲位置，將所述待存儲數據存儲在所述第一已存儲數據的原存儲位置。進一步地，本實施例中的第二存儲單元633還可以包括第二存儲子單元6333。第二存儲子單元6333用於若所述判斷子單元的判斷結果為所述各第一已存儲數據的各存儲位置中各第二已存儲數據的其他存儲位置均不空閒，則將所述第二已存儲數據作為第一已存儲數據，遞歸執行所述根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據
的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理的步驟，上述遞歸次數達到預設的遞歸次數閾值為止。更進一步地，本實施例提供的哈希數據存儲裝置還可以包括第二哈希處理模塊604和查詢模塊605。其中，第二哈希處理模塊604用於在所述根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理之後，採用所述第一哈希處理模塊所使用的多個哈希算法分別對待查詢數據進行哈希處理，獲取所述待查詢數據的多個哈希值，各哈希值分別與各哈希算法相對應。查詢模塊605用於在所述待查詢數據的各哈希值對應的存儲空間中的存儲位置分別查詢所述待存儲數據。本實施例提供了一種哈希數據存儲裝置，通過採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取待存儲數據的至少兩個哈希值，當待存儲數據的各存儲位置中存在空閒的存儲位置時，將待存儲數據存儲在一個空閒的存儲位置中，當待存儲數據的各存儲位置均不空閒時，根據待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對待存儲數據進行存儲處理；本實施例利用多種哈希算法來生成待存儲數據的多個存儲位置，當其存儲位置與已存儲數據的存儲位置出現衝突，通過迭代查找和數據移動來克服出現的衝突，從而可以有效減少哈希衝突，提高了資源的使用效率。最後應說明的是以上各實施例僅用以說明本發明的技術方案，而非對其限制；儘管參照前述各實施例對本發明進行了詳細的說明，本領域的普通技術人員應當理解其依然可以對前述各實施例所記載的技術方案進行修改，或者對其中部分或者全部技術特徵進行等同替換；而這些修改或者替換，並不使相應技術方案的本質脫離本發明各實施例技術方案的範圍。
權利要求
1.一種哈希數據存儲方法，其特徵在於，包括 採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取所述待存儲數據的至少兩個哈希值，各哈希值分別與各哈希算法相對應； 當所述待存儲數據的各存儲位置中存在空閒的存儲位置時，將所述待存儲數據存儲在一個空閒的存儲位置中；其中，所述待存儲數據的各存儲位置為所述待存儲數據的至少兩個哈希值分別對應的存儲位置； 當所述待存儲數據的各存儲位置均不空閒時，根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理；其中，所述第一已存儲數據的其他存儲位置為所述第一已存儲數據的其他哈希值對應的存儲位置。
2.根據權利要求I所述的方法，其特徵在於，所述根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理包括 依次判斷所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置中是否存在空閒的存儲位置； 若所述待存儲數據的各存儲位置中一個或多個第一已存儲數據的其他存儲位置中存在空閒的存儲位置，則將一個第一已存儲數據遷移到所述第一已存儲數據的空閒的存儲位置，將所述待存儲數據存儲在所述第一已存儲數據的原存儲位置； 若所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置均不空閒，則根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理。
3.根據權利要求2所述的方法，其特徵在於，所述根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理包括 依次判斷所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置中是否存在空閒的存儲位置； 若所述各第一已存儲數據的各存儲位置中一個或多個第二已存儲數據的其他存儲位置中存在空閒的存儲位置，則將一個第二已存儲數據遷移到所述第二已存儲數據的空閒的存儲位置，將所述第二已存儲數據對應的第一已存儲數據遷移到所述第二已存儲數據的原存儲位置，將所述待存儲數據存儲在所述第一已存儲數據的原存儲位置。
4.根據權利要求3所述的方法，其特徵在於，所述根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理還包括 若所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置均不空閒，則將所述第二已存儲數據作為第一已存儲數據，遞歸執行所述根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理的步驟，直到上述遞歸次數達到預設的遞歸次數閾值為止。
5.權利要求1-4中任一項所述的方法，其特徵在於，在所述根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理之後，還包括 採用數據存儲時所使用的多個哈希算法分別對待查詢數據進行哈希處理，獲取所述待查詢數據的多個哈希值，各哈希值分別與各哈希算法相對應； 在所述待查詢數據的各哈希值對應的存儲空間中的存儲位置分別查詢所述待存儲數據。
6.一種哈希數據存儲裝置，其特徵在於，包括 第一哈希處理模塊，用於採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取所述待存儲數據的至少兩個哈希值，各哈希值分別與各哈希算法相對應； 第一存儲模塊，用於當所述待存儲數據的各存儲位置中存在空閒的存儲位置時，將所述待存儲數據存儲在一個空閒的存儲位置中；其中，所述待存儲數據的各存儲位置為所述待存儲數據的至少兩個哈希值分別對應的存儲位置； 第二存儲模塊，用於當所述待存儲數據的各存儲位置均不空閒時，根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理；其中，所述第一已存儲數據的其他存儲位置為所述第一已存儲數據的其他哈希值對應的存儲位置。
7.根據權利要求6所述的裝置，其特徵在於，所述第二存儲模塊包括 判斷單元，用於當所述待存儲數據的各存儲位置均不空閒時，依次判斷所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置中是否存在空閒的存儲位置； 第一存儲單元，用於若所述判斷單元的判斷結果為所述待存儲數據的各存儲位置中一個或多個第一已存儲數據的其他存儲位置中存在空閒的存儲位置，則將一個第一已存儲數據遷移到所述第一已存儲數據的空閒的存儲位置，將所述待存儲數據存儲在所述第一已存儲數據的原存儲位置； 第二存儲單元，用於若所述判斷單元的判斷結果為所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置均不空閒，則根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行存儲處理。
8.根據權利要求7所述的裝置，其特徵在於，所述第二存儲單元包括 判斷子單元，用於依次判斷所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置中是否存在空閒的存儲位置； 第一存儲子單元，用於若所述判斷子單元的判斷結果為所述各第一已存儲數據的各存儲位置中一個或多個第二已存儲數據的其他存儲位置中存在空閒的存儲位置，則將一個第二已存儲數據遷移到所述第二已存儲數據的空閒的存儲位置，將所述第二已存儲數據對應的第一已存儲數據遷移到所述第二已存儲數據的原存儲位置，將所述待存儲數據存儲在所述第一已存儲數據的原存儲位置。
9.根據權利要求8所述的裝置，其特徵在於，所述第二存儲單元還包括 第二存儲子單元，用於若所述判斷子單元的判斷結果為所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置均不空閒，則將所述第二已存儲數據作為第一已存儲數據，遞歸執行所述根據所述各第一已存儲數據的其他存儲位置中各第二已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理的步驟，直到上述遞歸次數達到預設的遞歸次數閾值為止。
10.根據權利要求6-9中任一項所述的裝置，其特徵在於，還包括 第二哈希處理模塊，用於在所述根據所述待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對所述待存儲數據進行遞歸存儲處理之後，採用所述第一哈希處理模塊所使用的多個哈希算法分別對待查詢數據進行哈希處理，獲取所述待查詢數據的多個哈希值，各哈希值分別與各哈希算法相對應； 查詢模塊，用於在所述待查詢數據的各哈希值對應的存儲空間中的存儲位置分別查詢所述待存儲數據。
全文摘要
本發明提供一種哈希數據存儲方法和裝置，方法包括採用至少兩種哈希算法分別對待存儲數據進行哈希處理，獲取待存儲數據的至少兩個哈希值，各哈希值分別與各哈希算法相對應；當待存儲數據的各存儲位置中存在空閒的存儲位置時，將待存儲數據存儲在一個空閒的存儲位置中；當待存儲數據的各存儲位置均不空閒時，根據待存儲數據的各存儲位置中各第一已存儲數據的其他存儲位置的存儲情況對待存儲數據進行迭代遞歸存儲處理；本發明還提供了一種哈希數據存儲裝置。本發明可以有效減少哈希衝突，提高了資源的使用效率。
文檔編號G06F17/30GK102880628SQ201210199209
公開日2013年1月16日 申請日期2012年6月15日 優先權日2012年6月15日
發明者陳佳泳 申請人:福建星網銳捷網絡有限公司