一、概述

根據(jù)設(shè)定的哈希函數(shù)H（key）和處理沖突的方法將一組關(guān)鍵字影像到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便成為哈希表，這一映像過程稱為哈希造表或散列，所得存儲位置稱哈希地址或散列地址。

上面所提到的哈希函數(shù)是指：有一個對應(yīng)關(guān)系 f ，使得每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)，這樣在查找時，我們不需要像傳統(tǒng)的查找算法那樣進(jìn)行比較，而是根據(jù)這個對應(yīng)關(guān)系 f 找到給定值K的像f（K）。

哈希函數(shù)也可叫哈希算法，它可以用于檢驗信息是否相同（文件校驗），或者檢驗信息的擁有者是否真實（數(shù)字簽名）。

下面分別就哈希函數(shù)和處理沖突的方法進(jìn)行討論;

二、哈希函數(shù)的構(gòu)造方法

構(gòu)造哈希函數(shù)的方法有很多。在介紹各種方法前，首先需要明確什么是“好” 的哈希算法。若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)哈希函數(shù)映像到地址集合中任何一個地址的概率是相等的，則稱此類哈希函數(shù)是均勻的（Uniform）哈希函數(shù)。換句話說，就是使關(guān)鍵字經(jīng)過哈希函數(shù)得到一個“隨機的地址”，以便使一組關(guān)鍵字的哈希地址均勻分布在整個地址區(qū)間中，從而減少沖突。
常用的構(gòu)造哈希函數(shù)的方法有：

1. 直接定址法
   取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。即:
   H（key）=key 或 H（key） = a * key + b
   其中a 和 b為常數(shù)（這種哈希函數(shù)叫做自身函數(shù)）。

   例如：有一個1歲到100歲的人口數(shù)字統(tǒng)計表，其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身。如下表所示：

   地址	01	02	03	...	25	26	27	...	100
   年齡	1	2	3	...	25	26	27	...	100
   人數(shù)	3000	2000	5000	...	1050	...	...	...	...
   ...

   這樣若要詢問25歲的人有多少，則只要查表的第25項即可。
   由于直接定址所得的地址集合和關(guān)鍵字集合的大小相同。因此，對于不同的關(guān)鍵字不會發(fā)生沖突，但是實際中能使用這種哈希函數(shù)的情況很少。

2. 數(shù)字分析法
   假設(shè)關(guān)鍵字是以r為基數(shù)的數(shù)（如：以10為基的十進(jìn)制數(shù)），并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。

   例如有80個記錄，其關(guān)鍵字為8位十進(jìn)制數(shù)。假設(shè)哈希表的表長為100₁₀，則可取兩位十進(jìn)制數(shù)組成哈希地址。那么取哪兩位呢？原則是使用得到的哈希地址盡量避免產(chǎn)生沖突，則需從分析這80個關(guān)鍵字著手。假設(shè)這80個關(guān)鍵字中的一部分如下所列：
   

   
   對關(guān)鍵字的全體分析中我們發(fā)現(xiàn)：第①②位都是“8 1”，第③位只可能取1、2/3或4，第⑧位只可能取2、5或7，因此這4位都不可取。由于中間的4位都可看成是近乎隨機的，因此可取其中任意兩位，或取其中兩位與另兩位的疊加求和后舍去進(jìn)位作為哈希地址。

3. 平方取中法
   取關(guān)鍵字平方后的中間幾位為哈希地址。這是一種較常用的構(gòu)造哈希函數(shù)的方法。通常在選定哈希函數(shù)時不一定能知道關(guān)鍵字的全部情況，取其中哪幾位也不一定合適，而一個數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都有關(guān)，由此使隨機分布的關(guān)鍵字得到的哈希地址也是隨機的。取的位數(shù)由表長決定。

   例如：為BASIC原程序中的標(biāo)識符建立一個哈希表。假設(shè)BASIC語言中允許的標(biāo)識符為一個字母，或一個字母和一個數(shù)字。在計算機內(nèi)可用兩位八進(jìn)制數(shù)表示字母和數(shù)字，如圖（a）所示。取標(biāo)識符在計算機中的八進(jìn)制數(shù)為它的關(guān)鍵字。假設(shè)表長為512=2⁹，則可取關(guān)鍵字平方后的中間 9 位二進(jìn)制數(shù)作為哈希地址。例如圖（b）列出了一些標(biāo)識符及他們的哈希地址。
   

4. 折疊法
   將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址，這種方法稱為折疊法（folding）。關(guān)鍵字位數(shù)很多，而且關(guān)鍵字中每一位數(shù)字分布大致均勻時，可以采用折疊法得到哈希地址。

   例如：每一中西文圖書都有一個國際標(biāo)準(zhǔn)圖書編號（ISBN），它是一個10位的十進(jìn)制數(shù)字，若要以它作關(guān)鍵字建立一個哈希表，當(dāng)館藏書種類不到 10000 時，可采用折疊法構(gòu)造一個四位數(shù)的哈希函數(shù)。在折疊法中數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對齊，然后相加；間界疊加是從一端向另一端沿分割界來回折疊，然后對齊相加。如國際標(biāo)準(zhǔn)圖書編號0-442-20586-4的哈希地址分別如圖 （a）和（b）所示。
   

5. 除留余數(shù)法
   取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得的余數(shù)為哈希地址。即
   H（key） = key MOD p ， p ≤ m
   這是一種最簡單，也最常用的構(gòu)造哈希函數(shù)的方法。它不僅可以對關(guān)鍵字直接取模（MOD），也可以在折疊、平方取中等運算之后取模。
   值得注意的是，在使用除留余數(shù)法時，對p的選擇很重要。若p選的不好，容易產(chǎn)生同義詞。

   例如，已知散列元素為（18、75、60、43、54、90、46），表長m= 10，p = 7，則有
   h(18)=18 % 7=4 ， h(75)=75 % 7=5 ， h(60)=60 % 7=4 ，
   h(43)=43 % 7=1 ， h(54)=54 % 7=5 ， h(90)=90 % 7=6 ，
   h(46)=46 % 7=4
   由于沖突較多，為減少沖突，可取較大的m值和p值，如m=p=13，結(jié)果如下：
   h(18)=18 % 13=5 ， h(75)=75 % 13=10， h(60)=60 % 13=8 ，
   h(43)=43 % 13=4 ， h(54)=54 % 13=2 ， h(90)=90 % 13=12 ，
   h(46)=46 % 13=7

   0	1	2	3	4	5	6	7	8	9	10	11	12
   		54		43	18		46	60		75		90

理論研究表明，除留余數(shù)法的模p取不大于表長且最接近表長m的素數(shù)效果最好，且p最好取1.1ⁿ ~ 1.7ⁿ之間的一個素數(shù)（n為存在的數(shù)據(jù)元素個數(shù)）。

6. 隨機數(shù)法
   選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的哈希地址，即H（key）= random（key），其中random為隨機函數(shù)。通常，當(dāng)關(guān)鍵字長度不等時采用此法構(gòu)造哈希函數(shù)較恰當(dāng)。

以上便是常用的6種構(gòu)造哈希函數(shù)的方法，實際工作中需視不同的情況采用采用不同的哈希函數(shù)，通常考慮的因素有：

• 計算哈希函數(shù)所需時間（包括硬件指令的因素）。
• 關(guān)鍵字的長度。
• 哈希表的大小。
• 關(guān)鍵字的分布情況。
• 記錄的查找頻率。

三、處理沖突的方法

前面有提到過均勻的哈希函數(shù)可以減少沖突，但不能避免，因此，如何處理沖突是哈希造表不可缺少的另一方面。

通常用的處理沖突的方法有下列幾種：

1. 開放定址法
   H_i = (H(key) + d_i) MOD m i = 1,2,...,k ( k ≤ m-1)
   其中：H(key)為哈希函數(shù)；m 為哈希表表長；d_i為增量序列，可有下列3種取法：

   (1). d_i=1,2,3,...,m-1,稱線性探測再散列。
   (2). d_i=1², -1², 2², -2²,..., ±k² ( k ≤ m/2)稱二次探測再散列。
   (3). d_i=偽隨機數(shù)序列,稱偽隨機探測再散列。

   例如，在長度為11的哈希表中已填有關(guān)鍵字分別為17,60,29的記錄（哈希函數(shù) H(key) = key MOD 11），現(xiàn)有第四個記錄，其關(guān)鍵字為38，由哈希函數(shù)得到哈希地址為5，產(chǎn)生沖突。若用線性探測再散列方法處理，得到下一個地址為6，仍沖突，繼續(xù)算7，仍沖突，知道最后算出8，填入哈希表。若用二次三冊再散列，則應(yīng)填入需要為4的位置。
   

2. 再哈希法
   H_i = RH_i(key) i = 1,2,...,k
   RH_i均是不同的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。這個方法不易產(chǎn)生“聚集”，但增加了計算的時間。

3. 鏈地址法
   將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址在區(qū)間[0,m -1 ]上，則設(shè)立一個指針型向量
   Chain ChainHash[m]
   其每個分量的初始狀態(tài)都是空指針。凡哈希地址為i的記錄都插入到頭指針為ChainHash[i]的鏈表中。在鏈表中的插入位置可以在表頭或表尾；也可以在中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序。

4. 建立一個公共溢出區(qū)
   這也是處理沖突的一種方法、假設(shè)哈希函數(shù)的值域為[ 0, m - 1 ]，則設(shè)向量HashTable[ 0..m - 1 ]為基本表，每個分量存放一個記錄，另設(shè)向量OverTable[0..v]為溢出表。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。

四、哈希表的查找及其分析

在哈希表上進(jìn)行查找的過程和哈希建表的過程基本一致。給定K值，根據(jù)建表時設(shè)定的哈希函數(shù)求得哈希地址，若表中此位置上沒有記錄，則查找不成功；否則比較關(guān)鍵字，若和給定值相等，則查找成功；否則根據(jù)造表時設(shè)定的處理沖突的方案找“下一地址”，直到找到為止。

五、總結(jié)

• 哈希函數(shù)構(gòu)造方法：直接定址法、數(shù)字分析法、折疊法、平方取中法、除留余數(shù)法、隨機數(shù)法。
• 處理沖突方法：開放定址法、再哈希法、鏈地址法。
• 開放定址法中d_i的3種取法：線性探測再散列，二次探測再散列，偽隨機探測再散列。