[發明專利]基于Cuckoo哈希計算的數據存儲優化方法及系統

有效

• 申請號: 201710415853.5
• 申請日: 2017-06-06
• 公開（公告）號: CN107256130B
• 公開（公告）日: 2019-09-24
• 發明（設計）人: 華宇;孫園園;馮丹
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 廖盈春;李智

1.一種基于Cuckoo哈希計算的數據存儲優化方法，其特征在于，包括以下步驟：

S1、根據元素屬性隨機選擇兩個相互獨立的哈希函數計算得到元素在索引表中對應的兩個候選哈希桶；

S2、根據元素所對應的兩個候選哈希桶是否屬于cuckoo圖，對元素進行分類，其中，v+0類表示元素所對應的兩個候選哈希桶都在cuckoo圖中，插入元素不會造成cuckoo圖節點數增加；v+1類表示元素所對應的兩個候選哈希桶只有一個存在于cuckoo圖中，插入元素會使cuckoo圖節點數加1；v+2類表示元素所對應的兩個候選桶之前都沒有被加入cuckoo圖中，插入元素會使cuckoo圖節點數加2；

S3、對于cuckoo圖中的每個子圖，若插入元素后子圖中的邊數等于節點數，則該子圖有且只有一個回路，并將該子圖稱為滿載子圖；若插入元素后子圖中的邊數不等于節點數，則將該子圖稱為非滿載子圖，其中，在cuckoo圖中，將索引表中每個桶看作是圖的一個節點，將索引表中每個元素看作是圖的一條邊；

S4、若元素的兩個候選哈希桶對應的兩個節點所屬的子圖為滿載子圖，則在元素插入導致的踢出路徑會形成回路導致無限循環，預測插入操作一定失敗；若元素的兩個候選哈希桶對應的兩個節點所屬的子圖中有非滿載子圖，則在非滿載子圖中一定存在一個空位，經過有限次踢出操作時，所有元素都將插入索引表中，預測插入操作一定成功，其中，兩個候選哈希桶對應的兩個節點屬于相同子圖或者兩個候選哈希桶對應的兩個節點屬于不同子圖；

S5、若預測插入操作失敗，則將元素存入臨時空間，不進行任何踢出操作；若預測插入操作成功，則根據Cuckoo哈希機制執行元素插入操作。

2.根據權利要求1所述的方法，其特征在于，步驟S2具體包括以下子步驟：

S2.1、判斷兩個候選哈希桶是否都已經存在于cuckoo圖中，若都存在，則該元素屬于v+0類，否則執行步驟S2.2；

S2.2、判斷是否有一個候選哈希桶存在于cuckoo圖中，若是，則該元素屬于v+1類，否則該元素屬于v+2類。

3.根據權利要求1所述的方法，其特征在于，步驟S4具體包括以下子步驟：

S4.1、判斷兩個候選哈希桶是否屬于同一子圖，若是則執行步驟S4.2；否則執行步驟S4.3；

S4.2、判斷該子圖是否為滿載子圖，若是滿載子圖，則預測插入一定失敗，若是非滿載子圖，則預測插入一定成功；

S4.3、判斷兩個子圖是否都滿載，若兩個子圖均是滿載子圖，則預測插入一定失敗，否則預測插入一定成功。

4.根據權利要求1至3任意一項所述的方法，其特征在于，步驟S5具體包括以下子步驟：

S5.1、判斷元素是否屬于v+0類，若是則任選一個對應非滿載子圖的候選哈希桶，然后執行步驟S5.2，否則執行步驟S5.4；

S5.2、判斷該候選哈希桶是否被其他元素占據，若沒有則將該元素直接插入該候選哈希桶，并將該候選哈希桶對應子圖的邊數加1；若有元素占據，則執行步驟S5.3；

S5.3、哈希計算得到該候選哈希桶所占據元素的另一個候選哈希桶，再將待插入元素插入該候選哈希桶，將原有元素踢出成為待插入元素，并返回步驟S5.2繼續執行；

S5.4、判斷該元素是否屬于v+1類，若是則將該元素插入對應子圖新增節點所對應的哈希桶中，并將對應子圖的節點數加1以及對應子圖的邊數加1；否則，該元素屬于v+2類型，分配一個新的子圖號，直接將元素插入任一新增節點的對應桶中，再設置新子圖的節點數為2，邊數為1。