摘要： 为更有效地降低分段哈希算法的碰撞率,提出一种改进的分段哈希算法。在各哈希子表中采用开放地址法,降低各哈希子表中元素的碰撞率,进而降低整个分段哈希算法的碰撞率。对碰撞率、时间效率、空间效率进行分析。使用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

中图分类号: 

• TP309.7