基本概念

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

說的具體點就是它通過吧key值映射到表中的一個位置來訪問記錄，從而加快查找的速度。

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

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

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

散列

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

散列的運用：

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

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

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

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

散列函數(shù)

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

不過需要注意的是key值和經(jīng)過散列函數(shù)處理之后的散列值并不是唯一對應(yīng)的，這就造成了不同的key值具有相同的索引位置，這種現(xiàn)象叫做散列碰撞、也稱其為哈希沖突。對于hash沖突的解決辦法，將在后面予以總結(jié)。至于散列函數(shù)的具體實現(xiàn)，有很多加密技術(shù)都有十分nice的實現(xiàn)，這里我們看看Java中HashMap的hash()方法實現(xiàn)就可以了。HashMap采用的是內(nèi)部哈希技術(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ù)的具體實現(xiàn)。JDK1.7這里筆者對常用的散列算法做一個展示：

散列表

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

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

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

1、直接地址法：

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

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

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

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

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

3、平方取中法：

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

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

4、折疊法:

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

5、除留余法：

取關(guān)鍵字被某個不大于散列表表長 m 的數(shù) p 除后所得的余數(shù)為散列地址。即 hash(k)= k mod p, p < m。不僅可以對關(guān)鍵字直接取模，也可在折疊法、平方取中法等運算之后取模。對 p 的選擇很重要，一般取素數(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。

哈希沖突

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

1、分離連接法：

首先看看分離連接法，說白了這種方式就是鏈表數(shù)組的方式，將散列到同一個值得所有元素保存在一個表中，產(chǎn)生相同的一個值在散列表中使用鏈表的形式存儲。哈希沖突的位置就是鏈表的開始位置。在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、開放地址法

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

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

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

線性探測法

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

1、開始時hash(89)=9無沖突，直接插入；

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

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

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

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

Tips：思考其缺點!

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

平方探測法：

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

3、雙散列、再散列

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

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

最新評論