[發(fā)明專利]用于管理哈希表的方法、設(shè)備和計算機程序產(chǎn)品

在審

• 申請?zhí)枺?/td>: 201810048717.1
• 申請日: 2018-01-18
• 公開（公告）號: CN110109915A
• 公開（公告）日: 2019-08-09
• 發(fā)明（設(shè)計）人: 何哲;高雷;方皓;李志強;陳歡
• 申請（專利權(quán)）人: 伊姆西IP控股有限責(zé)任公司
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 北京市金杜律師事務(wù)所 11256
• 代理人: 王茂華

1.一種用于管理哈希表的方法，包括：

響應(yīng)于接收到寫入請求，確定與所述寫入請求相關(guān)聯(lián)的第一哈希值是否存儲于哈希表集合中，所述哈希表集合包括至少第一哈希表和第二哈希表，所述第一哈希表為第一存儲設(shè)備中當(dāng)前有效的哈希表，所述第二哈希表存儲于第二存儲設(shè)備中，所述第一存儲設(shè)備的訪問速度快于所述第二存儲設(shè)備；

響應(yīng)于確定所述第一哈希值未存儲于所述哈希表集合中并且哈希所述第一哈希表已滿，將所述第一存儲設(shè)備中預(yù)分配的第三哈希表作為所述第一存儲設(shè)備中當(dāng)前有效的哈希表；

向所述第三哈希表中寫入第一條目，所述第一條目包括所述第一哈希值；以及

將所述第一哈希表中的條目與所述第二哈希表中的條目進行合并以便存儲到所述第二存儲設(shè)備中。

2.根據(jù)權(quán)利要求1所述的方法，其中將所述第一哈希表中的條目與所述第二哈希表中的條目進行合并包括：

確定所述第一哈希表中的條目數(shù)目與所述第二哈希表中的條目數(shù)目之和是否達預(yù)定閾值；以及

響應(yīng)于所述和低于所述預(yù)定閾值，將所述第一哈希表中的條目和所述第二哈希表中的條目按哈希值大小順序?qū)懭氲剿龅诙１碇小?/p>

3.根據(jù)權(quán)利要求2所述的方法，還包括：

響應(yīng)于所述和達到所述預(yù)定閾值，將所述第一哈希表中的條目和所述第二哈希表中的條目按哈希值大小順序?qū)憣懭氲筋A(yù)分配的第四哈希表中。

4.根據(jù)權(quán)利要求2或3所述的方法，還包括：

從所述第一存儲設(shè)備中移除所述第一哈希表。

5.根據(jù)權(quán)利要求1所述的方法，還包括：

響應(yīng)于接收到刪除請求，確定所述第三哈希表是否已滿；以及

響應(yīng)于確定所述第三哈希表未滿，向所述第三哈希表寫入第二條目，所述第二條目包括與所述用戶刪除請求相關(guān)聯(lián)的第二哈希值；以及

在所述第三哈希表中對所述第二條目進行標記以指示所述第二哈希值將要被刪除。

6.根據(jù)權(quán)利要求5所述的方法，其中將所述第一哈希表中的條目與所述第二哈希表中的條目進行合并包括：

確定所述第一哈希表和所述第二哈希表中是否存在未被標記的第三條目，所述第三條目包括所述第二哈希值；以及

響應(yīng)于所述第三哈希表或所述第二哈希表中存在所述第三條目，從所述第一哈希表或所述第二哈希表中刪除所述第二條目和所述第三條目。

7.根據(jù)權(quán)利要求1所述的方法，其中確定第一哈希值是否存儲于哈希表集中包括：

確定所述第一哈希值是否存儲于所述第一哈希表中；

響應(yīng)于所述第一哈希值未存儲于所述第一哈希表中，使用布隆過濾器將所述第一哈希值映射到多個位，所述布隆過濾器與所述第二哈希表相關(guān)聯(lián)；以及

響應(yīng)于確定所述多個位中存在零位，確定所述第一哈希值未存儲于所述第二哈希表中。

8.根據(jù)權(quán)利要求7述的方法，還包括：

響應(yīng)于所述多個位中無零位，基于頁面索引確定所述第二哈希表中與所述第一哈希值相關(guān)聯(lián)的頁面，所述頁面索引存儲于所述第一存儲設(shè)備中；以及

從所述頁面中查詢所述第一哈希值。

9.根據(jù)權(quán)利要求7述的方法，其中所述布隆過濾器存儲于所述第一存儲設(shè)備中。

10.根據(jù)權(quán)利要求1所述的方法，其中在確定所述第一哈希值是否存儲于哈希表集合中前還包括：

基于所述第一哈希值，從多個哈希表集合中確定與所述第一哈希表相關(guān)聯(lián)的哈希表集合。