深入理解哈希表

轉自：https://bestswifter.com/hashtable/

這篇文章由一個簡單的問題引出:

有兩個字典，分別存有 100 條數據和 10000 條數據，如果用一個不存在的 key 去查找數據，在哪個字典中速度更快？

有些計算機常識的讀者都會立刻回答: “一樣快，底層都用了哈希表，查找的時間復雜度為 O(1)”。然而實際情況真的是這樣么？

答案是否定的，存在少部分情況兩者速度不一致，本文首先對哈希表做一個簡短的總結，然后思考 Java 和 Redis 中對哈希表的實現，最后再得出結論，如果對某個話題已經很熟悉，可以直接跳到文章末尾的對比和總結部分。

哈希表概述

Objective-C 中的字典?NSDictionary?底層其實是一個哈希表，實際上絕大多數語言中字典都通過哈希表實現，比如我曾經分析過的?Swift 字典的實現原理。

在討論哈希表之前，先規范幾個接下來會用到的概念。哈希表的本質是一個數組，數組中每一個元素稱為一個箱子(bin)，箱子中存放的是鍵值對。

哈希表的存儲過程如下:

1. 根據 key 計算出它的哈希值 h。
2. 假設箱子的個數為 n，那么這個鍵值對應該放在第?(h % n)?個箱子中。
3. 如果該箱子中已經有了鍵值對，就使用開放尋址法或者拉鏈法解決沖突。

在使用拉鏈法解決哈希沖突時，每個箱子其實是一個鏈表，屬于同一個箱子的所有鍵值對都會排列在鏈表中。

哈希表還有一個重要的屬性: 負載因子(load factor)，它用來衡量哈希表的?空/滿?程度，一定程度上也可以體現查詢的效率，計算公式為:

負載因子 = 總鍵值對數 / 箱子個數

負載因子越大，意味著哈希表越滿，越容易導致沖突，性能也就越低。因此，一般來說，當負載因子大于某個常數(可能是 1，或者 0.75 等)時，哈希表將自動擴容。

哈希表在自動擴容時，一般會創建兩倍于原來個數的箱子，因此即使 key 的哈希值不變，對箱子個數取余的結果也會發生改變，因此所有鍵值對的存放位置都有可能發生改變，這個過程也稱為重哈希(rehash)。

哈希表的擴容并不總是能夠有效解決負載因子過大的問題。假設所有 key 的哈希值都一樣，那么即使擴容以后他們的位置也不會變化。雖然負載因子會降低，但實際存儲在每個箱子中的鏈表長度并不發生改變，因此也就不能提高哈希表的查詢性能。

基于以上總結，細心的讀者可能會發現哈希表的兩個問題:

1. 如果哈希表中本來箱子就比較多，擴容時需要重新哈希并移動數據，性能影響較大。
2. 如果哈希函數設計不合理，哈希表在極端情況下會變成線性表，性能極低。

我們分別通過 Java 和 Redis 的源碼來理解以上問題，并看看他們的解決方案。

Java 8 中的哈希表

JDK 的代碼是開源的，可以從這里下載到，我們要找的 HashMap.java 文件的目錄在?openjdk/jdk/src/share/classes/java/util/HashMap.java。

HashMap 是基于 HashTable 的一種數據結構，在普通哈希表的基礎上，它支持多線程操作以及空的 key 和 value。

在 HashMap 中定義了幾個常量:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64; 

依次解釋以上常量:

1. DEFAULT_INITIAL_CAPACITY: 初始容量，也就是默認會創建 16 個箱子，箱子的個數不能太多或太少。如果太少，很容易觸發擴容，如果太多，遍歷哈希表會比較慢。
2. MAXIMUM_CAPACITY: 哈希表最大容量，一般情況下只要內存夠用，哈希表不會出現問題。
3. DEFAULT_LOAD_FACTOR: 默認的負載因子。因此初始情況下，當鍵值對的數量大于?16 * 0.75 = 12?時，就會觸發擴容。
4. TREEIFY_THRESHOLD: 上文說過，如果哈希函數不合理，即使擴容也無法減少箱子中鏈表的長度，因此 Java 的處理方案是當鏈表太長時，轉換成紅黑樹。這個值表示當某個箱子中，鏈表長度大于 8 時，有可能會轉化成樹。
5. UNTREEIFY_THRESHOLD: 在哈希表擴容時，如果發現鏈表長度小于 6，則會由樹重新退化為鏈表。
6. MIN_TREEIFY_CAPACITY: 在轉變成樹之前，還會有一次判斷，只有鍵值對數量大于 64 才會發生轉換。這是為了避免在哈希表建立初期，多個鍵值對恰好被放入了同一個鏈表中而導致不必要的轉化。

學過概率論的讀者也許知道，理想狀態下哈希表的每個箱子中，元素的數量遵守泊松分布:

當負載因子為 0.75 時，上述公式中 λ 約等于 0.5，因此箱子中元素個數和概率的關系如下:

| 數量 | 概率 | | :--: |:-----:| | 0 | 0.60653066 | | 1 | 0.30326533 | | 2 | 0.07581633 | | 3 | 0.01263606 | | 4 | 0.00157952 | | 5 | 0.00015795 | | 6 | 0.00001316 | | 7 | 0.00000094 | | 8 | 0.00000006 |

這就是為什么箱子中鏈表長度超過 8 以后要變成紅黑樹，因為在正常情況下出現這種現象的幾率小到忽略不計。一旦出現，幾乎可以認為是哈希函數設計有問題導致的。

Java 對哈希表的設計一定程度上避免了不恰當的哈希函數導致的性能問題，每一個箱子中的鏈表可以與紅黑樹切換。

Redis

Redis 是一個高效的 key-value 緩存系統，也可以理解為基于鍵值對的數據庫。它對哈希表的設計有非常多值得學習的地方，在不影響源代碼邏輯的前提下我會盡可能簡化，突出重點。

數據結構

在 Redis 中，字典是一個?dict?類型的結構體，定義在?src/dict.h?中:

typedef struct dict {  dictht ht[2];long rehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict; 

這里的?dictht?是用于存儲數據的結構體。注意到我們定義了一個長度為 2 的數組，它是為了解決擴容時速度較慢而引入的，其原理后面會詳細介紹，rehashidx?也是在擴容時需要用到。先看一下?dictht?的定義:

typedef struct dictht {  dictEntry **table;unsigned long size;unsigned long used; } dictht; 

可見結構體中有一個二維數組?table，元素類型是?dictEntry，對應著存儲的一個鍵值對:

typedef struct dictEntry {  void *key;union {void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry; 

從?next?指針以及二維數組可以看出，Redis 的哈希表采用拉鏈法解決沖突。

整個字典的層次結構如下圖所示:

添加元素

向字典中添加鍵值對的底層實現如下:

dictEntry *dictAddRaw(dict *d, void *key) {  int index; dictEntry *entry; dictht *ht; if (dictIsRehashing(d)) _dictRehashStep(d); if ((index = _dictKeyIndex(d, key)) == -1) return NULL; ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; entry = zmalloc(sizeof(*entry)); entry->next = ht->table[index]; ht->table[index] = entry; ht->used++; dictSetKey(d, entry, key); return entry; } 

dictIsRehashing?函數用來判斷哈希表是否正在重新哈希。所謂的重新哈希是指在擴容時，原來的鍵值對需要改變位置。為了優化重哈希的體驗，Redis 每次只會移動一個箱子中的內容，下一節會做詳細解釋。

仔細閱讀指針操作部分就會發現，新插入的鍵值對會放在箱子中鏈表的頭部，而不是在尾部繼續插入。這個細節上的改動至少帶來兩個好處:

1. 找到鏈表尾部的時間復雜度是 O(n)，或者需要使用額外的內存地址來保存鏈表尾部的位置。頭插法可以節省插入耗時。
2. 對于一個數據庫系統來說，最新插入的數據往往更有可能頻繁的被獲取。頭插法可以節省查找耗時。

增量式擴容

所謂的增量式擴容是指，當需要重哈希時，每次只遷移一個箱子里的鏈表，這樣擴容時不會出現性能的大幅度下降。

為了標記哈希表正處于擴容階段，我們在?dict?結構體中使用?rehashidx?來表示當前正在遷移哪個箱子里的數據。由于在結構體中實際上有兩個哈希表，如果添加新的鍵值對時哈希表正在擴容，我們首先從第一個哈希表中遷移一個箱子的數據到第二個哈希表中，然后鍵值對會被插入到第二個哈希表中。

在上面給出的?dictAddRaw?方法的實現中，有兩句代碼:

if (dictIsRehashing(d)) _dictRehashStep(d);  
// ...
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];  

第二句就是用來選擇插入到哪個哈希表中，第一句話則是遷移?rehashidx?位置上的鏈表。它實際上會調用?dictRehash(d,1)，也就是說是單步長的遷移。dictRehash?函數的實現如下:

int dictRehash(dict *d, int n) {  int empty_visits = n*10; /* Max number of empty buckets to visit. */ while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; while(d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits == 0) return 1; } de = d->ht[0].table[d->rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ while(de) { unsigned int h; nextde = de->next; /* Get the index in the new hash table */ h = dictHashKey(d, de->key) & d->ht[1].sizemask; de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; d->ht[0].used--; d->ht[1].used++; de = nextde; } d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; } /* Check if we already rehashed the whole table... */ if (d->ht[0].used == 0) { zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; return 0; } return 1; } 

這段代碼比較長，但是并不難理解。它由一個 while 循環和 if 語句組成。在單步遷移的情況下，最外層的 while 循環沒有意義，而它內部又可以分為兩個 while 循環。

第一個循環用來更新?rehashidx?的值，因為有些箱子為空，所以?rehashidx?并非每次都比原來前進一個位置，而是有可能前進幾個位置，但最多不超過 10。第二個循環則用來復制鏈表數據。

最外面的 if 判斷中，如果發現舊哈希表已經全部完成遷移，就會釋放舊哈希表的內存，同時把新的哈希表賦值給舊的哈希表，最后把?rehashidx?重新設置為 -1，表示重哈希過程結束。

默認哈希函數

與 Java 不同的是，Redis 提供了?void *?類型 key 的哈希函數，也就是通過任何類型的 key 的指針都可以求出哈希值。具體算法定義在?dictGenHashFunction?函數中，由于代碼過長，而且都是一些位運算，就不展示了。

它的實現原理是根據指針地址和這一塊內存的長度，獲取內存中的值，并且放入到一個數組當中，可見這個數組僅由 0 和 1 構成。然后再對這些數字做哈希運算。因此即使兩個指針指向的地址不同，但只要其中內容相同，就可以得到相同的哈希值。

歸納對比

首先我們回顧一下 Java 和 Redis 的解決方案。

Java 的長處在于當哈希函數不合理導致鏈表過長時，會使用紅黑樹來保證插入和查找的效率。缺點是當哈希表比較大時，如果擴容會導致瞬時效率降低。

Redis 通過增量式擴容解決了這個缺點，同時拉鏈法的實現(放在鏈表頭部)值得我們學習。Redis 還提供了一個經過嚴格測試，表現良好的默認哈希函數，避免了鏈表過長的問題。

Objective-C 的實現和 Java 比較類似，當我們需要重寫?isEqual()?方法時，還需要重寫?hash?方法。這兩種語言并沒有提供一個通用的、默認的哈希函數，主要是考慮到?isEqual()?方法可能會被重寫，兩個內存數據不同的對象可能在語義上被認為是相同的。如果使用默認的哈希函數就會得到不同的哈希值，這兩個對象就會同時被添加到?NSSet?集合中，這可能違背我們的期望結果。

根據我的了解，Redis 并不支持重寫哈希方法，難道 Redis 就沒有考慮到這個問題么？實際上還要從 Redis 的定位說起。由于它是一個高效的，Key-Value 存儲系統，它的 key 并不會是一個對象，而是一個用來唯一確定對象的標記。

一般情況下，如果要存儲某個用戶的信息，key 的值可能是這樣:?user:100001。Redis 只關心 key 的內存中的數據，因此只要是可以用二進制表示的內容都可以作為 key，比如一張圖片。Redis 支持的數據結構包括哈希表和集合(Set)，但是其中的數據類型只能是字符串。因此 Redis 并不存在對象等同性的考慮，也就可以提供默認的哈希函數了。

Redis、Java、Objective-C 之間的異同再次證明了一點:

沒有完美的架構，只有滿足需求的架構。

總結

回到文章開頭的問題中來，有兩個字典，分別存有 100 條數據和 10000 條數據，如果用一個不存在的 key 去查找數據，在哪個字典中速度更快？

完整的答案是:

在 Redis 中，得益于自動擴容和默認哈希函數，兩者查找速度一樣快。在 Java 和 Objective-C 中，如果哈希函數不合理，返回值過于集中，會導致大字典更慢。Java 由于存在鏈表和紅黑樹互換機制，搜索時間呈對數級增長，而非線性增長。在理想的哈希函數下，無論字典多大，搜索速度都是一樣快。

最后，整理了一下本文提到的知識點，希望大家讀完文章后對以下問題有比較清楚透徹的理解:

1. 哈希表中負載因子的概念
2. 哈希表擴容的過程，以及對查找性能的影響
3. 哈希表擴容速度的優化，拉鏈法插入新元素的優化，鏈表過長時的優化
4. 不同語言、使用場景下的取舍

參考資料

1. OpenJDK Source Release
2. HashMap vs Hashtable vs HashSet
3. 泊松分布
4. Redis Source code
5. An introduction to Redis data types and abstractions