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

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

使用哈希查找有兩個(gè)步驟：

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

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

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

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

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

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

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

在構(gòu)造這種特殊的“查找表”時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(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)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。

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

3.折疊法：

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

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

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

審核編輯：符乾江