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

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

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

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

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

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

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

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

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

3).只能盡量減少沖突而不能完全避免沖突，這是因為通常關鍵字集合比較大，其元素包括所有可能的關鍵字，而地址集合的元素僅為哈希表中的地址值

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

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

1.直接定址法：

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

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

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

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

3.折疊法：

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

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

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

審核編輯：符乾江