散列數據結構以及在HashMap中的應用

1. 為什麼需要散列表?

對於線性表和鏈表而言，訪問表中的元素，時間複雜度均為O(n)。即便是通過樹結構存儲數據，時間複雜度也為O(logn)。那麼有沒有一種方式可以將這個時間複雜度降為O(1)呢？當然有，這就是接下來要介紹的散列表。散列表是普通數組概念的推廣。由於對於普通數組只要知道其下標位置就可以使用O(1)的時間內訪問任意元素，如果存儲空間允許，我們可以提供一個足夠大的數組，為每個可能的關鍵字保留一個位置，這個位置也被稱之「槽」，從而可以充分的利用直接定址的技術優勢，其實就是典型的空間換時間。

2. 散列函數

既然散列表是對關鍵字進行計算，從而確定該關鍵字對應的數據在存儲中的位置，在下文中統一稱之為「槽」，那麼又該通過什麼方式進行計算呢？其實這個方式就是散列函數。散列函數的設計對於散列表的性能將起到決定性的作用。因為如果散列函數設計不當導致多個關鍵字計算出的結果都是同一個位置，即存在大量的散列衝突（也可以稱為散列碰撞）。現如今存在的散列函數演算法非常多，通常的散列演算法都是將關鍵字轉換為自然數，然後通過除法或是乘法進行散列。一些簡單的散列演算法，比如關鍵字是整數直接使用求余法；關鍵字是字元串的話，一種可行的演算法是每個字元的ASCII碼相加之後對錶的長度進行取模。對於同一類型的關鍵字的散列演算法是多種多樣的，但無論如何應該儘可能的避免散列衝突並且保證其散列的結果是均勻分布的。之所以要儘可能的保證散列結果是均勻分布其實也是為了儘可能的避免散列衝突。

3.散列衝突以及衝突解決

但是無論散列演算法設計的多麼完美，散列衝突它都是一定存在的。因為對於散列表的大小而言它是固定的，一旦你初始化之後就不會改變。但是對於元素而言是可以無限制的添加的，換句話說就是散列表中的「槽」位，對於關鍵字來說總歸是不夠的，所以就會出現多個關鍵字通過散列函數計算出的「槽」位是相同的。

當散列衝突出現的時候，主要通過開放定址法、完全散列法、分離鏈接法等其他演算法解決衝突。

1.開放定址法

在開放定址法中，散列表中的每個槽位最多只會存儲一個元素。當出現散列衝突的時候，就會從該槽位出發選擇一個方向（向前或是向後）開始探測，（每次探測的距離為1則稱之為線性探查，距離為某個數字的平方則稱之為平方探查）只要散列表足夠大，總歸是可以找到一個可以存儲的槽位，但是如此花費的時間是相當多的。更糟糕的是，即使散列表相對較空這樣佔據的槽位一旦開始形成，當後面出現本應該放到該槽位的關鍵字由於已被佔據，而不得不進行探測尋找可以存儲的槽位，這種現象也被稱之為聚集。除此之外可以採用雙重散列法，使用一組散列函數，知道找到空閑的位置為止，一種比較流行的做法是使用兩個相對獨立的散列函數hash1()，hash2()。當發生碰撞時，通過步長i進行探測。

(hash1(key) + i * hash2(key)) % TABLE_SIZE

這種雙散列如果hash2()設計的不好將會是災難性的。一個好的hash2()表現好的特徵是：1.不會產生0索引、2.可以探測整個散列表

2.分離鏈接法

在分離鏈接法中，散列表中出現衝突時，可以通過鏈表的方式將元素連接起來，在對元素進行訪問時，若發現該槽位中是一個鏈表則對該鏈表進行遍歷。此種分離方式並不只是僅限於鏈表，比如一顆樹或是另一個散列表都是可以的。比如即將在下文中提到的HashMap就是使用鏈表+紅黑樹來實現的。

3.再散列

如果散列表很多槽位已經被佔據，name操作的運行時間將開始消耗過長，且插入操作可能失敗。此時一種解決方法是建立另外一個大約兩倍大的表，掃描整個原始散列表計算每個元素的新的槽位並將其插入到新的表中，整個操作就被稱為再散列。其實本質上就是通過擴容減少衝突。

4.完全散列法

雖然全域散列和完全散列具有良好的理論性能，但實現起來不太方便，前提條件也多。在實際應用上，往往會更偏向其他方式解決衝突。

4.動態擴容

因為散列表在創建的時候其大小是固定的，而關鍵字是不斷被添加到但列表中，所以隨著關鍵字的不斷添加，產生散列衝突的概率就會越來越大。因此為了避免哈希衝突就需要擴大散列表的容量。當已被佔據的「槽」的個數和散列表的大小的比例達到一定的閾值時，就開始執行散列表的擴容，而這個閾值也被稱之為載入因子（或擴容因子）。在擴容的時候，往往需要對原來的關鍵字重新進行散列，但是通過某些技巧其實是可以避免再散列的情況，比如HashMap的源碼中在擴容的時候就沒有進行再散列，這一部分在下文將詳細講解。

5.散列在HashMap的應用

1、散列函數

 1 public int hashCode() {
 2     int h = hash;
 3     if (h == 0 && value.length > 0) {
 4         char val[] = value;
 5         for (int i = 0; i < value.length; i++) {
 6             h = 31 * h + val[i];
 7         }
 8         hash = h;
 9     }
10     return h;
11 }

在這裡為什麼選擇31作為乘數，為什麼不是偶數或其他奇質數3,5,…,33,37,97…等其他數字? 原因如下：
1. 31 是一個奇質數，如果選擇偶數會導致乘積運算時數據溢出,造成數據丟失;
2.哈希碰撞:實驗數據表明乘數為大於等於31的奇質數碰撞概率很小,基本穩定;
3.哈希分布:實驗數據表明乘數為大於等於31的奇質數哈希分布相對來說較為均勻。
4.另外在二進位中,2的5次方是32，那麼也就是 31 * i == (i << 5) -i。這主要是說乘積運算可以使用位移提升性能，同時JVM 也會位移操作的優化。

2、擾動函數

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在這裡HashMap並沒有直接將key的散列值返回，而是進行了一次干擾計算

(h = key.hashCode()) ^ (h >>> 16)

把哈希值右移16位，也就是自己長度的一般，之後再與原哈希值進行異或運算。這樣做的目的就是混合哈希值中的高位和低位增大隨機性，使得哈希分布更加均勻，減少碰撞。

3、初始化容量

 1 static final int MAXIMUM_CAPACITY = 1 << 30;
 2 
 3 static final int tableSizeFor(int cap) {
 4     int n = cap - 1;
 5     n |= n >>> 1;
 6     n |= n >>> 2;
 7     n |= n >>> 4;
 8     n |= n >>> 8;
 9     n |= n >>> 16;
10     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
11 
12 }

在這裡進行初始化容量的時候，會不斷進行或運算將二進位數都填上1，目的就是去尋找2的次冪的最小值。如傳入的cap值為9則返回距離9最小的2的次冪值即16。那在這裡為什麼需要尋找2的次冪的最小值呢？

4、插入、鏈表樹化、紅黑樹

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

通過源碼分析，HashMap增加元素的過程如下:
1. 如果散列表不存在或是其長度為0則進行一次擴容操作
2. 通過key的哈希值對散列表的長度進行與計算獲得槽位
2.1 若該槽位對應的元素為空
直接添加一個節點，添加節點後需要判斷是否超過負載閾值，超過則進行擴容。
2.2 該槽位存在值
2.2.1 判斷key是否與當前的key一致
一致時，修改該元素，然後返回舊值。
2.2.2 判斷該槽位對應的元素是否為樹節點，這個樹其實是一顆紅黑樹為樹節點時，則進入putTreeVal()方法，這個方法要做的事簡單的說就是「根據哈希值遍歷樹的結構，是否可以找到該key，若是可以找到就返回該節點，若是找不到就會新增的一個節點，並且平衡該樹，最終返回一個空值」。putTreeVal()方法在新增節點的是後續返回null最終需要判斷是否超過負載閾值，超過則進行擴容；修改節點時返回該節點數據，則將該樹節點對應的值修改為當前的value並直接返回。
2.2.3 說明這個槽位對應的元素是一個鏈表
為鏈表時，則先對鏈表進行遍歷，是否可以找到該key，若可以找到則將該元素，則將該節點的值修改為value並退出；找不到該key時，說明這是一個新增元素，所以會在鏈表的尾部在添加一個節點。添加完節點後還需要判斷該鏈表的長度是否超過了閾值(默認是8)，超過閾值後並且表的大小還要超過64，則會將該鏈表進行轉成二叉樹，然後在轉成紅黑樹，在轉換成樹的時候也會記錄各節點的在鏈表中的位置；否則也只會對該散列表進行擴容。最終判斷是否超過負載閾值，超過則進行擴容。

4、負載因子

 1 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 2  
 3 public HashMap(int initialCapacity) {
 4     this(initialCapacity, DEFAULT_LOAD_FACTOR);
 5 }
 6  
 7 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
 8     int s = m.size();
 9     if (s > 0) {
10         if (table == null) { // pre-size
11             float ft = ((float)s / loadFactor) + 1.0F;
12             int t = ((ft < (float)MAXIMUM_CAPACITY) ?  (int)ft : MAXIMUM_CAPACITY);
13             if (t > threshold)
14                 threshold = tableSizeFor(t);
15         }
16         else if (s > threshold)
17             resize();
18         for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
19             K key = e.getKey();
20             V value = e.getValue();
21             putVal(hash(key), key, value, false, evict);
22         }
23     }
24 }

負載因子是關鍵字與散列表大小的比值，它決定了數據量達到多少之後進行擴容，默認的負載因子為0.75。如果希望以更多的空間換時間，盡量避免散列碰撞，則可以手動指定更小的負載因子。

5、擴容元素拆分

當數組長度不足時，或是當前關鍵字與散列表大小的比值超過了負載因子則進行散列表的擴容。在jdk1.7中，散列表擴容時，需要進行再散列的操作，重新計算各個key在新表中的槽位。而在jdk1.8中，擴容機制進行了優化，已經不需要進行再散列了，而是通過該key新的哈希值與原來的散列表進行與運算【key.hash()&oldCap==0】,如果為0，則不需要修改槽位，否則將該槽位移動到原來的位置+oldCap的位置，即【j+oldCap】。當紅黑樹擴容後的節點數小於 UNTREEIFY_THRESHOLD（默認是6）即小於7個節點數時，紅黑樹則會進行鏈化，因為鏈表在轉成紅黑樹的時候，是有記錄各節點在鏈表中的位置的，所以紅黑樹在轉成鏈表的時候會相對簡單很多。

6、查找

HashMap查找元素的過程如下:
1. 通過散列函數計算並且擾動後的哈希值
2. 若散列表為空或其大小為0，則直接返回null；
3. 根據計算出的哈希值與散列表的大小-1做與運算獲得槽位【在表中的下標索引】
4. 該槽位的元素是否為樹節點
4.1 不為樹節點，按鏈表形式進行遍歷
4.2 為樹節點，則按照紅黑樹形式進行遍歷

10、刪除

HashMap刪除元素的過程如下:
1. 通過散列函數計算並且擾動後的哈希值
2. 若散列表為空或其大小為0，則直接返回null；
3. 根據計算出的哈希值與散列表的大小-1做與運算獲得槽位【在表中的下標索引】
4. 該槽位的元素是否為樹節點
4.1 不為樹節點，按鏈表形式進行刪除
4.2 為樹節點，則按照紅黑樹形式進行刪除，刪除之後會進行紅黑樹的平衡

Tags: HashMap hash演算法散列表散列表在Java中的應用