基于双计数布鲁姆过滤器的哈希方法和哈希装置

摘要

本发明提供一种哈希方法，用于在哈希表上实现哈希插入操作；哈希表包括多个存储桶，存储桶包括插入计数器和删除计数器，插入计数器用于记录所在存储桶中所插入元素的个数，删除计数器用于记录所在存储桶中删除元素的个数；该方法包括：将所要操作的元素按照哈希函数映射到哈希表的至少一个存储桶，存储桶被称为候选存储桶；根据目标存储桶的选取原则从候选存储桶中找出目标存储桶；在目标存储桶中插入所要插入的元素；判断新插入的元素是否对候选存储桶中先前已存储元素的存储位置造成影响，若已存储元素的存储位置已经不再满足目标存储桶的选取原则，则对已存储元素的存储位置重新进行调整；还包括累加所述候选存储桶的插入计数器的值的步骤。

主权项

1、一种哈希装置，其特征在于，包括存储桶、候选存储桶查找模块、目标存储桶查找模块以及元素插入模块；其中，所述的存储桶包括插入计数器和删除计数器，所述插入计数器用于记录所在存储桶中所插入元素的个数，所述删除计数器用于记录所在存储桶中删除元素的个数；所述的候选存储桶查找模块用于将所要操作的元素按照哈希函数映射到一个存储桶，所述存储桶被称为候选存储桶；所述的目标存储桶查找模块用于根据目标存储桶的选取原则从所述候选存储桶中找出目标存储桶；所述选取原则包括从所述候选存储桶中选出插入计数器值与删除计数器值之和最小的候选存储桶作为目标存储桶，若所能得到的插入计数器值与删除计数器值之和最小的候选存储桶多余一个，则根据存储桶索引值选择目标存储桶；所述的元素插入模块用于在所述目标存储桶中插入所要插入的元素；用于判断新插入的元素是否对所述候选存储桶中先前已存储元素的存储位置造成影响，若已存储元素的存储位置已经不再满足所述的目标存储桶的选取原则，则根据所述的目标存储桶的选取原则对所述已存储元素的存储位置重新进行调整；用于累加所述候选存储桶的插入计数器的值。