[發(fā)明專利]一種基于哈希算法的數(shù)據(jù)存儲方法及裝置

有效

• 申請?zhí)枺?/td>: 201010281747.0
• 申請日: 2010-09-13
• 公開（公告）號: CN102402394A
• 公開（公告）日: 2012-04-04
• 發(fā)明（設計）人: 袁清;章建桂
• 申請（專利權）人: 騰訊科技(深圳)有限公司
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 北京德琦知識產(chǎn)權代理有限公司 11018
• 代理人: 王一斌;王琦

1.一種基于哈希算法的數(shù)據(jù)存儲方法，其特征在于，該方法包括：

預先設置L個后端存儲模塊以及后端存儲模塊標識與模L運算的映射關系，L為大于1的自然數(shù)；

根據(jù)Hash算法計算待存儲數(shù)據(jù)的主鍵值；

對獲取的主鍵值以后端存儲模塊數(shù)量為模執(zhí)行模運算，根據(jù)后端存儲模塊標識與模L運算的映射關系，將執(zhí)行模L運算的主鍵值及對應的數(shù)據(jù)輸出至相應標識的后端存儲模塊；

確定后端存儲模塊預先設置的Hash表中沒有存儲待存儲數(shù)據(jù)，存儲待存儲數(shù)據(jù)及對應的主鍵值。

2.如權利要求1所述的方法，其特征在于，所述確定后端存儲模塊預先設置的Hash表中沒有存儲待存儲數(shù)據(jù)，存儲待存儲數(shù)據(jù)及對應的主鍵值具體包括：

依序判斷后端存儲模塊預先設置的Hash表中是否存儲有待存儲數(shù)據(jù)對應的主鍵值，如果沒有，在該Hash表中存儲該主鍵值以及該主鍵值對應的數(shù)據(jù)；否則，將Hash表中存儲的數(shù)據(jù)與該主鍵值對應的數(shù)據(jù)進行匹配；

判斷Hash表中存儲的數(shù)據(jù)與該主鍵值對應的數(shù)據(jù)不相匹配，對Hash表中存儲的數(shù)據(jù)設置沖突標記，將該主鍵值加上預先設置的步長；

判斷加上預先設置的步長的次數(shù)沒有超過預先設置的閾值，返回執(zhí)行所述依序判斷后端存儲模塊預先設置的Hash表中是否存儲有待存儲數(shù)據(jù)對應的主鍵值的步驟。

3.如權利要求2所述的方法，其特征在于，所述預先設置的步長與預先設置的步長的次數(shù)的乘積模后端存儲模塊數(shù)量的余數(shù)為0。

4.如權利要求1至3任一項所述的方法，其特征在于，進一步包括：所述后端存儲模塊的數(shù)量以每次翻倍的方式進行擴容。

5.如權利要求1至3任一項所述的方法，其特征在于，進一步包括：

根據(jù)查詢請求獲取查詢請求對應的主鍵值；

對獲取的主鍵值以后端存儲模塊數(shù)量為模執(zhí)行模運算，根據(jù)后端存儲模塊標識與模L運算的映射關系，獲取主鍵值對應的后端存儲模塊；

搜索Hash表，獲取待查詢數(shù)據(jù)。

6.如權利要求5所述的方法，其特征在于，所述根據(jù)查詢請求獲取查詢請求對應的主鍵值具體包括：

獲取查詢請求，判斷查詢請求中攜帶的是數(shù)據(jù)還是已經(jīng)標識化的主鍵值，如果是數(shù)據(jù)，計算該數(shù)據(jù)對應的主鍵值，將計算得到的主鍵值作為查詢請求對應的主鍵值；如果是已經(jīng)標識化的主鍵值，將該標識化的主鍵值作為查詢請求對應的主鍵值。

7.如權利要求6所述的方法，其特征在于，當所述查詢請求中攜帶的是數(shù)據(jù)時，所述搜索Hash表，獲取待查詢數(shù)據(jù)具體包括：

搜索Hash表，確定有待查詢數(shù)據(jù)對應的主鍵值；

判斷存儲的該主鍵值對應的數(shù)據(jù)結構中是否置有沖突標記，如果沒有，返回查詢請求成功信息，攜帶該主鍵值對應的數(shù)據(jù)；如果有，將當前帶查詢數(shù)據(jù)對應的主鍵值加上預先設置的步長；

確定加上預先設置的步長的次數(shù)沒有超過預先設置的閾值，返回執(zhí)行所述搜索Hash表，確定有待查詢數(shù)據(jù)對應的主鍵值的步驟。

8.如權利要求6所述的方法，其特征在于，當所述查詢請求中攜帶的是標識化的主鍵值時，所述搜索Hash表，獲取待查詢數(shù)據(jù)具體包括：

搜索Hash表中是否有標識化的主鍵值，如果有，返回查詢請求成功信息，攜帶該標識化的主鍵值對應的數(shù)據(jù)。

9.一種基于哈希算法的數(shù)據(jù)存儲裝置，其特征在于，該裝置包括：多個后端存儲模塊、映射關系存儲模塊、主鍵值計算模塊以及模運算單元，其中，

映射關系存儲模塊，用于存儲后端存儲模塊標識與模L運算的映射關系，L為后端存儲模塊數(shù)量；

主鍵值計算模塊，用于根據(jù)Hash算法計算待存儲數(shù)據(jù)的主鍵值，輸出至模運算單元；

模運算單元，用于根據(jù)后端存儲模塊數(shù)量，對獲取的主鍵值取模，根據(jù)取模的余數(shù)從映射關系存儲模塊獲取取模的余數(shù)映射的后端存儲模塊標識，將執(zhí)行取模運算的主鍵值及對應的數(shù)據(jù)輸出至相應標識的后端存儲模塊；

后端存儲模塊，用于確定預先設置的Hash表中沒有存儲待存儲數(shù)據(jù)，存儲待存儲數(shù)據(jù)及對應的主鍵值。

10.如權利要求9所述的裝置，其特征在于，所述后端存儲模塊為隨機存儲器、閃存、可擦寫存儲器或硬盤。

11.如權利要求9所述的裝置，其特征在于，所述后端存儲模塊包括：主鍵值查詢單元、Hash表存儲單元、數(shù)據(jù)匹配單元以及主鍵值沖突處理單元，其中，

主鍵值查詢單元，用于依序判斷Hash表中是否存儲有待存儲數(shù)據(jù)對應的主鍵值，如果沒有，將該主鍵值以及該主鍵值對應的數(shù)據(jù)輸出至Hash表中進行存儲；如果有，將該主鍵值以及該主鍵值對應的數(shù)據(jù)輸出至數(shù)據(jù)匹配單元；

數(shù)據(jù)匹配單元，用于將接收的數(shù)據(jù)與Hash表中存儲的數(shù)據(jù)進行匹配，如果相同，不作處理；否則，對存儲的數(shù)據(jù)設置沖突標記，將該主鍵值輸出至主鍵值沖突處理單元；

主鍵值沖突處理單元，用于將接收的主鍵值加上預先設置的步長，判斷加上預先設置的步長的次數(shù)是否超過預先設置的閾值，如果是，不作處理；否則，將加上預先設置步長的主鍵值輸出至主鍵值查詢單元。