(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210685649.6 (22)申请日 2022.06.16 (71)申请人 南京邮电大 学 地址 210046 江苏省南京市文苑路9号 (72)发明人 王俊昌　刘敦伟　肖甫　樊卫北　 何昕　田臣　 (74)专利代理 机构 南京经纬专利商标代理有限 公司 32200 专利代理师 陈月菊 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/2455(2019.01) (54)发明名称 一种关键数据结构的动态重构方法 (57)摘要 本发明公开了一种关键数据结构的动态重 构方法， 此方法适用于多种数据结构， 以哈希表 为例， 首先新建一个哈希表， 用于存储旧的哈希 表中的节点； 遍历旧哈希表中每个哈希桶的节 点， 对于每个节点， 首先全局指针指向该节 点， 此 时该节点进入危险期然后将该节点从旧哈希表 中删除； 根据新的哈希表的哈希函数， 确定当前 节点在新哈希表中的位置， 将当前节 点插入到新 哈希表中， 同步将全局指针设为NULL， 当前节点 结束危险期状态； 重复上述操作， 直至旧哈希表 中节点数为0， 删除旧哈希表。 本发明通过动态改 变哈希函数来重建哈希表， 解决健壮性问题， 使 用全局指针解决了在重建哈希表的过程中由于 伴随着并发的插入、 删除以及查询操作所导致的 数据短暂丢失的问题。 权利要求书2页 说明书5页 附图4页 CN 115098497 A 2022.09.23 CN 115098497 A 1.一种关键数据结构的动态重构方法， 其特 征在于， 所述重构方法包括以下步骤： S1， 新建一个哈希 表， 用于存 储旧的哈希 表中的节点； S2， 遍历旧哈希表中每个哈希桶的节点， 对于每个哈希桶中的每个节点， 全局指针指向 该节点， 该节点进入危险期， 转入步骤S3； 所述危险期是指分发节点过程中， 指定节点已经 从旧的哈希 表中删除， 但尚未存 入新的哈希 表的一段时间； S3， 将该节点从旧哈希 表中删除； S4， 根据新的哈希表的哈希函数， 确定当前节点在新哈希表中的位置， 将当前节点插入 到新哈希 表中， 同步将全局指针调整为 NULL， 该节点结束危险期状态； S5， 重复步骤S2 ‑S4， 直至旧哈希 表中节点数为0， 删除旧哈希 表。 2.根据权利1所述的关键数据 结构的动态重构方法， 其特征在于， 所述重构方法应用于 查找操作时， 包括以下 具体步骤： S21， 根据外 部输入的节点的键值， 确定待查找 节点的键值 为key； S22， 在旧哈希表中确定键值为key的节点所在的哈希桶， 遍历该哈希桶， 查找键值为 key的节点， 若查找到键值为key 的节点， 则返回该节点的指针， 结束流程； 若未查找到键值 为key的节点， 则转入步骤S23； S23， 判断当前是否有重建操作正在执行， 如没有重建操作正在执行， 则返回 ‑ENOENT， 表示哈希表中没有键值为key 的节点， 结束流程； 若当前有重建操作正在执行， 则转入步骤 S24； S24， 遍历处于危险期的节点， 查找键值为key的节点， 若查找到键值为key的节点， 返回 该节点的指针， 结束流 程； 若未查找到 键值为key的节点， 则转入步骤S25； S25， 在新哈希表中确定键值为key的节点所在的哈希桶， 遍历该哈希桶， 查找键值为 key的节点， 若查找到键值为key 的节点， 返回该节点的指针， 结束流程； 若未查找到键值为 key的节点， 则查找结束， 返回 ‑ENOENT， 表示哈希 表中没有键值 为key的节点。 3.根据权利1所述的关键数据 结构的动态重构方法， 其特征在于， 所述重构方法应用于 删除操作时， 包括以下 具体步骤： S26， 根据外 部输入的节点的键值， 确定待删除节点的键值 key； S27， 在旧哈希表中确定键值为key的节点所在的哈希桶位置， 尝试删除键值为key的节 点； 如删除成功， 则返回SUC CESS， 结束流 程； 如未删除成功， 则转入步骤S28； S28， 判断是否有重建操作正在执行， 如没有重建操作在执行， 则删除结束， 返回 ‑ ENOENT， 表 示哈希表中没有键值为key的节 点， 删除失败； 如有重 建操作在执行， 则转入步骤 S29； S29， 遍历处于危险期的节点， 尝试删除键值为key的节点， 如成功删除， 则返回 SUCCESS， 流程结束； 如未删除成功， 则转入步骤S3 0； S30， 在新哈希表中确定键值为key的节点所在哈希桶的位置， 尝试删除键值为key的节 点， 如删除成功， 返回SUCCESS， 流程结束； 如未删除成功， 则删除结束， 返回 ‑ENOENT， 表示哈 希表中没有键值 为key的节点， 删除失败。 4.根据权利1所述的关键数据 结构的动态重构方法， 其特征在于， 所述重构方法应用于 插入操作时， 包括以下步骤： S31， 根据外 部输入的节点的键值， 确定待插 入节点的键值 key；权　利　要　求　书 1/2 页 2 CN 115098497 A 2S32， 判断是否有重建操作正在执行， 如没有重建操作正在执行， 则转入步骤S33； 如有 重建操作正在执 行， 则转入步骤S34； S33： 在旧哈希表中确定键值为key的节点哈希桶的位置， 插入键值为key的节点； 如插 入成功， 则返回SUC CESS， 流程结束； 如插 入失败， 则转入步骤S3 6； S34， 在旧哈希表和处于危险期的节点中查找键值为key的节点； 如找键值为key的节 点， 转入步骤S3 6； 如未找键值 为key的节点， 则转入步骤S3 5； S35， 在新哈希表查找键值为key的节点所在哈希桶的位置， 在所属的哈希桶 中插入键 值为key的节点， 如插 入成功， 则返回SUC CESS， 结束流 程； 如插入失败， 则转入步骤S3 6； S36， 结束插 入流程， 返回‑EEXIST， 表示哈希 表中存在键值 为key的节点， 插 入失败。权　利　要　求　书 2/2 页 3 CN 115098497 A 3