适用于高速检索的完美Hash函数

• 作者: 王兴 鲍志伟
• 来源期刊: 计算机系统应用
• 关键词: 硬件Hash表 完美Hash函数 高速搜索 最小完美Hash表
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 研究开发
• 页码范围: 250-256
• 页数: 7页
• 字数: 4350字
• 语种: 中文

摘要

软件实现的Hash函数在当前检索领域应用非常广泛,但是由于处理速度不高,很难满足骨干网以及服务器海量数据的高速实时查找要求.硬件Hash函数处理速度快,但普遍存在设计电路复杂、存储空间利用率不高以及无法支持数据集动态更新等问题.基于位提取(Bit-extraction)算法,利用位选择(Bit-Selection)操作与位逻辑运算在FPGA上仿真实现一种Hash函数,可生成负载因子(Load factor)接近于1的近似最小完美Hash表.仿真结果表明,该Hash函数中每个24 bits长度Key的存储空间只要2.8-5.6 bits,系统时钟频率可以达到300MHz左右(吞吐率超过14Gbps).可以应用于IP地址查找、数据包分类、字符串匹配以及入侵检测等需要实时高速表查找的场景.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	鲍志伟	香港城市大学电子工程系	2	3	1.0	1.0