哈希查找算法的構(gòu)造和沖突解決方法

謝宇翔

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

關(guān)鍵詞：哈希，關(guān)鍵字，沖突，時間復(fù)雜度，空間復(fù)雜度，大數(shù)據(jù)

正文：

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

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

一、哈希的構(gòu)造方法[1][2]

1.直接定址法：

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

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

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

此時 f（key）=key-1905

2.數(shù)字分析法

假設(shè)關(guān)鍵字以固定位組成，且可能出現(xiàn)的關(guān)鍵字是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。

3.平方取中法

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

4.折疊法

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

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

5.除留余數(shù)法

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

6.偽隨機數(shù)法

f（key） = random（key）

這里 random 是隨機函數(shù)，當(dāng) key 的長度不等時，采用這種方法比較合適。

7.基數(shù)轉(zhuǎn)換法

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

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

二、哈希的沖突解決

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

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

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

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

其中f（key）為哈希函數(shù)，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=偽隨機數(shù)序列。

2.再哈希法：

這種方法是同時構(gòu)造多個不同的哈希函數(shù)：

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

當(dāng)哈希地址f1（key）發(fā)生沖突時，再計算f2（key）……，直到?jīng)_突不再產(chǎn)生。

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

3.鏈地址法（拉鏈法）

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

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

4.建立公共溢出區(qū)：

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

三、綜合實例：

問題描述[3]

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

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

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

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

參考文獻：

[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