基本概念

散列表(Hash table，也叫哈希表)，是根據(jù)關(guān)鍵字(key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。

說(shuō)的具體點(diǎn)就是它通過(guò)吧key值映射到表中的一個(gè)位置來(lái)訪問(wèn)記錄，從而加快查找的速度。

實(shí)現(xiàn)key值映射的函數(shù)就叫做散列函數(shù)

存放記錄的數(shù)組就就叫做散列表

實(shí)現(xiàn)散列表的過(guò)程通常就稱為散列(hashing)，也就是常說(shuō)的hash

散列

這里的散列的概念不僅限于數(shù)據(jù)結(jié)構(gòu)了，在計(jì)算機(jī)科學(xué)領(lǐng)域中，散列-哈希是一種對(duì)信息的處理方法，通過(guò)某種特定的函數(shù)/算法(散列函數(shù)/hash()方法)將要檢索的項(xiàng)與用來(lái)檢索的索引--( 散列值)關(guān)聯(lián)起來(lái)，生成一種便于搜索的數(shù)據(jù)結(jié)構(gòu)--散列表。如今，由于散列算法所計(jì)算的散列值 具有不可逆(無(wú)法逆向演算會(huì)原來(lái)的數(shù)值)的性質(zhì)，因此散列算法廣泛的運(yùn)用于加密技術(shù)。

散列的運(yùn)用：

1、加密散列，在信息安全領(lǐng)域使用

2、散列表，一種使用散列函數(shù)將鍵名和鍵值關(guān)聯(lián)起來(lái)的數(shù)據(jù)結(jié)構(gòu)

3、關(guān)聯(lián)數(shù)組，一種常常使用散列表來(lái)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)

4、幾何散列，尋找相同或相似的幾何形狀的一種有效方法

散列函數(shù)

通過(guò)上面可以知道，散列技術(shù)的實(shí)現(xiàn)是基于散列函數(shù)的。這里對(duì)散列函數(shù)進(jìn)行一個(gè)較深入的理解。前面就知道了散列函數(shù)--哈希函數(shù)就是完成key值與位置的映射。一般說(shuō)來(lái)key以字符 串的形式居多，位置也就是一個(gè)數(shù)值?？梢钥闯錾⒘泻瘮?shù)就像是實(shí)現(xiàn)信息的壓縮，把消息字符 串壓縮成數(shù)值摘要，是數(shù)據(jù)量變小，格式得以固定下來(lái)。
散列函數(shù)的工作原理圖：

不過(guò)需要注意的是key值和經(jīng)過(guò)散列函數(shù)處理之后的散列值并不是唯一對(duì)應(yīng)的，這就造成了不同的key值具有相同的索引位置，這種現(xiàn)象叫做散列碰撞、也稱其為哈希沖突。對(duì)于hash沖突的解決辦法，將在后面予以總結(jié)。至于散列函數(shù)的具體實(shí)現(xiàn)，有很多加密技術(shù)都有十分nice的實(shí)現(xiàn)，這里我們看看Java中HashMap的hash()方法實(shí)現(xiàn)就可以了。HashMap采用的是內(nèi)部哈希技術(shù)實(shí)現(xiàn)的，其中hash()方法就是散列函數(shù)，完成key值到數(shù)組索引位置的映射。                   

 /** 
  * Retrieve object hash code and applies a supplemental hash function to the 
  * result hash, which defends against poor quality hash functions. This is 
  * critical because HashMap uses power-of-two length hash tables, that 
  * otherwise encounter collisions for hashCodes that do not differ 
  * in lower bits. Note: Null keys always map to hash 0, thus index 0. 
  */ 
 final int hash(Object k) { 
  int h = 0; 
  if (useAltHashing) { 
   if (k instanceof String) { 
    return sun.misc.Hashing.stringHash32((String) k); 
   } 
   h = hashSeed; 
  } 
  h ^= k.hashCode(); 
  // This function ensures that hashCodes that differ only by 
  // constant multiples at each bit position have a bounded 
  // number of collisions (approximately 8 at default load factor). 
  h ^= (h >>> 20) ^ (h >>> 12); 
  return h ^ (h >>> 7) ^ (h >>> 4); 
 } 

上述代碼就是HashMap中散列函數(shù)的具體實(shí)現(xiàn)。JDK1.7這里筆者對(duì)常用的散列算法做一個(gè)展示：

散列表

在理解了上述散列\(zhòng)散列函數(shù)的概念之后我們正式的進(jìn)入到散列表的學(xué)習(xí).一個(gè)通俗的例子是，為了查找電話簿中某人的號(hào)碼，可以創(chuàng)建一個(gè)按照人名首字母順序排列的表（即建立人名 x 到首字母 F(x) 的一個(gè)函數(shù)關(guān)系），在首字母為 W 的表中查找“王”姓的電話號(hào)碼，顯然比直接查找就要快得多。這里使用人名作為關(guān)鍵字，“取首字母”是這個(gè)例子中散列函數(shù)的函數(shù)法則 F()，存放首字母的表對(duì)應(yīng)散列表。關(guān)鍵字和函數(shù)法則理論上可以任意確定。

散列函數(shù)的構(gòu)造

對(duì)于散列表這種數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)，其散列函數(shù)的構(gòu)造是十分關(guān)鍵的，散列函數(shù)實(shí)現(xiàn)了key的映射,并且訪問(wèn)記錄可以更快的被定位。一般來(lái)說(shuō)散列函數(shù)的構(gòu)造基于兩個(gè)標(biāo)準(zhǔn):簡(jiǎn)單、均勻簡(jiǎn)單指散列算法簡(jiǎn)單快捷，散列值生成簡(jiǎn)單。均勻指對(duì)于key值集合中的任一關(guān)鍵字，散列函數(shù)能夠以均與的概率映射到數(shù)組的任一一個(gè)索引位置上，這樣能夠減少散列碰撞。
散列函數(shù)構(gòu)造方法：

1、直接地址法：

直接取key值或者key值的某個(gè)線性函數(shù)值作為散列地址。即hash(k)=k或者h(yuǎn)ash(k)=a*k+b。

Tips： 簡(jiǎn)單的思考一下這種方式就可以知道，這種方式基本不會(huì)存在哈希沖突，不過(guò)事先我們應(yīng)該知道key集合的大小，而且使用線性函數(shù)值作為散列地址的話，很大程度上造成了空間的浪費(fèi)。hash(k)=k這種方式更加的雞肋沒(méi)必要，以這種方式散列還不如直接數(shù)組索引。

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

所謂的數(shù)字分析法就是假設(shè)關(guān)鍵字key是以r為基的數(shù)，并且hash表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成hash地址。

Tips：這種方式極度不靈活，限制太多。

3、平方取中法：

先通過(guò)求關(guān)鍵字的平方值擴(kuò)大相近數(shù)的差別，然后根據(jù)表長(zhǎng)度取中間的幾位數(shù)作為散列函數(shù)值。

Tips：這種方式中間的幾位數(shù)都和關(guān)鍵字的沒(méi)一位都有關(guān)，產(chǎn)生的散列地址較為的均勻。

4、折疊法:

將關(guān)鍵字分割成相同的幾位數(shù)(最后一位可不同)，然后去這幾部分的疊加和。折疊法一般是和除留余法一起使用的。

5、除留余法：

取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng) m 的數(shù) p 除后所得的余數(shù)為散列地址。即 hash(k)= k mod p, p < m。不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊法、平方取中法等運(yùn)算之后取模。對(duì) p 的選擇很重要，一般取素?cái)?shù)或 m ，若 p 選擇不好，容易產(chǎn)生碰撞。

6、隨機(jī)法：

h(key)=random(key)    其中random為偽隨機(jī)函數(shù)，但要保證函數(shù)值是在0到m-1之間?？偨Y(jié):在上述的方法中，3、4、5三種方法的結(jié)合使用方式較好，在JDK以前的版本就是使用的方法5。

哈希沖突

通過(guò)上面的學(xué)習(xí)中，我們知道散列函數(shù)得到的key -  索引位置 并不是唯一對(duì)應(yīng)的，可能造成不同的key值對(duì)應(yīng)相同的索引位置。這是我們應(yīng)該解決的問(wèn)題。實(shí)際的解決方法一般如下：

1、分離連接法：

首先看看分離連接法，說(shuō)白了這種方式就是鏈表數(shù)組的方式，將散列到同一個(gè)值得所有元素保存在一個(gè)表中，產(chǎn)生相同的一個(gè)值在散列表中使用鏈表的形式存儲(chǔ)。哈希沖突的位置就是鏈表的開(kāi)始位置。在JKD中HashMap就是這種方式解決哈希沖突的!

HashMap中沖突處理代碼如下   

for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
   Object k; 
   if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
    V oldValue = e.value; 
    e.value = value; 
    e.recordAccess(this); 
    return oldValue; 
   } 
  } 

2、開(kāi)放地址法

分離連接法的缺點(diǎn)在于使用了鏈表，由于給新的單元分配地址耗費(fèi)時(shí)間，造成算法速度較慢，解決的方法就是開(kāi)放地址法，在開(kāi)放地址法中較為常用的有兩種：線性探測(cè)法、平方探測(cè)法。 
開(kāi)放地址法:    

hash_i=(hash(key) + d(i)) mod m, i=1,2...k\,(k < m-1)，其中hash(key)為散列函數(shù)，m為散列表長(zhǎng)，d(i)為增量序列，i為已發(fā)生碰撞的次數(shù)。增量序列可有下列取法：

d(i)=1,2,3...(m-1) 稱為 線性探測(cè)；即 d(i)=i ，或者為其他線性函數(shù)。相當(dāng)于逐個(gè)探測(cè)存放地址的表，直到查找到一個(gè)空單元，把散列地址存放在該空單元。d(i)=1^2,  2^2,3^2... k^2 (k < m/2) 稱為 平方探測(cè)。相對(duì)線性探測(cè)，相當(dāng)于發(fā)生碰撞時(shí)探測(cè)間隔 d(i)=i^2 個(gè)單元的位置是否為空，如果為空，將地址存放進(jìn)去。d(i)=偽隨機(jī)數(shù)序列，稱為 偽隨機(jī)探測(cè)。

線性探測(cè)法

下面筆者將以一個(gè)實(shí)例演示線性探測(cè)的過(guò)程，進(jìn)而分析線性探測(cè)的特點(diǎn)，引出平方探測(cè)關(guān)鍵字為{89,18,49,58,69}插入到一個(gè)散列表中的情況。此時(shí)線性探測(cè)的方法是取d(i)=i。并假定取關(guān)鍵字除以 10 的余數(shù)為散列函數(shù)法則。

1、開(kāi)始時(shí)hash(89)=9無(wú)沖突，直接插入；

2、hash(18)=8無(wú)沖突，直接插入；

3、hash(49)=9沖突了，開(kāi)放地址，將49放入下一個(gè)空閑地址0

4、hash(58) =8沖突了，開(kāi)放地址，將58放入9沖突 ，放入0沖突、放入1

5、hash(69) =9沖突，開(kāi)放地址，將69放入0沖突，放入1沖突，放入2

Tips：思考其缺點(diǎn)!

線性探測(cè)的方式十分簡(jiǎn)單，明白，每次插入總是能夠找到一個(gè)地址，但是慢慢會(huì)形成一個(gè)區(qū)塊，其結(jié)果稱為一次聚集。任何關(guān)鍵字需探測(cè)越來(lái)越多的次數(shù)才能解決沖突，且完成之后由簡(jiǎn)介的增大了區(qū)塊。當(dāng)填裝因子>0.5時(shí)，這種方式就不是個(gè)好的方法了!

平方探測(cè)法：

使用平方探測(cè)法可以解決線性探測(cè)的一次聚集問(wèn)題。一般選擇d(i)=i^2.。至于其具體的步驟讀者可以按照上面的實(shí)例自行的模擬一下。這種方式會(huì)出現(xiàn)二次聚集的情況：散列到同一位置的哪些元素將探測(cè)相同的備選單元。

3、雙散列、再散列

對(duì)于雙散列和再散列的方式筆者這里就不在多提了。讀者可以查閱下相關(guān)的資料?？偨Y(jié)：對(duì)于散列表的實(shí)現(xiàn)新手不必太過(guò)在意，關(guān)鍵在于理解散列相關(guān)的概念。了解并掌握散列函數(shù)的作用及一般的實(shí)現(xiàn)方式。了解一般hash沖突和常用解決辦法。

以上所述是小編給大家介紹的Java數(shù)據(jù)結(jié)構(gòu)之散列表(動(dòng)力節(jié)點(diǎn)Java學(xué)院整理)，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

最新評(píng)論