基本概念
散列表(Hash table，也叫哈希表)，是根據(jù)關鍵字(key value)而直接進行訪問的數(shù)據(jù)結構。
說的具體點就是它通過吧key值映射到表中的一個位置來訪問記錄，從而加快查找的速度。
實現(xiàn)key值映射的函數(shù)就叫做散列函數(shù)
存放記錄的數(shù)組就就叫做散列表
實現(xiàn)散列表的過程通常就稱為散列(hashing)，也就是常說的hash
散列
這里的散列的概念不僅限于數(shù)據(jù)結構了，在計算機科學領域中，散列-哈希是一種對信息的處理方法，通過某種特定的函數(shù)/算法(散列函數(shù)/hash()方法)將要檢索的項與用來檢索的索引--( 散列值)關聯(lián)起來，生成一種便于搜索的數(shù)據(jù)結構--散列表。如今，由于散列算法所計算的散列值 具有不可逆(無法逆向演算會原來的數(shù)值)的性質(zhì)，因此散列算法廣泛的運用于加密技術。
散列的運用：
1、加密散列，在信息安全領域使用
2、散列表，一種使用散列函數(shù)將鍵名和鍵值關聯(lián)起來的數(shù)據(jù)結構
3、關聯(lián)數(shù)組，一種常常使用散列表來實現(xiàn)的數(shù)據(jù)結構
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沖突的解決辦法，將在后面予以總結。至于散列函數(shù)的具體實現(xiàn)，有很多加密技術都有十分nice的實現(xiàn)，這里我們看看Java中HashMap的hash()方法實現(xiàn)就可以了。HashMap采用的是內(nèi)部哈希技術實現(xiàn)的，其中hash()方法就是散列函數(shù)，完成key值到數(shù)組索引位置的映射。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/** * 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ù)的構造
對于散列表這種數(shù)據(jù)結構來說，其散列函數(shù)的構造是十分關鍵的，散列函數(shù)實現(xiàn)了key的映射,并且訪問記錄可以更快的被定位。一般來說散列函數(shù)的構造基于兩個標準:簡單、均勻簡單指散列算法簡單快捷，散列值生成簡單。均勻指對于key值集合中的任一關鍵字，散列函數(shù)能夠以均與的概率映射到數(shù)組的任一一個索引位置上，這樣能夠減少散列碰撞。
散列函數(shù)構造方法：
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之間。總結:在上述的方法中，3、4、5三種方法的結合使用方式較好，在JDK以前的版本就是使用的方法5。
哈希沖突
通過上面的學習中，我們知道散列函數(shù)得到的key - 索引位置 并不是唯一對應的，可能造成不同的key值對應相同的索引位置。這是我們應該解決的問題。實際的解決方法一般如下：
1、分離連接法：
首先看看分離連接法，說白了這種方式就是鏈表數(shù)組的方式，將散列到同一個值得所有元素保存在一個表中，產(chǎn)生相同的一個值在散列表中使用鏈表的形式存儲。哈希沖突的位置就是鏈表的開始位置。在JKD中HashMap就是這種方式解決哈希沖突的!
HashMap中沖突處理代碼如下
|
1
2
3
4
5
6
7
8
9
|
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ù)法則。
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ū)塊，其結果稱為一次聚集。任何關鍵字需探測越來越多的次數(shù)才能解決沖突，且完成之后由簡介的增大了區(qū)塊。當填裝因子>0.5時，這種方式就不是個好的方法了!
平方探測法：
使用平方探測法可以解決線性探測的一次聚集問題。一般選擇d(i)=i^2.。至于其具體的步驟讀者可以按照上面的實例自行的模擬一下。這種方式會出現(xiàn)二次聚集的情況：散列到同一位置的哪些元素將探測相同的備選單元。
3、雙散列、再散列
對于雙散列和再散列的方式筆者這里就不在多提了。讀者可以查閱下相關的資料。總結：對于散列表的實現(xiàn)新手不必太過在意，關鍵在于理解散列相關的概念。了解并掌握散列函數(shù)的作用及一般的實現(xiàn)方式。了解一般hash沖突和常用解決辦法。
以上所述是小編給大家介紹的Java數(shù)據(jù)結構之散列表(動力節(jié)點Java學院整理)，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對服務器之家網(wǎng)站的支持！
