深入淺析Java中的散列表

這期內容當中小編將會給大家帶來有關深入淺析Java中的散列表，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

基本概念

散列表(Hash table，也叫哈希表)，是根據關鍵字(key value)而直接進行訪問的數據結構。

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

實現key值映射的函數就叫做散列函數

存放記錄的數組就就叫做散列表

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

散列

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

散列的運用：

1、加密散列，在信息安全領域使用

2、散列表，一種使用散列函數將鍵名和鍵值關聯起來的數據結構

3、關聯數組，一種常常使用散列表來實現的數據結構

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

散列函數

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

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

 /** 
  * 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.stringHash42((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中散列函數的具體實現。JDK1.7這里筆者對常用的散列算法做一個展示：

散列表

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

散列函數的構造

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

1、直接地址法：

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

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

2、數字分析法：

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

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

3、平方取中法：

先通過求關鍵字的平方值擴大相近數的差別，然后根據表長度取中間的幾位數作為散列函數值。

Tips：這種方式中間的幾位數都和關鍵字的沒一位都有關，產生的散列地址較為的均勻。

4、折疊法:

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

5、除留余法：

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

6、隨機法：

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

哈希沖突

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

1、分離連接法：

首先看看分離連接法，說白了這種方式就是鏈表數組的方式，將散列到同一個值得所有元素保存在一個表中，產生相同的一個值在散列表中使用鏈表的形式存儲。哈希沖突的位置就是鏈表的開始位置。在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)為散列函數，m為散列表長，d(i)為增量序列，i為已發生碰撞的次數。增量序列可有下列取法：

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

線性探測法

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

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：思考其缺點!

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

平方探測法：

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

3、雙散列、再散列

對于雙散列和再散列的方式筆者這里就不在多提了。讀者可以查閱下相關的資料。總結：對于散列表的實現新手不必太過在意，關鍵在于理解散列相關的概念。了解并掌握散列函數的作用及一般的實現方式。了解一般hash沖突和常用解決辦法。

上述就是小編為大家分享的深入淺析Java中的散列表了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。