一种OpenGauss哈希连接中哈希表的访问方法_CN116756180A_海量数据.pdf
免费下载
(19)国家知识产权局
(12)发明专利申请
(10)申请公布号
(43)申请公布日
(21)申请号 202310533714 .8
(22)申请日 2023 .05 .12
(71)申请人 广州海量数据库技术有限公司
地址 510510 广东省广州市天河区建工路4
号佳都科技大厦2号楼3F301(仅限办
公）
(72)发明人 王皓 何小栋
(74)专利代理机构 北京尚钺知识产权代理事务
所(普通合伙) 11723
专利代理师 严田青
(51)Int.Cl.
G06F
16/2453
(2019 .01)
G06F
16/22
(2019 .01)
(54)发明名称
一种OpenGauss哈希连接中哈希表的访问方
法
(57)摘要
本发明涉及一种OpenGauss哈希连接中哈希
表的优化访问方法及访问系统。本方法包括构建
哈希表，完成对哈希桶数组与哈希冲突数组的填
充；遍历哈希桶数组，探测各位置存储的数据是
否发生了哈希冲突；根据探测结果利用哈希桶数
组与哈希冲突数组中存储的位置信息的空余空
间填充提示信息等步骤。本方法融合了链地址法
和开放寻址法的优点，针对哈希表的实现从多个
角度进行了优化，通过填充提示信息来区别每个
冲突的数据究竟是使用了链地址法，还是开放寻
址法，很大程度上提高了哈希表的访问性能，另
外 利 用 本 方 法 给 出 的 提 示 信 息 无 需 访 问
HashNext数组即可判断数据是否发生了哈希冲
突，提升了哈希表的内存访问和哈希连接的性
能。
权利要求书2页 说明书6页 附图3页
CN 116756180 A
2023.09.15
CN 116756180 A
1 .一种OpenGauss哈希连接中哈希表的访问方法，其特征在于，所述方法包括：
S1 .构建哈希表，完成对哈希桶数组与哈希冲突数组的填充；
S2 .从哈希桶数组下标为0的位置开始对哈希桶数组进行遍历，探测存储在该位置的数
据是否发生了哈希冲突；
S3 .根据步骤S2的探测结果，利用哈希桶数组与哈希冲突数组中存储的原始数据在原
始数据数组中的位置信息的空余空间，填充提示信息；
S4 .重复步骤S2和步骤S3直至完成对哈希桶数组的探测。
2.根据权利要求1所述的OpenGauss哈希连接中哈希表的访问方法，其特征在于，步骤
S1中所述哈希桶数组与哈希冲突数组中存储的是原始数据在原始数据数组中的位置信息，
所述位置信息由一个整形数据表示，采用int类型或long类型。
3 .根据权利要求1所述的OpenGauss哈希连接中哈希表的访问方法，其特征在于，步骤
S1中所述构建哈希表，包括：
S11 .从数据源获得M个数据，将其放入原始数据数组中；
S12.根据M值计算N值，N为从M开始的下一个以2为底次幂值；
S13 .遍历原始数据数组，计算每一个数据的哈希值H；
S14 .根据每个数据的哈希值H对N进行取模，通过取模结果计算出其在哈希桶数组中的
下标，并将该新数据在原始数据数组中的位置存储在哈希桶数组中；
S15 .重复步骤S13和步骤S14，直到将所有数据都存储在哈希桶数组与哈希冲突数组
中。
4 .根据权利要求3所述的OpenGauss哈希连接中哈希表的访问方法，其特征在于，S13中
所述计算每一个数据的哈希值H，当数据为整形数据时，计算哈希值H的方式是使用数据本
身的值。
5 .根据权利要求3所述的OpenGauss哈希连接中哈希表的访问方法，其特征在于，步骤
S14中所述将该数据在原始数据数组中的位置存储在哈希桶数组中，包括：
(1)当哈希桶数组中对应下标的存储位置空间没有被使用时，将新数据在原始数据数
组中的位置直接存储在该存储位置；
(2)当哈希桶数组中对应下标的存储位置空间已经被使用时，则先将其中的数据取出，
并根据该数据中的位置信息，将其存储到对应位置的哈希冲突数组中，然后将新数据在原
始数据数组中的位置存储在该存储位置。
6 .根据权利要求1所述的OpenGauss哈希连接中哈希表的访问方法，其特征在于，当所
述哈希桶数组与哈希冲突数组中存储的原始数据在原始数据数组中的位置信息为int类型
整形数据时，步骤S3中所述根据步骤S2的探测结果，利用哈希桶数组与哈希冲突数组中存
储的原始数据在原始数据数组中的位置信息的空余空间，填充提示信息，包括：
(1)数据间未发生哈希冲突，则在int类型的低位30bit填充原来的位置信息，在最高位
2bit填充提示信息01；
(2)数据间发生了哈希冲突，并且哈希桶数组中当前下标+1的空间被使用了，则在int
类型的低位30bit填充原来的位置信息，在最高位2bit填充提示信息11；
(3)数据间发生了哈希冲突，并且哈希桶数组中当前下标+1的空间未被使用，则在int
类型的低位30bit填充原来的位置信息，在最高位2bit填充提示信息10，并将本应存储在哈
权 利 要 求 书
1/2 页
2
CN 116756180 A
2
希冲突数组中的位置信息存储到哈希桶数组当前下标+1的位置，位置信息填充在该int类
型的低位30bit，最高位2bit填充提示信息10；
(4)当前哈希桶数组下标的空间未被使用，不做任何处理。
7 .根据权利要求6所述的OpenGauss哈希连接中哈希表的访问方法，其特征在于，所述
提示信息的含义如下：
0：表示哈希桶数组中当前下标的空间int类型的低位30bit没用被使用；
01：表示哈希桶数组中当前下标的空间int类型的低位30bit的数据没有发生哈希冲
突；
10：表示哈希桶数组中当前下标的空间int类型的低位30bit的数据发生了哈希冲突，
冲突的数据存储在哈希桶数组当前下标+1的空间中；
11：表示哈希桶数组中当前下标的空间int类型的低位30bit的数据发生了哈希冲突，
冲突的数据存储在哈希冲突数组中。
8.一种OpenGauss哈希连接中哈希表的访问系统，其特征在于，所述系统包括：
哈希表构建模块：用于构建哈希表，并完成对哈希桶数组与哈希冲突数组的填充；
哈希冲突探测模块：用于探测存储在哈希桶数组中的数据是否发生了哈希冲突；
提示信息填充模块：用于向哈希桶数组与哈希冲突数组中存储的位置信息的空余空间
中填充提示信息；
信息识别模块：用于识别提示信息并做出相应的处理决策。
9.一种计算机可读存储介质，所述存储介质上存储有计算机程序，所述程序被处理器
执行时实现权利要求1‑7任一项所述的OpenGauss哈希连接中哈希表的访问方法的步骤。
权 利 要 求 书
2/2 页
3
CN 116756180 A
3
of 12
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
最新上传
下载排行榜
1
2
centos7下oracle11.2.0.4 rac安装详细图文（虚拟机模拟多路径）.docx
3
白鳝-DBAIOPS：国产化替换浪潮进行时，信创数据库该如何选型？.pdf
4
PostgreSQL 缓存命中率低？可以这么做.doc
5
李飞-AI 引领的企业级智能分析架构演进与行业实践.pdf
6
达梦数据2024年年度报告.pdf
7
刘杰-江苏广电：从Oracle+Hadoop到TiDB，数据中台、实时数仓运维0负担.pdf
8
刘晓国-基于 Elasticsearch 创建企业 AI 搜索应用实践.pdf
9
晋鑫宇_AI Agent 赋能社交媒体-构建未来社交生态的核心驱动力.pdf
10
Sunny duan-大模型安全挑战与实践：构建 AI 时代的安全防线.pdf
相关文档
评论