[發(fā)明專利]一種結(jié)構(gòu)緊湊的鍵值對存儲結(jié)構(gòu)及快速鍵值對查找方法

有效

• 申請?zhí)枺?/td>: 201711287661.7
• 申請日: 2017-12-07
• 公開（公告）號: CN108021678B
• 公開（公告）日: 2022-05-17
• 發(fā)明（設計）人: 嵩天;魏煜
• 申請（專利權(quán)）人: 北京理工大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/242;G06F16/2455
• 代理公司: 北京正陽理工知識產(chǎn)權(quán)代理事務所(普通合伙) 11639
• 代理人: 鮑文娟

1.一種快速鍵值對查找方法，包括基于分層哈希表和布魯姆過濾器相結(jié)合的存儲結(jié)構(gòu)，通過首層使用2-left hashing 哈希結(jié)構(gòu)存儲，每層哈希表都作為輔助表保存在上層表中發(fā)生存儲沖突的數(shù)據(jù)，每層哈希表結(jié)合布魯姆過濾器進行沖突數(shù)據(jù)的保存，將“布魯姆過濾器判斷所查找的鍵是否存在當前集合中的結(jié)果”作為索引提高查找速度，從而提高存儲空間利用率使結(jié)構(gòu)緊湊并實現(xiàn)快速查找的軟件平臺要求，其特征在于：存儲結(jié)構(gòu)包括λ層哈希表，從第二層哈希表開始，每層哈希表中包含的總存儲塊數(shù)量呈等比序列遞減，其中，等比因子為10；

其中，首層哈希表存在左右兩個子表，每個子表中包含相同個數(shù)的存儲塊；對于其余層哈希表，不存在子表的概念；

每個存儲塊中第一個存儲單元保存該存儲塊中已被占用的存儲單元個數(shù)，其余存儲單元中存儲的是鍵值對；

其中，鍵值對包括鍵和值；具體存儲時存儲的是鍵的“值”和鍵的“校驗值”；其中，存儲的“值”部分可以存儲該值本身或者指向值本身存儲位置的指針，后文統(tǒng)稱為值；鍵的“校驗值”的計算可使用常用的校驗算法，所述校驗算法包括crc循環(huán)冗余校驗或md5校驗算法；

除最后一層哈希表外，每層哈希表對應一個布魯姆過濾器，從第一層布魯姆過濾器開始，每層布魯姆過濾器的所占空間大小呈等比序列遞減，其中，等比因子為10；

鍵值對數(shù)據(jù)存儲過程和鍵值對查找過程包括：

第一部分鍵值對數(shù)據(jù)存儲過程，即鍵值對插入過程，簡稱插入過程，具體步驟如下：

步驟1，設置哈希表層數(shù)以及每一層哈希表包含存儲塊的個數(shù)，同時設置每一層哈希表對應的布魯姆過濾器的大小；

步驟2，設置哈希表每個存儲塊中包含的存儲單元的個數(shù)N，設置每個存儲單元的大小為M比特；

步驟3, 向第一層哈希表中插入數(shù)據(jù)，所述第一層哈希表使用2-left hashing哈希表，若不沖突，則該鍵值對插入成功，跳至步驟5；若沖突，則將數(shù)據(jù)標記在第一層對應的bloomfilter中，并執(zhí)行步驟4；

步驟4，判斷當前層是否為最后一層，并根據(jù)判斷結(jié)果，若為最后一層，則跳入步驟7，若當前層不是哈希表結(jié)構(gòu)中的最后一層，應向當前層對應的布魯姆過濾器集合中添加當前鍵，跳至步驟5；

步驟5 跳入下一層哈希表中，進行一次哈希運算，使用此哈希運算的結(jié)果確定一個存儲塊位置，通過判斷該存儲塊和當前鍵是否存在沖突來進行如下操作：當出現(xiàn)插入數(shù)據(jù)沖突時，需要跳至步驟4；當插入數(shù)據(jù)不沖突時，將插入數(shù)據(jù)，即將該鍵的值和該鍵的校驗值保存到該存儲塊的第一個空閑的存儲單元中，進入步驟6；

步驟6，數(shù)據(jù)插入成功，即鍵值對插入函數(shù)調(diào)用成功，函數(shù)返回1，結(jié)束插入過程；

步驟7，數(shù)據(jù)插入失敗，即鍵值對插入函數(shù)調(diào)用失敗，函數(shù)返回0，結(jié)束插入過程；

至此，從步驟1到步驟6或步驟7，完成了插入過程；

第二部分鍵值對查找過程，即對于給出鍵值對中的鍵，查找對應鍵值對中的值的過程，簡稱查找過程，具體步驟如下：

步驟8，在第一層布魯姆過濾器集合中對給出鍵值對中的鍵進行查找，通過判斷該鍵是否在該集合中保存，決定跳至步驟10還是步驟9，具體為：

8.1 若該鍵不存在第一層布魯姆過濾器集合中，執(zhí)行步驟9；

8.2 若該鍵存在于第一層布魯姆過濾器集合中，執(zhí)行步驟10；

步驟9，在2-left hashing中進行兩次哈希計算，其結(jié)果在左右子表中分別確定一個存儲塊；將兩個存儲塊中每個非空單元內(nèi)的校驗值和“根據(jù)當前鍵計算出的校驗值”比較，查看是否存在相等的情況，決定跳至步驟13還是步驟14，具體為：

9.1 若存在相等的情況，則表示該單元保存的值即為所查找的鍵對應的值，跳至步驟13；

9.2 若不存在相等的情況，則鍵對應的值不存在于本存儲結(jié)構(gòu)中，跳至步驟14；

步驟10，進入下一層布魯姆過濾器，在下一層布魯姆過濾器集合中對給出的鍵進行查找，通過判斷該鍵是否在該布魯姆過濾器集合中來進行如下操作：

10.1 若該鍵存在于該布魯姆過濾器集合中，通過判斷當前布魯姆過濾器所在層是否為最后一層，決定跳至步驟11還是步驟10，具體為：

10.1A 若當前布魯姆過濾器所在層不是最后一層，跳至步驟10；

10.1B 若當前布魯姆過濾器所在層是最后一層，跳至步驟11；

10.2 若該鍵不存在于該層布魯姆過濾器集合中，進入當前布魯姆過濾器對應層的哈希表，跳至步驟12；

步驟11，進入最后一層哈希表；

步驟12，在當前層哈希表中查找鍵對應的校驗值，對鍵進行一次哈希運算，通過哈希運算的結(jié)果在哈希表中確定一個存儲塊，在存儲塊中遍歷每個非空單元的校驗值并比較是否與當前鍵的校驗值相等，根據(jù)是否存在相等的情況，判斷跳至步驟13還是步驟14，具體為：

12.1 若存在相等的情況，即找到了相等的校驗值，則進入步驟13；

12.2 若不存在相等的情況，即沒找到相等的校驗值，則進入步驟14；

步驟13，查找函數(shù)調(diào)用成功，函數(shù)返回當前存儲單元中保存的值，結(jié)束查找；

步驟14，查找函數(shù)調(diào)用失敗，函數(shù)返回0，結(jié)束查找；

至此，從步驟8到步驟13或步驟14，完成了一種快速鍵值對查找方法。