Java數(shù)據(jù)結(jié)構(gòu)之散列表(動力節(jié)點Java學院整理)

更新時間：2017年04月14日 09:30:17 投稿：mrr

散列表(Hash table，也叫哈希表)，是根據(jù)關鍵字(key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。這篇文章給大家介紹了java數(shù)據(jù)結(jié)構(gòu)之散列表，包括基本概念和散列函數(shù)相關知識，需要的的朋友參考下吧

基本概念

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

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

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

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

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

散列

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

散列的運用：

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

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

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

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

散列函數(shù)

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

不過需要注意的是key值和經(jīng)過散列函數(shù)處理之后的散列值并不是唯一對應的，這就造成了不同的key值具有相同的索引位置，這種現(xiàn)象叫做散列碰撞、也稱其為哈希沖突。對于hash沖突的解決辦法，將在后面予以總結(jié)。至于散列函數(shù)的具體實現(xiàn)，有很多加密技術都有十分nice的實現(xiàn)，這里我們看看Java中HashMap的hash()方法實現(xiàn)就可以了。HashMap采用的是內(nèi)部哈希技術實現(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ù)的概念之后我們正式的進入到散列表的學習.一個通俗的例子是，為了查找電話簿中某人的號碼，可以創(chuàng)建一個按照人名首字母順序排列的表（即建立人名 x 到首字母 F(x) 的一個函數(shù)關系），在首字母為 W 的表中查找“王”姓的電話號碼，顯然比直接查找就要快得多。這里使用人名作為關鍵字，“取首字母”是這個例子中散列函數(shù)的函數(shù)法則 F()，存放首字母的表對應散列表。關鍵字和函數(shù)法則理論上可以任意確定。

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

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

1、直接地址法：

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

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

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

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

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

3、平方取中法：

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

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

4、折疊法:

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

5、除留余法：

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

6、隨機法：

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

哈希沖突

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

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(i)=1^2, 2^2,3^2... k^2 (k < m/2) 稱為平方探測。相對線性探測，相當于發(fā)生碰撞時探測間隔 d(i)=i^2 個單元的位置是否為空，如果為空，將地址存放進去。d(i)=偽隨機數(shù)序列，稱為偽隨機探測。

線性探測法

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