散列表 及其在 JDK 中的實現

語言: CN / TW / HK
時間 2022-05-09 19:15:05
主題:

雜湊表在 JDK 中的演進實現

雜湊表的原理

散列表（Hash table，也叫雜湊表），是根據鍵（Key）而直接訪問在記憶體儲存位置的資料結構。也就是說，它通過計算出一個鍵值的函式，將所需查詢的資料對映到表中一個位置來供外部訪問，這加快了查詢速度。這個對映函式稱做雜湊函式，存放記錄的陣列稱做散列表。

一個現實中的例子是，通訊錄是一個以聯絡人名稱首字母進行排序的表，我們可以快速定位到一個首字母上。類似索引的概念，索引的效率一般是 O(1) 的，效率非常高。

  • 若關鍵字為 k，則其值存放在 f(k) 的儲存位置上。由此，不需比較便可直接取得所查記錄。這個對應關係 f 為雜湊函式，按這個思想建立的表為散列表。

  • 對不同的關鍵字可能得到同一雜湊地址，即 f(k1) != f(k2)，而 f(k1)=f(k2) 種現象稱為衝突。當存在衝突時，會將其放到同一個索引下的不同儲存位置。

具有相同函式返回值的 Key 對該雜湊函式來說稱做同義詞。綜上所述，根據雜湊函式 f(k) 理衝突的方法將一組關鍵字對映到一個同一個位置上，這個位置是一個有限的連續的地址集（區間)。並以 Key 為基礎在這個地址集中分配一個儲存位置，這種表便稱為散列表，這一對映過程稱為雜湊造表或雜湊，所得的儲存位置稱雜湊地址。

  • 若對於關鍵字集合中的任一個關鍵字，經雜湊函式對映到地址集合中任何一個地址的概率是相等的，則稱此類雜湊函式為 均勻雜湊函式（Uniform Hash function），這就使關鍵字經過雜湊函式得到一個“隨機的地址”，從而減少衝突。

雜湊演算法

  1. 直接定址法：取關鍵字或關鍵字的某個線性函式值為雜湊地址。即 hash(k)=k 或 hash(k)=a * k + b，其中 a、b 為常數（這種雜湊函式叫做自身函式)。
  2. 數字分析法：假設關鍵字是以 r 為基的數，並且雜湊表中可能出現的關鍵字都是事先知道的，則可取關鍵字的若干數位組成雜湊地址。
  3. 平方取中法：取關鍵字平方後的中間幾位為雜湊地址。通常在選定雜湊函式時不一定能知道關鍵字的全部情況，取其中的哪幾位也不一定合適，而一個數平方後的中間幾位數和數的每一位都相關，由此使隨機分佈的關鍵字得到的雜湊地址也是隨機的。取的位數由表長決定。
  4. 摺疊法：將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為雜湊地址。
  5. 隨機數法：直接取隨機數。
  6. 除留餘數法：取關鍵字被某個不大於散列表表長m的數p除後所得的餘數為雜湊地址。即 hash(k) = k mod p, p <= m 。不僅可以對關鍵字直接取模，也可在摺疊法、平方取中法等運算之後取模。對 p 的選擇很重要，一般取素數或 m ，若 p 選擇不好，容易產生衝突。

處理衝突演算法

上面提到了元素通過雜湊函式處理好遇到衝突時，會通過一個處理衝突的方法進行處理，然後再分配到指定位置上。常見的處理演算法有以下幾種：

  • 開放地址法：遇到雜湊衝突時，往後續逐個查詢空位置，將衝突物件存到第一個空位置中。
  • 單獨連結串列法：將雜湊到同一個儲存位置的所有元素儲存在一個連結串列中。實現時，一種策略是散列表同一位置的所有衝突結果都是用棧存放的，新元素被插入到表的前端還是後端完全取決於怎樣方便。
  • 雙雜湊：http://zh.wikipedia.org/wiki/%E5%8F%8C%E6%95%A3%E5%88%97
  • 再雜湊：即在上次雜湊計算髮生衝突時，利用該次衝突的雜湊函式值產生新的雜湊函式值，直到衝突不再發生。這種方法不易產生聚集，但增加了計算時間。

查詢效率

散列表的查詢過程基本上和元素新增到表中的過程相同。一些元素的 Key 可通過雜湊函式轉換的地址直接找到，而另一些元素的 Key 在雜湊函式得到的地址產生了衝突，需要按處理衝突的方法進行查詢。

在介紹的三種處理衝突的方法中，產生衝突後的查詢仍然是給定值與 Key 進行比較的過程。所以，對散列表查詢效率的量度，依然用平均查詢長度來衡量。

查詢過程中，Key 的比較次數，取決於產生衝突的多少，產生的衝突少，查詢效率就高；產生的衝突多，查詢效率就低。因此，影響產生衝突多少的因素，也就是影響查詢效率的因素。影響產生衝突多少有以下三個因素：

  • 雜湊函式是否均勻
  • 處理衝突的方法
  • 散列表的載荷因子

載荷因子

散列表的載荷因子定義為：a = 填入表中的元素個數 / 散列表的長度 。

a 是散列表裝滿程度的標誌因子。由於表長是定值，a 與“填入表中的元素個數”成正比，所以，a 越大，表明填入表中的元素越多，產生衝突的可能性就越大；反之，a 越小，標明填入表中的元素越少，產生衝突的可能性就越小。實際上，散列表的平均查詢長度是載荷因子 a 的函式，只是不同處理衝突的方法有不同的函式。

在 Java 中，一般設定載荷因子為 0.75，超過此值會 resize 散列表。

為什麼選擇 0.75 呢？

通常，預設負載因子 (0.75) 在時間和空間成本之間提供了良好的折衷。較高的值會減少空間開銷，但會增加查詢條目的時間成本（這反映在大多數 Hashtable / HashMap 操作中，包括 get 和 put）。

JDK 中的雜湊表結構

Hashtable

Hashtable 繼承自 Dictionary 和 Map，Dictionary 介面已標記為過時，並引導使用 Map 介面進行替代。

Hashtable 是 JDK 中對散列表的實現，標準的散列表，雜湊演算法是通過物件自身的 hashCode 取模後再用除留餘數法處理。衝突處理演算法是單獨連結串列法。

它有以下特點：

  • 同步： put 、get、remove、containsKey 等操作方法都有 synchronized 修飾。

所以，他是把當前整個 Hashtable 結構進行了加鎖。

  • 底層實現是陣列 + 連結串列，不存在紅黑樹變種。

java // Hashtable 的 get 方法，內部是遍歷連結串列 public synchronized V get(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; // 取模 + 除留餘數 // Entry 連結串列結構 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return (V)e.value; } } return null; }

  • 不能存 null 值。

java public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // ... }

官方推薦，如果不需要執行緒安全，使用 HashMap 替代，如果需要執行緒安全，使用 ConcurrentHashMap 替代。基本上就是廢棄的資料結構了。

HashMap

HashMap 繼承自 AbstractMap 和 Map，它的操作方法沒有進行同步處理，所以 HashMap 不是執行緒安全的。

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

這裡的 putVal 是重點：

java final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 初始化容量 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 儲存位置為空，建立一個新的節點進行儲存 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 發生衝突， p 為原來已存在的 node Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 原有的元素與新的元素 key 相同，hash 值相同，直接覆蓋 e = p; else if (p instanceof TreeNode) // 如果是樹節點，通過 putTreeVal 處理 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 這裡 TREEIFY_THRESHOLD = 8，當這個 bin 中的元素 >= 7 時，資料結構轉換為紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 在連結串列中找到了相同的元素，直接 break， 此時 e = p.next if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 因為 e = p.next, 所以這裡是遍歷到下一個節點 p = p.next } } // 更新找到的節點的值 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

在這個 put 方法中，基本上涵蓋了所有的查詢邏輯：

  1. 如果 HashMap 的 table 陣列為空，resize 進行初始化。
  2. table 陣列中的指定的儲存位置為空，直接建立一個新的 Node 並儲存到這裡。
  3. 如果 table 中指定位置已經存在其他元素，發生衝突，分為三種情況：
  4. 原有的元素與新的元素 key 相同，hash 值相同，直接覆蓋；
  5. 若此元素是一個 TreeNode 節點，是紅黑樹結構，通過 putTreeVal 方法進行處理。
  6. 剩下的情況開始遍歷連結串列，遍歷時進行兩個步驟的處理
    1. 檢查當前這個 bin 中元素數量，如果大於等於 7，呼叫 treeifyBin 方法進行紅黑樹變形。
    2. 在列表中查詢到相同的元素，直接跳出遍歷。
  7. 如果經過查詢，能夠找到已有的節點，直接覆蓋成新的值。
  8. 最後檢查載荷因子，判斷是否需要進行 resize。

HashMap 的 get 方法內部呼叫的是 getNode 方法：

```java public V get(Object key) { Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; }

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

```

基本也是分為三個 case ：

  • 檢查第一個節點
  • 如果節點是樹結構，通過 getTreeNode 去查詢
  • 不是第一個節點也不是樹結構，遍歷連結串列查詢

這裡不管是 put 還是 set 都沒有對 null 進行丟擲 NPE 的處理，所以 HashMap 是可以存一個 null 的。

ConcurrentHashMap

最後是執行緒安全的 ConcurrentHashMap ， 從名字就可以看出這是個可用於併發的 HashMap 。

它繼承自 AbstractMap 並實現了 ConcurrentMap 。

它的內部資料結構和 HashMap 基本一致，不同的是，對 table 陣列進行了一些同步的處理。並且不允許將 null 用作鍵或值。

讀操作通過 CAS 和 volatile 進行處理；寫操作通過 synchronized 遍歷中的 node 處理，相比 Hashtable 鎖整張表，大大提高了效率。

java final V putVal(K key, V value, boolean onlyIfAbsent) { // 不允許 null 為 key 或 value if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; // 空 table 進行初始化操作 if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); // 如果正在進行調整大小，則有助於傳輸。 else { V oldVal = null; synchronized (f) { // 加鎖處理 if (tabAt(tab, i) == f) { // 存新的節點到連結串列中 if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } // 樹結構 else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } // resize 檢查 if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }

「」