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

李立亚，吴 丽，迟荣华

(无锡科技职业学院人工智能学院，江苏 无锡 214028)

0 引言

在计算机数据处理技术中，哈希算法将任意长度数据块映射为较短的固定长度的二进制值，即哈希值。只要是更改数据块的任何字节，都会产生不同的哈希值，反向找到同一哈希值的不同输入，在计算上代价巨大。因此，哈希算法广泛应用在数据的完整性检验、数据快速查找、构造安全的数据结构等。

哈希算法的实现方式有加减法、位运算、乘法除法、查表、混合实现等，不同实现方式在运行速度和哈希效果上有所差异。比较常见的算法有MD5、SHA-1、BKDRHash、APHash 等。不同的哈希算法有不同的特性，适用不同的场合。文献[1]对哈希函数的迭代结构和压缩函数进行了研究，可以构造安全性较高的哈希算法。文献[2]在哈希计算过程中加入了随机性，提高了哈希算法的安全性。文献[3]利用二元方程构造了一种哈希算法，具备较好的效果和性能。文献[4]利用明文信息进行迭代次数控制，增加了随机性。文献[5]针对物联网设备设计了一种轻量级哈希函数，在安全和性能上做了折中，牺牲部分性能，提高安全性。文献[6]使用字典法构造了一种完美哈希函数，效果较好，但算法复杂和对工作空间要求高。文献[7]从理论上证明了采用异或运算和位移运算能够提供较好的哈希值随机特性，并用这两种基本操作，提出了异或循环哈希算法，在性能和效率上有优势。文献[8]设计了一种基于异或运算、并加入伪随机移位的哈希函数，应用在以TCP 网络连接管理的哈希表中，取得了较好的效果。

本文通过移位、取反、和加法加速数据混淆过程，设计了一种快速字符串哈希算法，算法结构简明、编程实现简单。与文献[9]提出的BKDRHash 算法相比，本算法在效果上相当的情况下，速度上具有10%左右优势。

1 算法设计

采用的混淆计算手段越多、混淆过程的计算参数调整越灵活、越容易获得较好的哈希效果，但计算过多又会影响算法性能。本算法在位混淆设计上，使用短周期计算指令的操作完成，减少计算数量。

1.1 计算流程

本文哈希算法以位运算、加法为基础构造。如图1 所示。中间结果左移、取反，然后加字符（改进算法再加中间一次结果），循环往复，直至处理完毕所有数据，计算出Hash结果。通过实验测试搜索左移位数因子，左移7位效果最佳。

算法设计上分为基本型和改进型两种：基本型算法速度更快，混淆效果稍弱，速度更快。改进型算法再加一次中间哈希码，效果更好，速度稍弱。

1.2 位混淆设计思路

本算法计算过程使用的数据位字长基于标准字长，与CPU 字长、或程序设计语言支持的字长一致，比如32位、64位。设计思路：①移位和取反只使用一次，移位和取反可以迅速地改变数据位，但对数据位的混淆功能有限；②最多使用两次加法操作，进行混淆。

计算次序设计：移位操作会损失数据位，取反操作仅对位取反，加法操作进行位混淆扩散功能，因此按先移位、再取反，最后做加法的次序进行计算。

本文采取对中间结果进行移位取反，再加字符串中字符的方案设计。移位操作将低位补0，取反时，这些位变为1，从而增加1 的数量。如此，在做加法时可以获得较好的混淆扩散效果。

计算公式为：中间哈希码=中间哈希码左移7位后取反+字符+中间哈希码。

基本型混淆扩散过程如图1所示。

图1 混淆扩散过程图

1.3 算法复杂度分析

本算法对空间需求为几个整型变量的空间。

计算复杂度，每轮迭代都有中间结果移位、取反、加操作运算，计算复杂度为O（N+N+N）。与BKDR 算法相比，BKDR 算法计算复杂度为O（N+N），但BKDR中使用了乘法，乘法指令周期数远大于位运算和加法。因此本算法在指令周期数上具有优势。

2 仿真实验

BKDR快速哈希算法，在速度、哈希效果上都非常优秀，该算法来自于Brian Kernighan 和Dennis Ritchie 合著的《The C Programming Language》专著。本文以该算法为参照对象进行对比测试。

两个算法均用VC#进行程序编码。BKDR快速哈希算法选用种子值131，算法代码如下：

2.1 实验方法及结果

⑴性能测试

分别用大小两种数据块来测试性能：①测试20个字长的数据块1000 万次；②测试1000 万个字长的数据块100次。

分别在WIN7 系统和WIN10 系统两台PC 上进行了测试。WIN7 系统配置为Intel i5-2400 CPU，主频为3.1GHz，最大睿频3.4Ghz。WIN10 系统配置为Intel i5-8400 CPU,主频为2.80GHz，最大睿频4.0Ghz。

在两个系统平台上测试过程中，发现WIN7 系统平台测试结果比较稳定，变化很小。而WIN10系统平台测试结果稳定性较差，变化较大。推测是WIN7 平台CPU 睿频范围小、WIN10 平台CPU 睿频范围大，测试过程中CPU睿频程度不同导致测试结果稳定性不同。

经过多次测试，选出偏离度较小的样本数据做为测试结果，如表1和表2所示。

表1 20个字长的数据块1000万次测试结果（单位：毫秒）

表2 1000万个字长的数据块100次测试结果（单位：毫秒）

对20 个字长的数据块1000 万次测试结果，两个系统平台的结果基本一致，本文设计的哈希算法比BKDR 哈希算法的性能高8%左右对1000 万个字长的数据块测试中，WIN10平台上的速度比WIN7平台慢，而WIN7 平台上，本文算法的性能优势达到了10.5%左右。

⑵哈希效果测试

哈希效果测试主要测试哈希冲突情况，冲突次数少的为优。设计了两类测试：第一类是直接测试，测试哈希码冲突情况；第二类是映射测试，将哈希码映射到一个数组上，看映射冲突情况。

测试字符串的字符表由71个字符组成，71个字符如下：

第一步，定长字符串测试。使用上述71 个字符，生成了26003571 个字符串，字符串长度为1、2、3、4、5的字符串个数分别为71、71×71=5041、71 ＾3=357911、71＾4=25411681、228867 个。用本论文哈希算法和BKDR 哈希算法计算这些字符串的哈希码，均没有冲突。

第二步，随机字符串及映射冲突测试。使用上述71 个字符随机生成长度为1-50 的字符串240000 个，分别用本文哈希算法和BKDR 哈希算法计算哈希码，并映射到尺寸为300000的数组上，检验哈希码冲突和映射冲突情况。12 次测试结果如表3 所示，本算法哈希码冲突高一些，映射冲突相当略高。

表3 随机字符串及映射冲突测试对比（单位：次）

2.2 算法的改进型

基本型的随机字符串的冲突测试中，哈希冲突效果稍差。原因是每轮计算过程中的左移操作，损失了中间结果的高7 位，并且字符高位都是0，无法充分对数据位进行混淆和扩散。

改进型再加一次中间哈希码，增加了一个加法操作，可以在对性能影响不大的情况下，提升数据位的混淆和扩散效果。随机生成240000 个字符串映射到300000 个数组元素的部分测试结果如表4 所示，改进型算法哈希效果与BKDR算法相当。

表4 改进算法随机字符串冲突测试对比（单位：次）

本文还测试了随机生成3000、8000、16000、24000个字符串映射到5000、10000、20000、30000 个数组元素，两个算法效果也是相当。

改进后的算法，因为多了一次加法操作，性能上会略慢。分别在上述WIN7 和WIN10 平台上测试，WIN7 平台性能比BKDR 算法快8%左右。在WIN10平台两个算法性能持，结合上面的性能测试，推测是在新的平台中，乘法指令得到了优化，使乘法运算性能得到了提高。

3 结束语

本文针对字符串哈希计算需求，提出了一种快速哈希算法，本算法结构简单、易实现。在性能上优于BKDR 哈希算法，在哈希效果上与BKDR 算法相当。尤其是针对长度为5 及以下的字符串的哈希计算，使用本文基本型算法计算的哈希码抗冲突效果与BKDR算法相当，在性能上有显著优势。

在对乘除法没有显著优化的平台上，比如嵌入式平台和系统、单片机开发中，本算法与BKDR 相比，具有明显的性能优势，在对计算功耗和性能比较敏感的应用场合，使用本算法能节省8%-11%左右的算力消耗。

本算法的提出，为快速字符串哈希算法，提供了一种新的实用方法。