科创中国

电子信息技术

本发明公开了一种针对非易失内存的哈希表构建方法及系统。本发明方法构建一个哈希表，该哈希表逻辑上构建成一个倒立的完全二叉树，该二叉树的所有叶子节点是可寻址的单元，所有的非叶子节点是不可寻址单元且作为叶子节点处理哈希冲突的备用单元；从叶子节点到根节点路径上的所有非叶子节点用于存储在该叶子节点处发生哈希冲突的冲突元素；进一步删除该二叉树底部的多层只保留顶部剩余的层；该哈希表中每个元素对应两个不同的哈希位置，这两个哈希位置通过使用两个不同的哈希函数计算得到。本发明还实现了一种针对非易失内存的哈希表构建系统。本发明技术方案所构建的哈希表不会造成任何额外的写，并且具有高的空间利用率和低的请求延迟。

传统的内存技术DRAM和SRAM，已经被广泛使用在计算机系统的内存层次中分别作为主存和片上缓存。但是这些传统的内存技术面临不断增加的泄漏功耗和有限的可扩展性等问题。新型的非易失内存技术(NVM)，如相变存储器(PCM)，阻变存储器(ReRAM)和自旋扭矩存储器(STT-RAM)，由于具有高密度、高可扩展性和接近于零的待机能耗等优点，被提出作为DRAM和SRAM的替代品。然而，NVM在写耐久性和写性能上具有一定的局限性。NVM的存储单元只能容忍有限次数的写，例如PCM的每个存储单元只能写1000万到1亿次。对NVM的写操作不仅磨损有限的耐久性，并且造成比读操作更高的延迟和能耗开销。

冯丹，1970年5月生，湖北京山人，华中科技大学计算机学院院长，教授，博士生导师。信息存储系统教育部重点实验室副主任，武汉光电国家实验室（筹），兼任中国计算机学会外部设备专业委员会委员，中国计算机学会信息存储技术专业委员会委员，中国电子工业标准化技术协会海量存储标准工作委员会副主任委员武汉市科学技术协会常委，武汉市政协委员，第十三届全国人大代表。