适用于高速检索的完美Hash函数
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

香港研究资助局项目(CityU 119809);浙江广厦建设职业技术学院重点项目(2015005)


Perfect Hash Function for High-Speed Searching
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Software-based hash function has been popularly applied to current networking searching area, but it is difficult to meet the demand of high-speed real-time applications in backbone network and services with mass data. In the general design of hardware-based hash function, there are still some drawbacks such as complex logic circuit memory inefficiency, and incremental updates for dataset needed to be solved. This paper proposed a design of hardware perfect hash function on FPGA based on bit-extraction algorithm, using simple bit-selection and bit logic operation. The achievable load factor can be up to 1, and the amortized memory cost of the hash function is about 2.8-5.6 bits/key for 32-bit keys, and the system clock frequency is about 300MHz(Throughput more than 14Gbps). The proposed method can be applied to real-time applications that require high-speed table lookup, e.g. IP address lookup, packet classification, string matching and intrusion detection systems.

    参考文献
    相似文献
    引证文献
引用本文

王兴,鲍志伟.适用于高速检索的完美Hash函数.计算机系统应用,2016,25(2):250-256

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2015-05-16
  • 最后修改日期:2015-09-16
  • 录用日期:
  • 在线发布日期: 2016-02-23
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号