哈希表就是一種以鍵-值(key-indexed)存儲數(shù)據(jù)的結(jié)構(gòu)，我們只要輸入待查找的值即key，即可查找到其對應(yīng)的值。

哈希的思路很簡單，如果所有的鍵都是整數(shù)，那么就可以使用一個簡單的無序數(shù)組來實(shí)現(xiàn)：將鍵作為索引，值即為其對應(yīng)的值，這樣就可以快速訪問任意鍵的值。這是對于簡單的鍵的情況，我們將其擴(kuò)展到可以處理更加復(fù)雜的類型的鍵。

使用哈希查找有兩個步驟：

1.使用哈希函數(shù)將被查找的鍵轉(zhuǎn)換為數(shù)組的索引。在理想的情況下，不同的鍵會被轉(zhuǎn)換為不同的索引值，但是在有些情況下我們需要處理多個鍵被哈希到同一個索引值的情況。所以哈希查找的第二個步驟就是處理沖突

2.處理哈希碰撞沖突。有很多處理哈希碰撞沖突的方法，本文后面會介紹拉鏈法和線性探測法。

哈希表是一個在時間和空間上做出權(quán)衡的經(jīng)典例子。如果沒有內(nèi)存限制，那么可以直接將鍵作為數(shù)組的索引。那么所有的查找時間復(fù)雜度為O(1)；如果沒有時間限制，那么我們可以使用無序數(shù)組并進(jìn)行順序查找，這樣只需要很少的內(nèi)存。哈希表使用了適度的時間和空間來在這兩個極端之間找到了平衡。只需要調(diào)整哈希函數(shù)算法即可在時間和空間上做出取舍。

在Hash表中，記錄在表中的位置和其關(guān)鍵字之間存在著一種確定的關(guān)系。這樣我們就能預(yù)先知道所查關(guān)鍵字在表中的位置，從而直接通過下標(biāo)找到記錄。使ASL趨近與0.

1)哈希(Hash)函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到某個地址集合上，它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可；

2)由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1！=key2，而f(key1)=f(key2)。

3).只能盡量減少沖突而不能完全避免沖突，這是因?yàn)橥ǔｊP(guān)鍵字集合比較大，其元素包括所有可能的關(guān)鍵字，而地址集合的元素僅為哈希表中的地址值

在構(gòu)造這種特殊的“查找表”時，除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法。

一.Hash構(gòu)造函數(shù)的方法

1.直接定址法：

直接定址法是以數(shù)據(jù)元素關(guān)鍵字k本身或它的線性函數(shù)作為它的哈希地址，即：H（k）=k或H（k）=a×k+b；(其中a,b為常數(shù))

2.數(shù)字分析法：

假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。

數(shù)字分析法是取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字位作為哈希地址的方法。即當(dāng)關(guān)鍵字的位數(shù)很多時，可以通過對關(guān)鍵字的各位進(jìn)行分析，丟掉分布不均勻的位，作為哈希值。它只適合于所有關(guān)鍵字值已知的情況。通過分析分布情況把關(guān)鍵字取值區(qū)間轉(zhuǎn)化為一個較小的關(guān)鍵字取值區(qū)間。

3.折疊法：

將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。兩種疊加處理的方法：移位疊加:將分割后的幾部分低位對齊相加；邊界疊加:從一端沿分割界來回折疊，然后對齊相加。

所謂折疊法是將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位），這方法稱為折疊法。這種方法適用于關(guān)鍵字位數(shù)較多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻的情況。

折疊法中數(shù)位折疊又分為移位疊加和邊界疊加兩種方法，移位疊加是將分割后是每一部分的最低位對齊，然后相加；邊界疊加是從一端向另一端沿分割界來回折疊，然后對齊相加。

審核編輯：符乾江