哈希查找算法的構造和沖突解決方法

謝宇翔

摘要：本文對經典算法中的哈希算法（又稱散列），介紹了其常用的七種構造方法和四種沖突解決方法及其原理，并通過舉例，詳細說明了各種方法的具體實現和適用場景。

關鍵詞：哈希，關鍵字，沖突，時間復雜度，空間復雜度，大數據

正文：

在如今的大數據時代，需要各種高效，海量的數據處理技術，哈希（HASH）算法以自身的優點，被廣泛應用在查找，存儲，加密，校驗，區塊鏈等眾多場景，大大提升了數據存儲分析的效率，是不可或缺的數據處理技術。

以下就對哈希的構造和沖突解決原理進行詳細的理論和舉例說明。

一、哈希的構造方法[1][2]

1.直接定址法：

哈希地址：f（key）=a*key+b （a，b為常數）

簡單均勻，不產生沖突，需事先知道key的分布情況，適合查找表較小且連續的情況。

舉例：比方說某校從1905年起招生，則統計每屆招生人數時，可以用年份-1905作為地址：

此時 f（key）=key-1905

2.數字分析法

假設關鍵字以固定位組成，且可能出現的關鍵字是事先知道的，則可取關鍵字的若干數位組成哈希地址。

3.平方取中法

一個數平方的中間幾位與這個數的每一位都有關，因而平方取中法產生沖突的機會相對較小。所取的位數由表長決定。適合于不知道關鍵字分布，而位數又不是很大的情況。

4.折疊法

把一個關鍵字分成位數相同的幾段（最后一段位數可以不同），然后將各段的疊加和（舍去進位）作為哈希地址。

事先不需要知道關鍵字的分布，而且關鍵字中每一位上數字分布大致均勻，適合關鍵字位數較多的情況。

5.除留余數法

取關鍵字被某個不大于哈希表表長m的數p除后所得的余數為哈希地址。即 f（key） = key mod p，p<=m。不僅可以對關鍵字直接取模，也可在折疊法、平方取中法等運算之后取模。對p的選擇很重要，一般取質數或m。這是比較重要和常用的方法，被廣泛使用。

6.偽隨機數法

f（key） = random（key）

這里 random 是隨機函數，當 key 的長度不等時，采用這種方法比較合適。

7.基數轉換法

將一個數看作其它進制，然后按照新進制取其中若干位作為哈希值。一般取大于原基數的數作為轉換的基數，并且兩個基數是互質的。

比方說key是十進制的，那可以新的進制為十三進制，取其第3，6，9位，即f（key）=key13的第3，6，9位。

二、哈希的沖突解決

下面以創建哈希表為例，說明解決沖突的方法。

常用的解決沖突方法有以下四種：開放尋址法、再哈希法、鏈地址法（拉鏈法）和建立一個公共溢出區。[1][2]

1.開放尋址法：當關鍵字key的哈希地址q=f（key）發生沖突，以q為基數再生成一個哈希地址q1，若q1仍然沖突，再以q為基數生成另一個哈希地址q2，…，直到找到不沖突的哈希地址。這種方法有一個通用的再散列函數形式：

fi=（f（key）+di）%m i=1，2，…，n

其中f（key）為哈希函數，m 為表長，di稱為增量序列。di的取值方式，主要有以下三種：

a） 線性探測再散列 di=1，2，3，…，m-1

b） 二次探測再散列 di=k，-k，k-1，-（k-1），…，1，-1 ? ?（ k<=m/2）

c） 偽隨機探測再散列 di=偽隨機數序列。

2.再哈希法：

這種方法是同時構造多個不同的哈希函數：

fi（key） i=1，2，…，k

當哈希地址f1（key）發生沖突時，再計算f2（key）……，直到沖突不再產生。

比方說fi（key） 定義為對key取5+6i的模，也就是11，17，23，29….

3.鏈地址法（拉鏈法）

這種方法的基本思想是將所有哈希地址為f（key）=i的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經常進行插入和刪除的情況。

舉例，用以上f（key）=key%13為例，首先建立一個擁有索引為13的數組，數組中每個元素為一個鏈表的頭指針，然后在需要存放數據的時候，根據f（key）找到數組中對應元素對應的鏈表（頭指針），然后在此鏈表最后插入數據。

4.建立公共溢出區：

這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表。

三、綜合實例：

問題描述[3]

A和 B各有排列好的n塊積木，每塊積木上寫有一個小寫英文字母。

允許A從自己的積木串s中丟掉任意塊（也允許不丟）;允許B從自己的積木串t中丟掉左邊連續的一段積木和右邊連續的一段積木（也允許只丟一邊或兩邊都不丟）。不允許丟棄自己所有積木。然后A和B分別將自己剩下的積木按原來的順序重新排成一排。

計算一下，有多少種不同的情況下他們最后剩下的兩排積木是相同的（剩下的這兩排積木塊數相同且每一個位置上的字母都對應相同）？

解答：因為對s的要求比較寬松，所以首先枚舉t的子串，通過逐一匹配s的位，以此來獲取t中可能匹配的所有子串，時間復雜度為O（n^2）。然后在累計答案處進行字符串的相等判斷和去除重復，這里的比較用哈希表來大大提高效率：首先計算t每個可能字串的哈希值，把每個字符轉換成ascii與‘a’的差值，即a=1，b=2，…，并把每個位以base（很大的質數）作為進制獲得表示t從i到j的哈希key數組HashKey[i][j]，然后比方說采用除留余數法，以另一個大質數作為模數獲得哈希地址來進行比較。若是簡單的進行枚舉比較，那時間復雜度將大幅度增加;和其它方法相比較，使用hash應該是時間復雜度最優的方法。

參考文獻：

[1]哈希算法原理詳解 https：//www.jianshu.com/p/f9239c9377c5

[2]哈希算法以及沖突解決 https：//www.itdaan.com/blog/2016/12/06/c885400f4092.html

[3]洛谷 https：//www.luogu.com.cn/problem/P7469