這篇文章由一個(gè)簡單的問題引出:

有兩個(gè)字典，分別存有 100 條數(shù)據(jù)和 10000 條數(shù)據(jù)，如果用一個(gè)不存在的 key 去查找數(shù)據(jù)，在哪個(gè)字典中速度更快冠胯？

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

答案是否定的，存在少部分情況兩者速度不一致割粮，本文首先對哈希表做一個(gè)簡短的總結(jié)盾碗，然后思考 Java 和 Redis 中對哈希表的實(shí)現(xiàn)，最后再得出結(jié)論舀瓢，如果對某個(gè)話題已經(jīng)很熟悉廷雅，可以直接跳到文章末尾的對比和總結(jié)部分。

哈希表概述

Objective-C 中的字典 NSDictionary 底層其實(shí)是一個(gè)哈希表京髓，實(shí)際上絕大多數(shù)語言中字典都通過哈希表實(shí)現(xiàn)航缀，比如我曾經(jīng)分析過的 Swift 字典的實(shí)現(xiàn)原理。

在討論哈希表之前堰怨，先規(guī)范幾個(gè)接下來會用到的概念芥玉。哈希表的本質(zhì)是一個(gè)數(shù)組，數(shù)組中每一個(gè)元素稱為一個(gè)箱子(bin)备图，箱子中存放的是鍵值對灿巧。

哈希表的存儲過程如下:

1. 根據(jù) key 計(jì)算出它的哈希值 h。
2. 假設(shè)箱子的個(gè)數(shù)為 n揽涮，那么這個(gè)鍵值對應(yīng)該放在第 (h % n) 個(gè)箱子中抠藕。
3. 如果該箱子中已經(jīng)有了鍵值對，就使用開放尋址法或者拉鏈法解決沖突蒋困。

在使用拉鏈法解決哈希沖突時(shí)盾似，每個(gè)箱子其實(shí)是一個(gè)鏈表，屬于同一個(gè)箱子的所有鍵值對都會排列在鏈表中雪标。

哈希表還有一個(gè)重要的屬性: 負(fù)載因子(load factor)零院，它用來衡量哈希表的 空/滿 程度，一定程度上也可以體現(xiàn)查詢的效率村刨，計(jì)算公式為:

負(fù)載因子 = 總鍵值對數(shù) / 箱子個(gè)數(shù)

負(fù)載因子越大告抄，意味著哈希表越滿，越容易導(dǎo)致沖突嵌牺，性能也就越低打洼。因此，一般來說髓梅，當(dāng)負(fù)載因子大于某個(gè)常數(shù)(可能是 1拟蜻，或者 0.75 等)時(shí)绎签，哈希表將自動擴(kuò)容枯饿。

哈希表在自動擴(kuò)容時(shí)，一般會創(chuàng)建兩倍于原來個(gè)數(shù)的箱子诡必，因此即使 key 的哈希值不變奢方，對箱子個(gè)數(shù)取余的結(jié)果也會發(fā)生改變搔扁，因此所有鍵值對的存放位置都有可能發(fā)生改變，這個(gè)過程也稱為重哈希(rehash)蟋字。

哈希表的擴(kuò)容并不總是能夠有效解決負(fù)載因子過大的問題稿蹲。假設(shè)所有 key 的哈希值都一樣，那么即使擴(kuò)容以后他們的位置也不會變化鹊奖。雖然負(fù)載因子會降低苛聘，但實(shí)際存儲在每個(gè)箱子中的鏈表長度并不發(fā)生改變，因此也就不能提高哈希表的查詢性能忠聚。

基于以上總結(jié)设哗，細(xì)心的讀者可能會發(fā)現(xiàn)哈希表的兩個(gè)問題:

1. 如果哈希表中本來箱子就比較多，擴(kuò)容時(shí)需要重新哈希并移動數(shù)據(jù)两蟀，性能影響較大网梢。
2. 如果哈希函數(shù)設(shè)計(jì)不合理，哈希表在極端情況下會變成線性表赂毯，性能極低战虏。

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

Java 8 中的哈希表

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

HashMap 是基于 HashTable 的一種數(shù)據(jù)結(jié)構(gòu)啸盏，在普通哈希表的基礎(chǔ)上，它支持多線程操作以及空的 key 和 value骑祟。

在 HashMap 中定義了幾個(gè)常量:

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: 初始容量回懦，也就是默認(rèn)會創(chuàng)建 16 個(gè)箱子，箱子的個(gè)數(shù)不能太多或太少次企。如果太少怯晕，很容易觸發(fā)擴(kuò)容，如果太多缸棵，遍歷哈希表會比較慢舟茶。
2. MAXIMUM_CAPACITY: 哈希表最大容量，一般情況下只要內(nèi)存夠用堵第，哈希表不會出現(xiàn)問題吧凉。
3. DEFAULT_LOAD_FACTOR: 默認(rèn)的負(fù)載因子。因此初始情況下踏志，當(dāng)鍵值對的數(shù)量大于 16 * 0.75 = 12 時(shí)阀捅，就會觸發(fā)擴(kuò)容。
4. TREEIFY_THRESHOLD: 上文說過针余，如果哈希函數(shù)不合理饲鄙，即使擴(kuò)容也無法減少箱子中鏈表的長度凄诞，因此 Java 的處理方案是當(dāng)鏈表太長時(shí)，轉(zhuǎn)換成紅黑樹忍级。這個(gè)值表示當(dāng)某個(gè)箱子中帆谍，鏈表長度大于 8 時(shí)，有可能會轉(zhuǎn)化成樹轴咱。
5. UNTREEIFY_THRESHOLD: 在哈希表擴(kuò)容時(shí)汛蝙，如果發(fā)現(xiàn)鏈表長度小于 6，則會由樹重新退化為鏈表朴肺。
6. MIN_TREEIFY_CAPACITY: 在轉(zhuǎn)變成樹之前患雇，還會有一次判斷，只有鍵值對數(shù)量大于 64 才會發(fā)生轉(zhuǎn)換宇挫。這是為了避免在哈希表建立初期苛吱，多個(gè)鍵值對恰好被放入了同一個(gè)鏈表中而導(dǎo)致不必要的轉(zhuǎn)化。

學(xué)過概率論的讀者也許知道器瘪，理想狀態(tài)下哈希表的每個(gè)箱子中翠储，元素的數(shù)量遵守泊松分布:

當(dāng)負(fù)載因子為 0.75 時(shí)，上述公式中 λ 約等于 0.5橡疼，因此箱子中元素個(gè)數(shù)和概率的關(guān)系如下:

| 數(shù)量 | 概率 | | :--: |:-----:| | 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 以后要變成紅黑樹援所，因?yàn)樵谡Ｇ闆r下出現(xiàn)這種現(xiàn)象的幾率小到忽略不計(jì)。一旦出現(xiàn)欣除，幾乎可以認(rèn)為是哈希函數(shù)設(shè)計(jì)有問題導(dǎo)致的住拭。

Java 對哈希表的設(shè)計(jì)一定程度上避免了不恰當(dāng)?shù)墓：瘮?shù)導(dǎo)致的性能問題，每一個(gè)箱子中的鏈表可以與紅黑樹切換历帚。

Redis

Redis 是一個(gè)高效的 key-value 緩存系統(tǒng)滔岳，也可以理解為基于鍵值對的數(shù)據(jù)庫。它對哈希表的設(shè)計(jì)有非常多值得學(xué)習(xí)的地方挽牢，在不影響源代碼邏輯的前提下我會盡可能簡化谱煤，突出重點(diǎn)。

數(shù)據(jù)結(jié)構(gòu)

在 Redis 中禽拔，字典是一個(gè) dict 類型的結(jié)構(gòu)體刘离，定義在 src/dict.h 中:

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

這里的 dictht 是用于存儲數(shù)據(jù)的結(jié)構(gòu)體。注意到我們定義了一個(gè)長度為 2 的數(shù)組睹栖，它是為了解決擴(kuò)容時(shí)速度較慢而引入的硫惕，其原理后面會詳細(xì)介紹，rehashidx 也是在擴(kuò)容時(shí)需要用到野来。先看一下 dictht 的定義:

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

可見結(jié)構(gòu)體中有一個(gè)二維數(shù)組 table恼除，元素類型是 dictEntry，對應(yīng)著存儲的一個(gè)鍵值對:

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

從 next 指針以及二維數(shù)組可以看出梁只，Redis 的哈希表采用拉鏈法解決沖突缚柳。

整個(gè)字典的層次結(jié)構(gòu)如下圖所示:

image.png

添加元素

向字典中添加鍵值對的底層實(shí)現(xiàn)如下:

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 函數(shù)用來判斷哈希表是否正在重新哈希。所謂的重新哈希是指在擴(kuò)容時(shí)搪锣，原來的鍵值對需要改變位置秋忙。為了優(yōu)化重哈希的體驗(yàn)，Redis 每次只會移動一個(gè)箱子中的內(nèi)容构舟，下一節(jié)會做詳細(xì)解釋灰追。

仔細(xì)閱讀指針操作部分就會發(fā)現(xiàn)，新插入的鍵值對會放在箱子中鏈表的頭部狗超，而不是在尾部繼續(xù)插入弹澎。這個(gè)細(xì)節(jié)上的改動至少帶來兩個(gè)好處:

1. 找到鏈表尾部的時(shí)間復(fù)雜度是 O(n)，或者需要使用額外的內(nèi)存地址來保存鏈表尾部的位置努咐。頭插法可以節(jié)省插入耗時(shí)苦蒿。
2. 對于一個(gè)數(shù)據(jù)庫系統(tǒng)來說，最新插入的數(shù)據(jù)往往更有可能頻繁的被獲取渗稍。頭插法可以節(jié)省查找耗時(shí)佩迟。

增量式擴(kuò)容

所謂的增量式擴(kuò)容是指，當(dāng)需要重哈希時(shí)竿屹，每次只遷移一個(gè)箱子里的鏈表报强，這樣擴(kuò)容時(shí)不會出現(xiàn)性能的大幅度下降。

為了標(biāo)記哈希表正處于擴(kuò)容階段拱燃，我們在 dict 結(jié)構(gòu)體中使用 rehashidx 來表示當(dāng)前正在遷移哪個(gè)箱子里的數(shù)據(jù)秉溉。由于在結(jié)構(gòu)體中實(shí)際上有兩個(gè)哈希表，如果添加新的鍵值對時(shí)哈希表正在擴(kuò)容碗誉，我們首先從第一個(gè)哈希表中遷移一個(gè)箱子的數(shù)據(jù)到第二個(gè)哈希表中召嘶，然后鍵值對會被插入到第二個(gè)哈希表中。

在上面給出的 dictAddRaw 方法的實(shí)現(xiàn)中哮缺，有兩句代碼:

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

第二句就是用來選擇插入到哪個(gè)哈希表中苍蔬，第一句話則是遷移 rehashidx 位置上的鏈表。它實(shí)際上會調(diào)用 dictRehash(d,1)蝴蜓，也就是說是單步長的遷移碟绑。dictRehash 函數(shù)的實(shí)現(xiàn)如下:

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;
}

這段代碼比較長，但是并不難理解茎匠。它由一個(gè) while 循環(huán)和 if 語句組成格仲。在單步遷移的情況下，最外層的 while 循環(huán)沒有意義诵冒，而它內(nèi)部又可以分為兩個(gè) while 循環(huán)凯肋。

第一個(gè)循環(huán)用來更新 rehashidx 的值，因?yàn)橛行┫渥訛榭掌觯?rehashidx 并非每次都比原來前進(jìn)一個(gè)位置侮东，而是有可能前進(jìn)幾個(gè)位置圈盔，但最多不超過 10。第二個(gè)循環(huán)則用來復(fù)制鏈表數(shù)據(jù)悄雅。

最外面的 if 判斷中驱敲，如果發(fā)現(xiàn)舊哈希表已經(jīng)全部完成遷移，就會釋放舊哈希表的內(nèi)存宽闲，同時(shí)把新的哈希表賦值給舊的哈希表众眨，最后把 rehashidx 重新設(shè)置為 -1，表示重哈希過程結(jié)束容诬。

默認(rèn)哈希函數(shù)

與 Java 不同的是娩梨，Redis 提供了 void * 類型 key 的哈希函數(shù)，也就是通過任何類型的 key 的指針都可以求出哈希值览徒。具體算法定義在 dictGenHashFunction 函數(shù)中狈定，由于代碼過長，而且都是一些位運(yùn)算习蓬，就不展示了掸冤。

它的實(shí)現(xiàn)原理是根據(jù)指針地址和這一塊內(nèi)存的長度，獲取內(nèi)存中的值友雳，并且放入到一個(gè)數(shù)組當(dāng)中稿湿，可見這個(gè)數(shù)組僅由 0 和 1 構(gòu)成。然后再對這些數(shù)字做哈希運(yùn)算押赊。因此即使兩個(gè)指針指向的地址不同饺藤，但只要其中內(nèi)容相同，就可以得到相同的哈希值流礁。

歸納對比

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

Java 的長處在于當(dāng)哈希函數(shù)不合理導(dǎo)致鏈表過長時(shí)，會使用紅黑樹來保證插入和查找的效率神帅。缺點(diǎn)是當(dāng)哈希表比較大時(shí)再姑，如果擴(kuò)容會導(dǎo)致瞬時(shí)效率降低。

Redis 通過增量式擴(kuò)容解決了這個(gè)缺點(diǎn)找御，同時(shí)拉鏈法的實(shí)現(xiàn)(放在鏈表頭部)值得我們學(xué)習(xí)元镀。Redis 還提供了一個(gè)經(jīng)過嚴(yán)格測試，表現(xiàn)良好的默認(rèn)哈希函數(shù)霎桅，避免了鏈表過長的問題栖疑。

Objective-C 的實(shí)現(xiàn)和 Java 比較類似，當(dāng)我們需要重寫 isEqual() 方法時(shí)滔驶，還需要重寫 hash 方法遇革。這兩種語言并沒有提供一個(gè)通用的、默認(rèn)的哈希函數(shù)，主要是考慮到 isEqual() 方法可能會被重寫萝快，兩個(gè)內(nèi)存數(shù)據(jù)不同的對象可能在語義上被認(rèn)為是相同的锻霎。如果使用默認(rèn)的哈希函數(shù)就會得到不同的哈希值，這兩個(gè)對象就會同時(shí)被添加到 NSSet 集合中揪漩，這可能違背我們的期望結(jié)果旋恼。

根據(jù)我的了解，Redis 并不支持重寫哈希方法氢拥，難道 Redis 就沒有考慮到這個(gè)問題么？實(shí)際上還要從 Redis 的定位說起锨侯。由于它是一個(gè)高效的嫩海，Key-Value 存儲系統(tǒng)，它的 key 并不會是一個(gè)對象囚痴，而是一個(gè)用來唯一確定對象的標(biāo)記叁怪。

一般情況下，如果要存儲某個(gè)用戶的信息深滚，key 的值可能是這樣: user:100001奕谭。Redis 只關(guān)心 key 的內(nèi)存中的數(shù)據(jù)，因此只要是可以用二進(jìn)制表示的內(nèi)容都可以作為 key痴荐，比如一張圖片血柳。Redis 支持的數(shù)據(jù)結(jié)構(gòu)包括哈希表和集合(Set)，但是其中的數(shù)據(jù)類型只能是字符串生兆。因此 Redis 并不存在對象等同性的考慮难捌，也就可以提供默認(rèn)的哈希函數(shù)了。

Redis鸦难、Java根吁、Objective-C 之間的異同再次證明了一點(diǎn):

沒有完美的架構(gòu)，只有滿足需求的架構(gòu)合蔽。

總結(jié)

回到文章開頭的問題中來击敌，有兩個(gè)字典，分別存有 100 條數(shù)據(jù)和 10000 條數(shù)據(jù)拴事，如果用一個(gè)不存在的 key 去查找數(shù)據(jù)沃斤，在哪個(gè)字典中速度更快？

完整的答案是:

在 Redis 中刃宵，得益于自動擴(kuò)容和默認(rèn)哈希函數(shù)轰枝，兩者查找速度一樣快。在 Java 和 Objective-C 中组去，如果哈希函數(shù)不合理鞍陨，返回值過于集中，會導(dǎo)致大字典更慢。Java 由于存在鏈表和紅黑樹互換機(jī)制诚撵，搜索時(shí)間呈對數(shù)級增長缭裆，而非線性增長。在理想的哈希函數(shù)下寿烟，無論字典多大澈驼，搜索速度都是一樣快。

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

1. 哈希表中負(fù)載因子的概念
2. 哈希表擴(kuò)容的過程，以及對查找性能的影響
3. 哈希表擴(kuò)容速度的優(yōu)化徘六，拉鏈法插入新元素的優(yōu)化内边，鏈表過長時(shí)的優(yōu)化
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

轉(zhuǎn)自： [深入理解哈希表]