海量数据处理方法和装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN111723266A(43)申请公布日2020.09.29(21)申请号201910207946.8(22)申请日2019.03.19(71)申请人北京沃东天骏信息技术有限公司地址100176北京市大兴区北京经济技术开发区科创十一街18号院2号楼4层A402室(72)发明人余伟伟闫创任莉强邢淇翔(74)专利代理机构中国贸促会专利商标事务所有限公司11038代理人许蓓(51)Int.Cl.G06F16/953(2019.01)G06F16/951(2019.01)G06F16/958(2019.01)权利要求书2页说明书9页附图6页(54)发明名称海量数据处理方法和装置(57)摘要本公开提出一种海量数据处理方法和装置，涉及计算机领域。通过第一元素的哈希值定位第一元素在哈希表的存储位置，然后在存储位置处的存储块保存的元素中查找第一元素，由于查找的是元素而非元素的哈希值，因此能够准确判断第一元素是否为重复元素，解决由于“哈希冲突”导致的重复元素判定错误的问题，并通过定位使得仅在少量几个元素中进行元素的查找，因此能够同时能兼顾重复元素的判定效率。本公开适用于海量数据处理的重复数据判定场景。CN111723266ACN111723266A权利要求书1/2页1.一种海量数据处理方法，其特征在于，包括：获取待处理的第一元素；计算第一元素的哈希值；从哈希表中确定第一元素的哈希值对应的存储块；从第一元素的哈希值对应的存储块中查找是否存在第一元素；如果查找到第一元素，输出第一元素是重复元素的结果。2.如权利要求1所述的方法，其特征在于，第一元素的哈希值包括：第一元素基于第一哈希函数进行哈希计算得到第一哈希值，以及，第一元素基于至少一个第二哈希函数分别进行哈希计算得到至少一个第二哈希值；在确定第一元素不是重复元素的情况下：如果第一元素在位数组中映射的多个位的值中含有初始值，将第一元素记录到哈希表的第一哈希值对应的第一存储块中，并将第一元素在位数组中映射的多个位的值变更为非初始值；如果第一元素在位数组中映射的多个位的值均为非初始值，将第一元素记录到哈希表的第二哈希值对应的第二存储块中。3.如权利要求2所述的方法，其特征在于，其中，从暂存区中读取待处理的第一元素；如果哈希表的第一哈希值对应的第一存储块没有空的存储位，将第一存储块中任意一个第一存储位的元素存放到暂存区，并将第一元素记录到第一存储位；或者，如果哈希表的第二哈希值对应的第二存储块没有空的存储位，将第二存储块中任意一个第二存储位的元素存放到缓存区，并将第一元素记录到第二存储位。4.如权利要求2所述的方法，其特征在于，所述变更方法包括：将第一哈希值或第一元素在位数组中映射的多个位的值变更为预设值，或者，将第一哈希值或第一元素在位数组中映射的多个位的值分别增加1。5.如权利要求2所述的方法，其特征在于，在所述变更方法为将第一元素在位数组中映射的多个位的值增加1的情况下，还包括：获取欲删除的第二元素，其中，第二元素基于第一哈希函数进行哈希计算得到第三哈希值，第二元素基于至少一个第二哈希函数分别进行哈希计算得到至少一个第四哈希值；判断第二元素在位数组中映射的多个位的值是否均为非初始值；如果第二元素在位数组中映射的多个位的值均为非初始值，从哈希表的第三哈希值对应的第三存储块中查找是否存在第二元素，从第三存储块中删除查找到的第二元素，并将第二元素在位数组中映射的多个位的值分别减小1；如果第二元素在位数组中映射的多个位的值中含有初始值或者从第三存储块中未查找到第二元素，从哈希表的第四哈希值对应的第四存储块中查找是否存在第二元素，从第四存储块中删除查找到的第二元素。6.如权利要求5所述的方法，其特征在于，如果从哈希表中未查找到第二元素，从缓存区中查找是否存在第二元素，从缓存区中删除查找到的第二元素；或者，如果从哈希表或缓存区中未查找到第二元素，从数据库中查找是否存在第二元素，从数据库中删除查找到的第二元素。2CN111723266A权利要求书2/2页7.如权利要求2所述的方法，其特征在于，从第一元素的哈希值对应的存储块中查找是否存在第一元素包括：判断第一元素在位数组中映射的多个位的值是否均为非初始值；如果第一元素在位数组中映射的多个位的值均为非初始值，从哈希表的第一哈希值对应的第一存储块中查找是否存在第一元素；如果第一元素在位数组中映射的多个位的值中含有初始值或者从第一存储块中未查找到第一元素，从哈希表的第二哈希值对应的第二存储块中查找是否存在第一元素。8.如权利要求7所述的方法，其特征在于，还包括：在判断步骤之前，从暂存区中查找是否存在第一元素；或者，如果从哈希表中未查找到第一元素，从缓存区中查找是否存在第一元素；或者，如果从哈希