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

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

答案是否定的师坎，存在少部分情況兩者速度不一致，本文首先對(duì)哈希表做一個(gè)簡(jiǎn)短的總結(jié)堪滨，然后思考 Java 和 Redis 中對(duì)哈希表的實(shí)現(xiàn)胯陋，最后再得出結(jié)論。

1. 介紹

散列表（Hash table袱箱，也叫哈希表）遏乔，是根據(jù)鍵值對(duì)（Key value）而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)发笔，它通過(guò)把鍵值對(duì)映射到表中一個(gè)位置來(lái)訪問(wèn)記錄盟萨，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)了讨，存放記錄的數(shù)組叫做哈希表鸯旁。

給定表 M，存在函數(shù) f(key)量蕊，對(duì)任意給定的鍵值 key铺罢，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表 M 為哈希(Hash)表残炮，函數(shù) f(key) 為哈希(Hash) 函數(shù)韭赘。

鏈表查找可能會(huì)從鏈表的頭結(jié)點(diǎn)開始遍歷，依次將每個(gè)結(jié)點(diǎn)中的信息與查詢條件進(jìn)行比較势就，直到查找成功或者失敗為止泉瞻，這種做法的時(shí)間復(fù)雜度為 O(n)。即使采用二叉排序樹進(jìn)行存儲(chǔ)苞冯，也最多為 O(logn)袖牙。Hash 表通過(guò)查詢條件可以直接獲取到該記錄在表中的存儲(chǔ)位置，復(fù)雜度直接降到 O(1)舅锄。

Hash 表采用一個(gè)映射函數(shù) f : key —> address 將關(guān)鍵字映射到該記錄在表中的存儲(chǔ)位置鞭达，從而在想要查找該記錄時(shí)，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計(jì)算出該記錄在表中的存儲(chǔ)位置，通常情況下畴蹭，這種映射關(guān)系稱作為 Hash 函數(shù)坦仍，而通過(guò) Hash 函數(shù)和關(guān)鍵字計(jì)算出來(lái)的存儲(chǔ)位置（注意這里的存儲(chǔ)位置只是表中的存儲(chǔ)位置，并不是實(shí)際的物理地址）稱作為 Hash 地址叨襟。

2.概述

Objective-C 中的字典 NSDictionary 底層其實(shí)是一個(gè)哈希表繁扎，實(shí)際上絕大多數(shù)語(yǔ)言中字典都通過(guò)哈希表實(shí)現(xiàn)，比如 Swift 字典的實(shí)現(xiàn)原理糊闽。

在討論哈希表之前梳玫，先規(guī)范幾個(gè)接下來(lái)會(huì)用到的概念。哈希表的本質(zhì)是一個(gè)數(shù)組右犹，數(shù)組中每一個(gè)元素稱為一個(gè)箱子(bin)汽纠，箱子中存放的是鍵值對(duì)。[{}, {}]

哈希表的存儲(chǔ)過(guò)程如下:

?①傀履、根據(jù) key 計(jì)算出它的哈希值 h。

?②莉炉、假設(shè)箱子的個(gè)數(shù)為 n钓账，那么這個(gè)鍵值對(duì)應(yīng)該放在第 (h % n) 個(gè)箱子中。

?③絮宁、如果該箱子中已經(jīng)有了鍵值對(duì)梆暮，就使用開放尋址法或者拉鏈法解決沖突。

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

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

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

負(fù)載因子越大忍饰，意味著哈希表越滿贪嫂，越容易導(dǎo)致沖突，性能也就越低艾蓝。因此力崇，一般來(lái)說(shuō)，當(dāng)負(fù)載因子大于某個(gè)常數(shù)（可能是 1赢织，或 0.75 等）時(shí)亮靴，哈希表將自動(dòng)擴(kuò)容。

哈希表在自動(dòng)擴(kuò)容時(shí)于置，一般會(huì)創(chuàng)建兩倍于原來(lái)個(gè)數(shù)的箱子茧吊，因此即使 key 的哈希值不變，對(duì)箱子個(gè)數(shù)取余的結(jié)果也會(huì)發(fā)生改變饱狂，因此所有鍵值對(duì)的存放位置都有可能發(fā)生改變，這個(gè)過(guò)程也稱為重哈希（rehash）雏婶。

哈希表的擴(kuò)容并不總是能夠有效解決負(fù)載因子過(guò)大的問(wèn)題。假設(shè)所有 key 的哈希值都一樣，那么即使擴(kuò)容以后他們的位置也不會(huì)變化参歹。雖然負(fù)載因子會(huì)降低，但實(shí)際存儲(chǔ)在每個(gè)箱子中的鏈表長(zhǎng)度并不發(fā)生改變郎汪，因此也就不能提高哈希表的查詢性能照筑。

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

①趁窃、如果哈希表中本來(lái)箱子就比較多，擴(kuò)容時(shí)需要重新哈希并移動(dòng)數(shù)據(jù)急前，性能影響較大醒陆。

②、如果哈希函數(shù)設(shè)計(jì)不合理裆针，哈希表在極端情況下會(huì)變成線性表刨摩，性能極低。

我們分別通過(guò) Java 和 Redis 的源碼來(lái)理解以上問(wèn)題世吨，并看看他們的解決方案澡刹。

3. Java8 中的哈希表

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

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

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

1. DEFAULT_INITIAL_CAPACITY: 初始容量奏甫，也就是默認(rèn)會(huì)創(chuàng)建 16 個(gè)箱子戈轿，箱子的個(gè)數(shù)不能太多或太少。如果太少阵子，很容易觸發(fā)擴(kuò)容思杯；如果太多，遍歷哈希表會(huì)比較慢挠进。

2. MAXIMUM_CAPACITY: 哈希表最大容量色乾，一般情況下只要內(nèi)存夠用，哈希表不會(huì)出現(xiàn)問(wèn)題领突。

3. DEFAULT_LOAD_FACTOR: 默認(rèn)的負(fù)載因子暖璧。因此初始情況下，當(dāng)鍵值對(duì)的數(shù)量大于 16 * 0.75 = 12 時(shí)君旦，就會(huì)觸發(fā)擴(kuò)容澎办。

4. TREEIFY_THRESHOLD: 上文說(shuō)過(guò)嘲碱，如果哈希函數(shù)不合理，即使擴(kuò)容也無(wú)法減少箱子中鏈表的長(zhǎng)度局蚀，因此 Java 的處理方案是當(dāng)鏈表太長(zhǎng)時(shí)麦锯，轉(zhuǎn)換成紅黑樹。這個(gè)值表示當(dāng)某個(gè)箱子中琅绅，鏈表長(zhǎng)度大于 8 時(shí)扶欣，有可能會(huì)轉(zhuǎn)化成樹。

5. UNTREEIFY_THRESHOLD: 在哈希表擴(kuò)容時(shí)奉件，如果發(fā)現(xiàn)鏈表長(zhǎng)度小于 6宵蛀，則會(huì)由樹重新退化為鏈表。

6. MIN_TREEIFY_CAPACITY: 在轉(zhuǎn)變成樹之前县貌，還會(huì)有一次判斷术陶，只有鍵值對(duì)數(shù)量大于 64 才會(huì)發(fā)生轉(zhuǎn)換。這是為了避免在哈希表建立初期煤痕，多個(gè)鍵值對(duì)恰好被放入了同一個(gè)鏈表中而導(dǎo)致不必要的轉(zhuǎn)化梧宫。

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

泊松分布

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

這就是為什么箱子中鏈表長(zhǎng)度超過(guò) 8 以后要變成紅黑樹巷帝，因?yàn)樵谡Ｇ闆r下出現(xiàn)這種現(xiàn)象的幾率小到忽略不計(jì)忌卤。一旦出現(xiàn)，幾乎可以認(rèn)為是哈希函數(shù)設(shè)計(jì)有問(wèn)題導(dǎo)致的楞泼。

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

4. Redis

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

1、數(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 是用于存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)體。注意到我們定義了一個(gè)長(zhǎng)度為 2 的數(shù)組谨娜，它是為了解決擴(kuò)容時(shí)速度較慢而引入的鹃锈，其原理后面會(huì)詳細(xì)介紹，rehashidx 也是在擴(kuò)容時(shí)需要用到瞧预。先看一下 dictht 的定義：

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

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

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)如下圖所示:

Dict 字典層次結(jié)構(gòu)

2圆丹、添加元素

向字典中添加鍵值對(duì)的底層實(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ù)用來(lái)判斷哈希表是否正在重新哈希。所謂的重新哈希是指在擴(kuò)容時(shí)躯喇，原來(lái)的鍵值對(duì)需要改變位置辫封。為了優(yōu)化重哈希的體驗(yàn)，Redis 每次只會(huì)移動(dòng)一個(gè)箱子中的內(nèi)容廉丽，下一節(jié)會(huì)做詳細(xì)解釋倦微。

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

1. 找到鏈表尾部的時(shí)間復(fù)雜度是 O(n)，或者需要使用額外的內(nèi)存地址來(lái)保存鏈表尾部的位置焦履。頭插法可以節(jié)省插入耗時(shí)拓劝。

2. 對(duì)于一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)來(lái)說(shuō)，最新插入的數(shù)據(jù)往往更有可能頻繁的被獲取嘉裤。頭插法可以節(jié)省查找耗時(shí)郑临。

3、增量式擴(kuò)容

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

為了標(biāo)記哈希表正處于擴(kuò)容階段躺翻，我們?cè)?dict 結(jié)構(gòu)體中使用 rehashidx 來(lái)表示當(dāng)前正在遷移哪個(gè)箱子里的數(shù)據(jù)。由于在結(jié)構(gòu)體中實(shí)際上有兩個(gè)哈希表秋柄，如果添加新的鍵值對(duì)時(shí)哈希表正在擴(kuò)容获枝，我們首先從第一個(gè)哈希表中遷移一個(gè)箱子的數(shù)據(jù)到第二個(gè)哈希表中蠢正，然后鍵值對(duì)會(huì)被插入到第二個(gè)哈希表中骇笔。

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

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

第二句就是用來(lái)選擇插入到哪個(gè)哈希表中嚣崭，第一句話則是遷移 rehashidx 位置上的鏈表笨触。它實(shí)際上會(huì)調(diào)用 dictRehash(d, 1)，也就是說(shuō)是單步長(zhǎng)的遷移雹舀。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;
}

這段代碼比較長(zhǎng)芦劣，但是并不難理解。它由一個(gè) while 循環(huán)和 if 語(yǔ)句組成说榆。在單步遷移的情況下虚吟，最外層的 while 循環(huán)沒(méi)有意義寸认，而它內(nèi)部又可以分為兩個(gè) while 循環(huán)。

第一個(gè)循環(huán)用來(lái)更新 rehashidx 的值串慰，因?yàn)橛行┫渥訛榭掌?rehashidx 并非每次都比原來(lái)前進(jìn)一個(gè)位置，而是有可能前進(jìn)幾個(gè)位置邦鲫，但最多不超過(guò) 10灸叼。第二個(gè)循環(huán)則用來(lái)復(fù)制鏈表數(shù)據(jù)。

最外面的 if 判斷中庆捺，如果發(fā)現(xiàn)舊哈希表已經(jīng)全部完成遷移古今，就會(huì)釋放舊哈希表的內(nèi)存，同時(shí)把新的哈希表賦值給舊的哈希表滔以，最后把 rehashidx 重新設(shè)置為 -1捉腥，表示重哈希過(guò)程結(jié)束。

4醉者、默認(rèn)哈希函數(shù)

與 Java 不同的是但狭，Redis 提供了 void * 類型 key 的哈希函數(shù)，也就是通過(guò)任何類型的 key 的指針都可以求出哈希值撬即。具體算法定義在 dictGenHashFunction 函數(shù)中立磁，由于代碼過(guò)長(zhǎng)，而且都是一些位運(yùn)算剥槐，就不展示了唱歧。

它的實(shí)現(xiàn)原理是根據(jù)指針地址和這一塊內(nèi)存的長(zhǎng)度，獲取內(nèi)存中的值粒竖，并且放入到一個(gè)數(shù)組當(dāng)中颅崩，可見這個(gè)數(shù)組僅由 0 和 1 構(gòu)成。然后再對(duì)這些數(shù)字做哈希運(yùn)算蕊苗。因此即使兩個(gè)指針指向的地址不同沿后，但只要其中內(nèi)容相同，就可以得到相同的哈希值朽砰。

5. 歸納對(duì)比

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

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

Redis 通過(guò)增量式擴(kuò)容解決了這個(gè)缺點(diǎn)造锅，同時(shí)拉鏈法的實(shí)現(xiàn)（放在鏈表頭部）值得我們學(xué)習(xí)撼唾。Redis 還提供了一個(gè)經(jīng)過(guò)嚴(yán)格測(cè)試，表現(xiàn)良好的默認(rèn)哈希函數(shù)哥蔚，避免了鏈表過(guò)長(zhǎng)的問(wèn)題倒谷。

Objective-C 的實(shí)現(xiàn)和 Java 比較類似蛛蒙，當(dāng)我們需要重寫 isEqual() 方法時(shí)，還需要重寫 hash 方法渤愁。這兩種語(yǔ)言并沒(méi)有提供一個(gè)通用的宇驾、默認(rèn)的哈希函數(shù)，主要是考慮到 isEqual() 方法可能會(huì)被重寫猴伶，兩個(gè)內(nèi)存數(shù)據(jù)不同的對(duì)象可能在語(yǔ)義上被認(rèn)為是相同的课舍。如果使用默認(rèn)的哈希函數(shù)就會(huì)得到不同的哈希值，這兩個(gè)對(duì)象就會(huì)同時(shí)被添加到 NSSet 集合中他挎，這可能違背我們的期望結(jié)果筝尾。

根據(jù)我的了解，Redis 并不支持重寫哈希方法办桨，難道 Redis 就沒(méi)有考慮到這個(gè)問(wèn)題么筹淫？實(shí)際上還要從 Redis 的定位說(shuō)起。由于它是一個(gè)高效的呢撞，Key-Value 存儲(chǔ)系統(tǒng)损姜，它的 key 并不會(huì)是一個(gè)對(duì)象，而是一個(gè)用來(lái)唯一確定對(duì)象的標(biāo)記殊霞。

一般情況下摧阅，如果要存儲(chǔ)某個(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 并不存在對(duì)象等同性的考慮拦英，也就可以提供默認(rèn)的哈希函數(shù)了蜒什。

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

沒(méi)有完美的架構(gòu)灾常，只有滿足需求的架構(gòu)。

6. 總結(jié)

回到文章開頭的問(wèn)題中來(lái)做裙，有兩個(gè)字典岗憋，分別存有 100 條數(shù)據(jù)和 10000 條數(shù)據(jù)肃晚，如果用一個(gè)不存在的 key 去查找數(shù)據(jù)锚贱，在哪個(gè)字典中速度更快？

完整的答案是:

在 Redis 中关串，得益于自動(dòng)擴(kuò)容和默認(rèn)哈希函數(shù)拧廊，兩者查找速度一樣快监徘。

在 Java 和 Objective-C 中，如果哈希函數(shù)不合理吧碾，返回值過(guò)于集中凰盔，會(huì)導(dǎo)致大字典更慢。Java 由于存在鏈表和紅黑樹互換機(jī)制倦春，搜索時(shí)間呈對(duì)數(shù)級(jí)增長(zhǎng)户敬，而非線性增長(zhǎng)。在理想的哈希函數(shù)下睁本，無(wú)論字典多大尿庐，搜索速度都是一樣快。

最后呢堰，整理了一下本文提到的知識(shí)點(diǎn)抄瑟，希望大家讀完文章后對(duì)以下問(wèn)題有比較清楚透徹的理解:

1. 哈希表中負(fù)載因子的概念
2. 哈希表擴(kuò)容的過(guò)程，以及對(duì)查找性能的影響
3. 哈希表擴(kuò)容速度的優(yōu)化枉疼，拉鏈法插入新元素的優(yōu)化皮假，鏈表過(guò)長(zhǎng)時(shí)的優(yōu)化
4. 不同語(yǔ)言、使用場(chǎng)景下的取舍

7. 學(xué)習(xí)文章

? OpenJDK Source Release
? HashMap vs Hashtable vs HashSet
? 泊松分布
? Redis Source code
? An introduction to Redis data types and abstractions
? 韋易笑 # 基礎(chǔ)優(yōu)化-讓哈希表更公平一些