一种针对非易失内存的哈希表构建方法及系统.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN107153707A(43)申请公布日2017.09.12(21)申请号201710332674.5(22)申请日2017.05.12(71)申请人华中科技大学地址430074湖北省武汉市洪山区珞喻路1037号(72)发明人华宇左鹏飞冯丹(74)专利代理机构华中科技大学专利中心42201代理人廖盈春李智(51)Int.Cl.G06F17/30(2006.01)权利要求书2页说明书4页附图2页(54)发明名称一种针对非易失内存的哈希表构建方法及系统(57)摘要本发明公开了一种针对非易失内存的哈希表构建方法及系统。本发明方法构建一个哈希表，该哈希表逻辑上构建成一个倒立的完全二叉树，该二叉树的所有叶子节点是可寻址的单元，所有的非叶子节点是不可寻址单元且作为叶子节点处理哈希冲突的备用单元；从叶子节点到根节点路径上的所有非叶子节点用于存储在该叶子节点处发生哈希冲突的冲突元素；进一步删除该二叉树底部的多层只保留顶部剩余的层；该哈希表中每个元素对应两个不同的哈希位置，这两个哈希位置通过使用两个不同的哈希函数计算得到。本发明还实现了一种针对非易失内存的哈希表构建系统。本发明技术方案所构建的哈希表不会造成任何额外的写，并且具有高的空间利用率和低的请求延迟。CN107153707ACN107153707A权利要求书1/2页1.一种针对非易失内存的哈希表构建方法，其特征在于，所述方法包括以下步骤：(1)位置共享：将哈希表中的所有存储单元逻辑上组织成一个倒立的完全二叉树，该二叉树顶层的所有叶子结点为哈希函数寻址单元，当叶子结点发生哈希冲突的时候，冲突元素储存在叶子结点到根节点路径上的非叶子结点中；(2)路径缩减：只保留所述二叉树最顶部的K层；(3)双路径哈希：所述哈希表中每个元素使用两个不同的哈希函数对应到两个不同的哈希位置。2.根据权利要求1所述的一种针对非易失内存的哈希表构建方法，其特征在于，将所述二叉树的所有节点由顶层到底层依次存储在一个一维数组中，二叉树中第N层所有节点占据所述一维数组中的2L-(L-N)个位置。3.根据权利要求1所述的一种针对非易失内存的哈希表构建方法，其特征在于，所述哈希表中每个单元存储三项数据，分别是单元标识、存储元素键值和存储元素值；单元标识为“0”表示该单元为空，单元标识为“1”表示该单元被占用。4.根据权利要求1所述的一种针对非易失内存的哈希表构建方法，其特征在于，所述哈希表包括以下操作：插入操作：要插入一个新的元素<key,value>，其中key表示存储元素键值，value表示存储元素值；将key带入哈希函数计算哈希位置p1和p2，判断叶子节点p1和p2中是否有空节点，是则将新的元素存入其中一个空节点并将单元标识token置为“1”；否则继续迭代遍历路径-p1和-p2在下一层的节点，直至找到一个空的节点将新的元素存入，并将token置为“1”；若遍历完两条路径依然没有找到空节点，则插入失败，其中，所述路径-p1和-p2分别表示叶子节点p1和p2到根节点的路径；查询操作：通过哈希函数计算查询key对应的哈希位置p1和p2，由顶层到底层迭代遍历路径-p1和-p2中的节点寻找目标元素，找到后返回目标元素的value，若遍历完路径-p1和-p2后没有找到目标元素，则查询目标不在哈希表中；删除操作：通过哈希函数计算查询key对应的哈希位置p1和p2，由顶层到底层迭代遍历路径-p1和-p2中的节点寻找目标元素，找到后将目标元素的token置为“0”，若没有找到目标元素则删除目标不在哈希表中。5.一种针对非易失内存的哈希表构建系统，其特征在于，所述系统包括：位置共享模块，用于将哈希表中的所有存储单元逻辑上组织成一个倒立的完全二叉树，该二叉树顶层的所有叶子结点为哈希函数寻址单元，当叶子结点发生哈希冲突的时候，冲突元素储存在叶子结点到根节点路径上的非叶子结点中；路径缩减模块，用于只保留所述二叉树最顶部的K层；双路径哈希模块，用于将所述哈希表中每个元素使用两个不同的哈希函数对应到两个不同的哈希位置。6.根据权利要求5所述的一种针对非易失内存的哈希表构建系统，其特征在于，所述二叉树的所有节点由顶层到底层依次存储在一个一维数组中，二叉树中第N层所有节点占据所述一维数组中的2L-(L-N)个位置。7.根据权利要求5所述的一种针对非易失内存的哈希表构建系统，其特征在于，所述哈希表中每个单元存储三项数据，分别是单元标识、存储元素键值和存储元素值；单元标识为2CN107153707A权利要求书2/2页“0”表示该单元为空，单元标识为“1”表示该单元被占用。8.根据权利要求5所述的一种针对非易失内存的哈希表构建系统，其特征在于，所述哈希表包括以下操作：插入操作：要插入