计算机工程 ›› 2015, Vol. 41 ›› Issue (1): 266-269.doi: 10.3969/j.issn.1000-3428.2015.01.050

• 开发研究与工程应用 • 上一篇    下一篇

一种改进的分段哈希算法

胥攀,刘胜利,兰景宏,肖达   

  1. 数学工程与先进计算国家重点实验室,郑州 450002
  • 收稿日期:2014-02-19 修回日期:2014-03-21 出版日期:2015-01-15 发布日期:2015-01-16
  • 作者简介:胥 攀(1988-),男,硕士研究生,主研方向:信息安全;刘胜利,副教授、博士;兰景宏,硕士研究生;肖 达,讲师、博士研究生。
  • 基金项目:
    国家自然科学基金资助项目(61309007);郑州市科技创新团队基金资助项目(10CXTD150)

An Improved Segment Hash Algorithm

XU Pan,LIU Shengli,LAN Jinghong,XIAO Da   

  1. State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450002,China
  • Received:2014-02-19 Revised:2014-03-21 Online:2015-01-15 Published:2015-01-16

摘要: 为更有效地降低分段哈希算法的碰撞率,提出一种改进的分段哈希算法。在各哈希子表中采用开放地址法,降低各哈希子表中元素的碰撞率,进而降低整个分段哈希算法的碰撞率。对碰撞率、时间效率、空间效率进行分析。使用11 119 905个不同IP数据包的五元组信息,对该算法的碰撞率和时间效率进行测试。实验结果表明,改进的分段哈希算法在不增加内存使用的情况下,可有效降低分段哈希算法的碰撞率,并且随着分段哈希子表数量的增加,该算法的各项性能优势会更加明显。

关键词: 哈希, 开放地址法, 碰撞, 分段哈希子表, 五元组, 分类

Abstract: Collision rate is important to evaluate the hash algorithm.To reduce the collision rate of segment hash algorithm,an improved algorithm is proposed by combining the open address method and the segment hash algorithm,and the performance of the algorithm including collision rate,time efficiency,space efficiency is analyzed.The algorithm is tested by 11 119 905 different IP packets.Experimental results show that the algorithm can reduce the collision rate without increasing memory usage,which can effectively reduce the collision rate of piecewise hashing algorithm.And with the number of sub-table hash increasing,the algorithm is more efficient.

Key words: hash, open address method, collision, segment hash table, five-tuple, classification

中图分类号: