一种基于移位取反和加法的字符串哈希算法

A string hash algorithm based on shift inversion and addition

哈希算法大量应用于信息传输、存储、校验等领域,其中面向字符串的哈希算法结构简单、易编码实现、速度快,这类算法的设计往往使用位操作、算术运算、查表等运算的组合来实现,不同的组合在性能和效果上也不相同。理论上,运算步骤越简单、性能越好,但哈希效果难以保证;步骤越多、性能越差,但哈希效果容易有保障。本文使用移位、取反和加法三种基本运算,设计了一种快速字符串哈希算法,使用较少的步骤获得了较好的性能和效果。通过与BKDR哈希算法对比测试,本算法在性能上有8%的优势,两者哈希效果相当。

Hash algorithm is widely used in information transmission,storage,verification,etc.The hash algorithm for string is simple in structure,easy to encode,and fast.The design of such algorithms is often implemented by a combination of operations such as bit operations,arithmetic operations,and table lookups.Different combinations are different in performance and effect.In theory,the simpler the operation steps,the better the performance,but the hash effect is difficult to guarantee;the more steps,the worse the performance,but the hash effect is easily guaranteed.In this paper,basic operations of shift,inversion and addition are used to design a fast string hashing algorithm,which achieves better performance and effect with fewer steps.By comparing with the BKDR hash algorithm,the algorithm has an 8%advantage in performance,and the hash effect is equivalent.