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

李立亞，吳 麗，遲榮華

(無錫科技職業學院人工智能學院，江蘇 無錫 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%左右的算力消耗。

本算法的提出，為快速字符串哈希算法，提供了一種新的實用方法。