[發明專利]基于碰撞的帶老化刪除的雙層無鎖哈希表實現方法有效
| 申請號： | 202110032390.0 | 申請日： | 2021-01-11 |
| 公開（公告）號： | CN112783894B | 公開（公告）日： | 2022-12-20 |
| 發明（設計）人： | 譚宇翔 | 申請（專利權）人： | 山東兆物網絡技術股份有限公司 |
| 主分類號： | G06F16/22 | 分類號： | G06F16/22;G06F16/901 |
| 代理公司： | 青島發思特專利商標代理有限公司 37212 | 代理人： | 劉濤 |
| 地址： | 255000 山東*** | 國省代碼： | 山東;37 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 基于 碰撞 老化 刪除 雙層 無鎖哈希表 實現 方法 | ||
【權利要求書】：
1.一種基于碰撞的帶老化刪除的雙層無鎖哈希表實現方法，其特征在于，包括以下步驟：
S1：設置雙層哈希表；S1的具體步驟包括設置兩個不同的哈希函數，分配雙層哈希表，針對相同key進行計算，分別得出兩個不同的索引值，其中一個索引值定位第一層表位置，第二個索引值定位第二層表位置；
S2：進行無鎖操作；S2的具體步驟包括：哈希表入口的數據結構以跳躍表作為基本數據結構，在跳躍表的基礎上加大節點層數，形成多級鏈表；
S3：進行跳躍表+雙向鏈表的運行方式；步驟S3中將哈希表入口更改為跳躍表+雙向鏈表的運行方式，每當插入/查詢/刪除時，同時操作兩個數據結構，需要做如下更改:
雙向鏈表的key按照時間戳進行升序排列，每當插入某個元素或者查找到某個元素，將該元素置頂到該表頭；
跳躍表的key按照第三套哈希算法計算，進行排序并存儲，更改完畢后，跳躍表的表頭按分層進行查詢/插入/刪除/修改,雙向鏈表表尾指向的內容就是按時間排序的最不活躍的元素內容；
S4：在步驟S3的基礎上，執行FIFO控制；所述步驟S4具體操作如下：當元素刪除時，先將元素的key從上述兩個數據結構中摘除，然后將其放入該入口的freelist中，freelist以FIFO的方式實現，每壓進一個元素，就把頭元素進行刪除。
下載完整專利技術內容需要扣除積分，VIP會員可以免費下載。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于山東兆物網絡技術股份有限公司，未經山東兆物網絡技術股份有限公司許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/202110032390.0/1.html，轉載請聲明來源鉆瓜專利網。
