dict猎物，又稱字典(dictionary)或映射(map)棍现，是集合的一種；這種集合中每個元素都是KV鍵值對横缔。
字典dict在各編程語言中都有體現(xiàn)铺遂，面向?qū)ο蟮木幊陶Z言如C++、Java中都稱其為Map茎刚。
Redis的KV存儲結(jié)構(gòu)
Redis內(nèi)存數(shù)據(jù)庫襟锐，最底層是一個redisDb;
redisDb 整體使用 dict字典 來存儲鍵值對KV;
字典中的每一項(xiàng)，使用dictEntry 膛锭，代表KV鍵值捌斧；類似于HashMap中的鍵值對Entry。
why dict/map?
dict是一種用于維護(hù)key和value映射關(guān)系的數(shù)據(jù)結(jié)構(gòu)泉沾，與很多編程語言中的Map類似。
為什么dict/map 這么受歡迎呢妇押？
因?yàn)閐ict/map實(shí)現(xiàn)了key和value的映射跷究，通過key查詢value是效率非常高的操作，時間復(fù)雜度是O(C)敲霍，C是常數(shù)俊马，在沒有沖突/碰撞的情況下丁存，可以達(dá)到O(1)。
dict本質(zhì)上是為了解決算法中的查找問題（Searching）柴我，一般查找問題的解法分為兩個大類：一個是基于各種平衡樹解寝，一個是基于哈希表。
- 平衡樹艘儒，如二叉搜索樹聋伦、紅黑樹，使用的是“二分思想”界睁；
如果需要實(shí)現(xiàn)排序觉增，則可使用平衡樹，如:用大頂堆實(shí)現(xiàn)TreeMap翻斟； - 哈希表逾礁，如Java中的Map，Python中的字典dict访惜，使用的是“映射思想”嘹履；
我們平常使用的各種Map或dict，大都是基于哈希表實(shí)現(xiàn)的债热。在不要求數(shù)據(jù)有序存儲砾嫉，且能保持較低的哈希值沖突概率的前提下，基于哈希表的查找性能能做到非常高效阳柔，接近O(1)焰枢，而且容易實(shí)現(xiàn)。
Redis dict的應(yīng)用
字典dict 在 Redis 中的應(yīng)用廣泛舌剂， 使用頻率可以說和 SDS 以及雙端鏈表不相上下济锄， 基本上各個功能模塊都有用到字典的地方。
其中霍转， 字典dict的主要用途有以下兩個：
- 實(shí)現(xiàn)數(shù)據(jù)庫鍵空間（key space）荐绝；
- 用作 hash 鍵的底層實(shí)現(xiàn)之一；
以下兩個小節(jié)分別介紹這兩種用途避消。
Redis數(shù)據(jù)庫鍵空間（key space）
Redis 是一個鍵值對數(shù)據(jù)庫服務(wù)器低滩，服務(wù)器中每個數(shù)據(jù)庫都由 redisDB 結(jié)構(gòu)表示（默認(rèn)16個庫）。其中岩喷，redisDB 結(jié)構(gòu)的 dict 字典保存了數(shù)據(jù)庫中所有的鍵值對恕沫，這個字典被稱為鍵空間（key space）。
可以認(rèn)為纱意，Redis默認(rèn)16個庫婶溯，這16個庫在各自的鍵空間（key space）中；其實(shí)就通過鍵空間（key space）實(shí)現(xiàn)了隔離。而鍵空間（key space）底層是dict實(shí)現(xiàn)的迄委。
鍵空間（key space）除了實(shí)現(xiàn)了16個庫的隔離褐筛，還能基于鍵空間通知(Keyspace Notifications) 實(shí)現(xiàn)某些事件的訂閱通知，如某個key過期的時間叙身，某個key的value變更事件渔扎。
鍵空間通知(Keyspace Notifications)，是因?yàn)殒I空間（key space）實(shí)現(xiàn)了16個庫的隔離信轿，而我們執(zhí)行Redis命令最終都是落在其中一個庫上晃痴，當(dāng)有事件發(fā)生在某個庫上時，該庫對應(yīng)的鍵空間（key space）就能基于pub/sub發(fā)布訂閱虏两，實(shí)現(xiàn)事件“廣播”愧旦。
鍵空間（key space），詳細(xì)分析定罢，可參見：Redis鍵空間通知(Keyspace Notifications)
dict 用作 hash 鍵的底層實(shí)現(xiàn)
Redis 的 hash 鍵使用以下兩種數(shù)據(jù)結(jié)構(gòu)作為底層實(shí)現(xiàn):
- 壓縮列表ziplist 笤虫；
- 字典dict；
因?yàn)閴嚎s列表 比字典更節(jié)省內(nèi)存祖凫，所以程序在創(chuàng)建新 Hash 鍵時琼蚯，默認(rèn)使用壓縮列表作為底層實(shí)現(xiàn)， 當(dāng)有需要時惠况，才會將底層實(shí)現(xiàn)從壓縮列表轉(zhuǎn)換到字典遭庶。
ziplist 是為 Redis 節(jié)約內(nèi)存而開發(fā)的、非常節(jié)省內(nèi)存的雙向鏈表稠屠，深入學(xué)習(xí)可移步Redis的list
壓縮鏈表轉(zhuǎn)成字典(ziplist->dict)的條件
同時滿足以下兩個條件峦睡，hash 鍵才會使用ziplist：
1、key和value 長度都小于64
2权埠、鍵值對數(shù)小于512
該配置 在redis.conf
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
如何實(shí)現(xiàn)字典dict/映射
dict榨了，又稱字典(dictionary)或映射(map)，是集合的一種攘蔽；這種集合中每個元素都是KV鍵值對龙屉。
它是根據(jù)關(guān)鍵字值（key）而直接進(jìn)行訪問KV鍵值對的數(shù)據(jù)結(jié)構(gòu)。也就是說满俗，它通過把關(guān)鍵字值映射到一個位置來訪問記錄转捕，以加快查找的速度。這個映射函數(shù)稱為哈希函數(shù)（也稱為散列函數(shù)）唆垃。
因此通常我們稱字典dict五芝，也叫哈希表。
映射過程辕万，通常使用hash算法實(shí)現(xiàn)与柑，因此也稱映射過程為哈习迹化，存放記錄的數(shù)組叫做散列表价捧、或hash表。
哈衔写粒化之后難免會產(chǎn)生一個問題结蟋，那就是對不同的關(guān)鍵字，可能得到同一個散列地址渔彰，即不同的key散列到同一個數(shù)組下標(biāo)嵌屎，這種現(xiàn)象稱為沖突，那么我們該如何去處理沖突呢恍涂？
最常用的就是鏈地址法宝惰，也常被稱為拉鏈法，就是在沖突的下標(biāo)處再沧，維護(hù)一個鏈表尼夺，所有映射到該下標(biāo)的記錄，都添加到該鏈表上炒瘸。
Redis字典dict如何實(shí)現(xiàn)的淤堵？
Redis字典dict，也是采用哈希表顷扩，本質(zhì)就是數(shù)組+鏈表拐邪。
也是眾多編程語言實(shí)現(xiàn)Map的首選方式，如Java中的HashMap隘截。
Redis字典dict 的底層實(shí)現(xiàn)扎阶，其實(shí)和Java中的ConcurrentHashMap思想非常相似。
就是用數(shù)組+鏈表實(shí)現(xiàn)了分布式哈希表婶芭。當(dāng)不同的關(guān)鍵字东臀、散列到數(shù)組相同的位置，就拉鏈雕擂，用鏈表維護(hù)沖突的記錄啡邑。當(dāng)沖突記錄越來越多、鏈表越來越長井赌，遍歷列表的效率就會降低谤逼，此時需要考慮將鏈表的長度變短。
將鏈表的長度變短仇穗，一個最直接有效的方式就是擴(kuò)容數(shù)組流部。將數(shù)組+鏈表結(jié)構(gòu)中的數(shù)組擴(kuò)容，數(shù)組變長纹坐、對應(yīng)數(shù)組下標(biāo)就增多了枝冀；將原數(shù)組中所有非空的索引下標(biāo)、搬運(yùn)到擴(kuò)容后的新數(shù)組，經(jīng)過重新散列果漾，自然就把沖突的鏈表變短了球切。
如果你對Java的HashMap或ConcurrentHashMap 底層實(shí)現(xiàn)原理比較了解，那么對Redis字典dict的底層實(shí)現(xiàn)绒障，也能很快上手吨凑。
dict.h 給出了這個字典dict的定義：
/*
* 字典
*
* 每個字典使用兩個哈希表，用于實(shí)現(xiàn)漸進(jìn)式 rehash
*/
typedef struct dict {
// 特定于類型的處理函數(shù)
dictType *type;
// 類型處理函數(shù)的私有數(shù)據(jù)
void *privdata;
// 哈希表（2 個）
dictht ht[2];
// 記錄 rehash 進(jìn)度的標(biāo)志户辱，值為 -1 表示 rehash 未進(jìn)行
int rehashidx;
// 當(dāng)前正在運(yùn)作的安全迭代器數(shù)量
int iterators;
} dict;
typedef struct dictType {
unsigned int (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;
結(jié)合上面的代碼鸵钝，可以很清楚地看出dict的結(jié)構(gòu)。一個dict由如下若干項(xiàng)組成：
-
dictType *type;一個指向dictType結(jié)構(gòu)的指針（type）庐镐。它通過自定義的方式使得dict的key和value能夠存儲任何類型的數(shù)據(jù)恩商。 -
void *privdata;一個私有數(shù)據(jù)指針（privdata）。由調(diào)用者在創(chuàng)建dict的時候傳進(jìn)來必逆。 -
dictht ht[2];兩個哈希表（ht[2]）怠堪。只有在rehash的過程中，ht[0]和ht[1]才都有效末患。而在平常情況下研叫，只有ht[0]有效，ht[1]里面沒有任何數(shù)據(jù)璧针。上圖表示的就是rehash進(jìn)行到中間某一步時的情況嚷炉。 -
int rehashidx;當(dāng)前rehash索引（rehashidx）。如果rehashidx = -1探橱，表示當(dāng)前沒有在rehash過程中申屹；否則，表示當(dāng)前正在進(jìn)行rehash隧膏，且它的值記錄了當(dāng)前rehash進(jìn)行到哪一步了哗讥。 -
int iterators;當(dāng)前正在進(jìn)行遍歷的iterator的個數(shù)。這不是我們現(xiàn)在討論的重點(diǎn)胞枕，暫時忽略杆煞。
dictType結(jié)構(gòu)包含若干函數(shù)指針，用于dict的調(diào)用者對涉及key和value的各種操作進(jìn)行自定義腐泻。這些操作包含：
- hashFunction决乎，對key進(jìn)行哈希值計算的哈希算法。
- keyDup和valDup派桩，分別定義key和value的拷貝函數(shù)构诚，用于在需要的時候?qū)ey和value進(jìn)行深拷貝，而不僅僅是傳遞對象指針铆惑。
- keyCompare范嘱，定義兩個key的比較操作送膳，在根據(jù)key進(jìn)行查找時會用到。
- keyDestructor和valDestructor丑蛤，分別定義對key和value的析構(gòu)函數(shù)叠聋。
私有數(shù)據(jù)指針（privdata）就是在dictType的某些操作被調(diào)用時會傳回給調(diào)用者。
dictht(dict hash table)哈希表
dictht 是字典 dict 哈希表的縮寫盏阶，即dict hash table晒奕。
dict.h/dictht 類型定義：
/*
* 哈希表
*/
typedef struct dictht {
// 哈希表節(jié)點(diǎn)指針數(shù)組（俗稱桶，bucket）
dictEntry **table;
// 指針數(shù)組的大小
unsigned long size;
// 指針數(shù)組的長度掩碼名斟，用于計算索引值
unsigned long sizemask;
// 哈希表現(xiàn)有的節(jié)點(diǎn)數(shù)量
unsigned long used;
} dictht;
/*
* 哈希表節(jié)點(diǎn)
*/
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 鏈往后繼節(jié)點(diǎn)
struct dictEntry *next;
} dictEntry;
dictht 定義一個哈希表的結(jié)構(gòu)，包括以下部分：
- 一個dictEntry指針數(shù)組（table）魄眉。key的哈希值最終映射到這個數(shù)組的某個位置上（對應(yīng)一個bucket）砰盐。如果多個key映射到同一個位置，就發(fā)生了沖突坑律，那么就拉出一個dictEntry鏈表岩梳。
- size：標(biāo)識dictEntry指針數(shù)組的長度。它總是2的指數(shù)次冪晃择。
- sizemask：用于將哈希值映射到table的位置索引冀值。它的值等于(size-1)，比如7, 15, 31, 63宫屠，等等列疗，也就是用二進(jìn)制表示的各個bit全1的數(shù)字。每個key先經(jīng)過hashFunction計算得到一個哈希值浪蹂，然后計算(哈希值 & sizemask)得到在table上的位置抵栈。相當(dāng)于計算取余(哈希值 % size)。
- used：記錄dict中現(xiàn)有的數(shù)據(jù)個數(shù)坤次。它與size的比值就是裝載因子古劲。這個比值越大，哈希值沖突概率越高缰猴。
Redis dictht的負(fù)載因子
我們知道當(dāng)HashMap中由于Hash沖突（負(fù)載因子）超過某個閾值時产艾，出于鏈表性能的考慮、會進(jìn)行擴(kuò)容滑绒，Redis dict也是一樣闷堡。
一個dictht 哈希表里，核心就是一個dictEntry數(shù)組蹬挤，同時用size記錄了數(shù)組大小缚窿，用used記錄了所有記錄數(shù)。
dictht的負(fù)載因子焰扳，就是used與size的比值倦零，也稱裝載因子（load factor）误续。這個比值越大，哈希值沖突概率越高扫茅。當(dāng)比值[默認(rèn)]超過5蹋嵌，會強(qiáng)制進(jìn)行rehash。
dictEntry結(jié)構(gòu)中包含k, v和指向鏈表下一項(xiàng)的next指針葫隙。k是void指針栽烂，這意味著它可以指向任何類型。v是個union恋脚，當(dāng)它的值是uint64_t腺办、int64_t或double類型時，就不再需要額外的存儲糟描，這有利于減少內(nèi)存碎片怀喉。當(dāng)然，v也可以是void指針船响，以便能存儲任何類型的數(shù)據(jù)躬拢。
next 指向另一個 dictEntry 結(jié)構(gòu)， 多個 dictEntry 可以通過 next 指針串連成鏈表见间， 從這里可以看出聊闯， dictht 使用鏈地址法來處理鍵碰撞： 當(dāng)多個不同的鍵擁有相同的哈希值時，哈希表用一個鏈表將這些鍵連接起來米诉。
下圖展示了一個由 dictht 和數(shù)個 dictEntry 組成的哈希表例子：
如果再加上之前列出的 dict 類型菱蔬，那么整個字典結(jié)構(gòu)可以表示如下：
在上圖給出的示例中， 只使用了 0 號哈希表ht[0]荒辕，且rehashidx=-1表明字典未進(jìn)行 rehash汗销。
什么是rehash，下文會詳細(xì)展開抵窒。
Redis dict使用的哈希算法
前面提到弛针，一個kv鍵值對，添加到哈希表時李皇，需要用一個映射函數(shù)將key散列到一個具體的數(shù)組下標(biāo)削茁。
Redis 目前使用兩種不同的哈希算法：
1、MurmurHash2
是種32 bit 算法：這種算法的分布率和速度都非常好掉房；Murmur哈希算法最大的特點(diǎn)是碰撞率低茧跋，計算速度快。Google的Guava庫包含最新的Murmur3卓囚。
具體信息請參考 MurmurHash 的主頁： http://code.google.com/p/smhasher/ 瘾杭。
2、基于 djb 算法實(shí)現(xiàn)的一個大小寫無關(guān)散列算法：具體信息請參考 http://www.cse.yorku.ca/~oz/hash.html 哪亿。
使用哪種算法取決于具體應(yīng)用所處理的數(shù)據(jù)：
- 命令表以及 Lua 腳本緩存都用到了算法 2 粥烁。
- 算法 1 的應(yīng)用則更加廣泛：數(shù)據(jù)庫贤笆、集群、哈希鍵讨阻、阻塞操作等功能都用到了這個算法芥永。
Redis dict各種操作
以下是用于處理 dict 的各種 API ， 它們的作用及相應(yīng)的算法復(fù)雜度：
| 操作 | 函數(shù) | 算法復(fù)雜度 |
|---|---|---|
| 創(chuàng)建一個新字典 | dictCreate | O(1) |
| 添加新鍵值對到字典 | dictAdd | O(1) |
| 添加或更新給定鍵的值 | dictReplace | O(1) |
| 在字典中查找給定鍵所在的節(jié)點(diǎn) | dictFind | O(1) |
| 在字典中查找給定鍵的值 | dictFetchValue | O(1) |
| 從字典中隨機(jī)返回一個節(jié)點(diǎn) | dictGetRandomKey | O(1) |
| 根據(jù)給定鍵钝吮，刪除字典中的鍵值對 | dictDelete | O(1) |
| 清空并釋放字典 | dictRelease | O(N) |
| 清空并重置（但不釋放）字典 | dictEmpty | O(N) |
| 縮小字典 | dictResize | O(N) |
| 擴(kuò)大字典 | dictExpand | O(N) |
| 對字典進(jìn)行給定步數(shù)的 rehash | dictRehash | O(N) |
| 在給定毫秒內(nèi)埋涧，對字典進(jìn)行rehash | dictRehashMilliseconds | O(N) |
下面，會對一些關(guān)鍵步驟進(jìn)行詳細(xì)講解奇瘦。
dict的創(chuàng)建（dictCreate）
創(chuàng)建dict
dict *d = dictCreate(&hash_type, NULL);
dict *dictCreate(dictType *type,
void *privDataPtr)
{
dict *d = zmalloc(sizeof(*d));
_dictInit(d,type,privDataPtr);
return d;
}
int _dictInit(dict *d, dictType *type,
void *privDataPtr)
{
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
d->type = type;
d->privdata = privDataPtr;
d->rehashidx = -1;
d->iterators = 0;
return DICT_OK;
}
static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}
dictCreate為dict的數(shù)據(jù)結(jié)構(gòu)分配空間并為各個變量賦初值棘催。其中兩個哈希表ht[0]和ht[1]起始都沒有分配空間，table指針都賦為NULL耳标。這意味著要等第一個數(shù)據(jù)插入時才會真正分配空間巧鸭。
- ht[0]->table 的空間分配將在第一次往字典添加鍵值對時進(jìn)行；
- ht[1]->table 的空間分配將在 rehash 開始時進(jìn)行麻捻；
添加新鍵值對到字典(dictAdd)
根據(jù)字典所處的狀態(tài)， 將給定的鍵值對添加到字典可能會引起一系列復(fù)雜的操作：
- 如果字典為未初始化（即字典的 0 號哈希表的 table 屬性為空）呀袱，則程序需要對 0 號哈希表進(jìn)行初始化贸毕；
- 如果在插入時發(fā)生了鍵碰撞，則程序需要處理碰撞夜赵；
- 如果插入新元素明棍，使得字典滿足了 rehash 條件，則需要啟動相應(yīng)的 rehash 程序寇僧；
當(dāng)程序處理完以上三種情況之后摊腋，新的鍵值對才會被真正地添加到字典上。
dictAdd函數(shù)是調(diào)用 dictAddRaw實(shí)現(xiàn)的：
/* 將Key插入哈希表 */
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d); // 如果哈希表在rehashing嘁傀，則執(zhí)行單步rehash
/* 調(diào)用_dictKeyIndex() 檢查鍵是否存在兴蒸，如果存在則返回NULL */
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry)); // 為新增的節(jié)點(diǎn)分配內(nèi)存
entry->next = ht->table[index]; // 將節(jié)點(diǎn)插入鏈表表頭
ht->table[index] = entry; // 更新節(jié)點(diǎn)和桶信息
ht->used++; // 更新ht
/* 設(shè)置新節(jié)點(diǎn)的鍵 */
dictSetKey(d, entry, key);
return entry;
}
整個添加流程可以用下圖表示：
在接下來的三節(jié)中， 我們將分別看到细办，添加操作如何在以下三種情況中執(zhí)行：
1橙凳、字典為空；
2笑撞、添加新鍵值對時發(fā)生碰撞處理岛啸；
3、添加新鍵值對時觸發(fā)了 rehash 操作茴肥；
添加新元素時table為空
當(dāng)?shù)谝淮瓮兆值淅锾砑渔I值對時坚踩， 程序會根據(jù) dict.h/DICT_HT_INITIAL_SIZE 里指定的大小為 d->ht[0]->table 分配空間 （在目前的版本中， DICT_HT_INITIAL_SIZE 的值為 4 ）瓤狐。
以下是字典空白時的樣子：
以下是往空白字典添加了第一個鍵值對之后的樣子：
添加新鍵值對時發(fā)生碰撞
在哈希表實(shí)現(xiàn)中瞬铸， 當(dāng)兩個不同的鍵擁有相同的哈希值時批幌， 稱這兩個鍵發(fā)生碰撞（collision）， 而哈希表實(shí)現(xiàn)必須想辦法對碰撞進(jìn)行處理赴捞。
字典哈希表所使用的碰撞解決方法被稱之為鏈地址法： 這種方法使用鏈表將多個哈希值相同的節(jié)點(diǎn)串連在一起逼裆， 從而解決沖突問題。
假設(shè)現(xiàn)在有一個帶有三個節(jié)點(diǎn)的哈希表赦政，如下圖：
對于一個新的鍵值對 key4 和 value4 胜宇， 如果 key4 的哈希值和 key1 的哈希值相同， 那么它們將在哈希表的 0 號索引上發(fā)生碰撞恢着。
通過將 key4-value4 和 key1-value1 兩個鍵值對用鏈表連接起來桐愉， 就可以解決碰撞的問題：
添加新鍵值對時觸發(fā)了 rehash
對于使用鏈地址法來解決碰撞問題的哈希表 dictht 來說， 哈希表的性能取決于大嘘伞（size屬性）與保存節(jié)點(diǎn)數(shù)量（used屬性）之間的比率：
哈希表的大小與節(jié)點(diǎn)數(shù)量从诲，比率在 1:1 時，哈希表的性能最好靡羡；
如果節(jié)點(diǎn)數(shù)量比哈希表的大小要大很多的話系洛，那么哈希表就會退化成多個鏈表，哈希表本身的性能優(yōu)勢便不復(fù)存在略步；
舉個例子描扯， 下面這個哈希表， 平均每次失敗查找只需要訪問 1 個節(jié)點(diǎn)（非空節(jié)點(diǎn)訪問 2 次趟薄，空節(jié)點(diǎn)訪問 1 次）：
而下面這個哈希表绽诚， 平均每次失敗查找需要訪問 5 個節(jié)點(diǎn)：
為了在字典的鍵值對不斷增多的情況下保持良好的性能， 字典需要對所使用的哈希表（ht[0]）進(jìn)行 rehash 操作： 在不修改任何鍵值對的情況下杭煎，對哈希表進(jìn)行擴(kuò)容恩够， 盡量將比率維持在 1:1 左右。
dictAdd 在每次向字典添加新鍵值對之前羡铲， 都會對哈希表 ht[0] 進(jìn)行檢查蜂桶， 對于 ht[0] 的 size 和 used 屬性， 如果它們之間的比率 ratio = used / size 滿足以下任何一個條件的話犀勒，rehash 過程就會被觸發(fā)：
- 自然 rehash ： ratio >= 1 屎飘，且變量 dict_can_resize 為true。
- 強(qiáng)制 rehash ： ratio 大于變量 dict_force_resize_ratio （目前版本中贾费， dict_force_resize_ratio 的值為 5 ）钦购。
什么時候 dict_can_resize 會為false？
在前面介紹字典的應(yīng)用時也說到過褂萧， 數(shù)據(jù)庫就是字典押桃， 數(shù)據(jù)庫里的哈希類型鍵也是字典， 當(dāng) Redis 使用子進(jìn)程對數(shù)據(jù)庫執(zhí)行后臺持久化任務(wù)時（比如執(zhí)行 BGSAVE 或 BGREWRITEAOF 時）导犹， 為了最大化地利用系統(tǒng)的 copy on write 機(jī)制唱凯， 程序會暫時將 dict_can_resize 設(shè)為false羡忘， 避免執(zhí)行自然 rehash ， 從而減少程序?qū)?nèi)存的觸碰（touch）磕昼。當(dāng)持久化任務(wù)完成之后卷雕， dict_can_resize 會重新被設(shè)為true。
另一方面票从， 當(dāng)字典滿足了強(qiáng)制 rehash 的條件時漫雕， 即使 dict_can_resize 不為true（有 BGSAVE 或 BGREWRITEAOF 正在執(zhí)行）， 這個字典一樣會被 rehash 峰鄙。
Rehash 執(zhí)行過程
字典的 rehash 操作實(shí)際上就是執(zhí)行以下任務(wù)：
1浸间、創(chuàng)建一個比 ht[0]->table 更大的 ht[1]->table ；
2吟榴、將 ht[0]->table 中的所有鍵值對遷移到 ht[1]->table 魁蒜；
3、將原有 ht[0] 的數(shù)據(jù)清空吩翻，并將 ht[1] 替換為新的 ht[0] 兜看；
經(jīng)過以上步驟之后， 程序就在不改變原有鍵值對數(shù)據(jù)的基礎(chǔ)上狭瞎， 增大了哈希表的大小铣减。
dict的rehash 本質(zhì)就是擴(kuò)容，就是將數(shù)組+鏈表結(jié)構(gòu)中的數(shù)組擴(kuò)容脚作；
這個過程，需要開辟一個更大空間的數(shù)組缔刹，將老數(shù)組中每個非空索引的bucket球涛，搬運(yùn)到新數(shù)組；搬運(yùn)完成后再釋放老數(shù)組的空間校镐。
作為例子亿扁， 以下四個小節(jié)展示了一次對哈希表進(jìn)行 rehash 的完整過程。
1. 開始 rehash
這個階段有兩個事情要做：
- 設(shè)置字典的 rehashidx 為 0 鸟廓，標(biāo)識著 rehash 的開始从祝；
- 為 ht[1]->table 分配空間，大小至少為 ht[0]->used 的兩倍引谜；
這時的字典是這個樣子：
2. Rehash 進(jìn)行中
在這個階段牍陌， ht[0]->table 的節(jié)點(diǎn)會被逐漸遷移到 ht[1]->table ， 因?yàn)?rehash 是分多次進(jìn)行的（細(xì)節(jié)在下一節(jié)解釋）员咽， 字典的 rehashidx 變量會記錄 rehash 進(jìn)行到 ht[0] 的哪個索引位置上毒涧。
注意除了節(jié)點(diǎn)的移動外， 字典的 rehashidx 贝室、 ht[0]->used 和 ht[1]->used 三個屬性也產(chǎn)生了變化契讲。
3. 節(jié)點(diǎn)遷移完畢
到了這個階段仿吞，所有的節(jié)點(diǎn)都已經(jīng)從 ht[0] 遷移到 ht[1] 了：
4. Rehash 完畢
在 rehash 的最后階段，程序會執(zhí)行以下工作：
- 釋放 ht[0] 的空間捡偏；
- 用 ht[1] 來代替 ht[0] 唤冈，使原來的 ht[1] 成為新的 ht[0] ；
- 創(chuàng)建一個新的空哈希表银伟，并將它設(shè)置為 ht[1] 你虹；
- 將字典的 rehashidx 屬性設(shè)置為 -1 ，標(biāo)識 rehash 已停止枣申；
以下是字典 rehash 完畢之后的樣子：
incremental rehashing 增量/漸進(jìn)式rehash
在上一節(jié)售葡，我們了解了字典的 rehash 過程， 需要特別指出的是忠藤， rehash 并不是在觸發(fā)之后挟伙，馬上就執(zhí)行直到完成； 而是分多次模孩、漸進(jìn)式地完成的尖阔。
rehash會產(chǎn)生的問題
1、rehash的過程榨咐，會使用兩個哈希表介却，創(chuàng)建了一個更大空間的ht[1]，此時會造成內(nèi)存陡增块茁；
2齿坷、rehash的過程，可能涉及大量KV鍵值對dictEntry的搬運(yùn)数焊，耗時較長永淌；
如果這個 rehash 過程必須將所有鍵值對遷移完畢之后才將結(jié)果返回給用戶， 這樣的處理方式將不滿足Redis高效響應(yīng)的特性佩耳。
rehash會產(chǎn)生的問題遂蛀，主要層面就是內(nèi)存占用陡增、和處理耗時長的問題干厚，基于這兩點(diǎn)李滴，還會帶來其他影響。
為了解決這些問題蛮瞄， Redis 使用了incremental rehashing所坯，是一種 增量/漸進(jìn)式的 rehash 方式： 通過將 rehash 分散到多個步驟中進(jìn)行， 從而避免了集中式的計算/節(jié)點(diǎn)遷移挂捅。
dictAdd 添加鍵值對到dict包竹，檢查到需要進(jìn)行rehash時，會將dict.rehashidx 設(shè)置為 0 ，標(biāo)識著 rehash 的開始周瞎；
后續(xù)請求苗缩，在執(zhí)行add、delete声诸、find操作時酱讶，都會判斷dict是否正在rehash，如果是彼乌，就執(zhí)行_dictRehashStep()函數(shù)泻肯，進(jìn)行增量rehash。
每次執(zhí)行 _dictRehashStep 慰照， 會將ht[0]->table 哈希表第一個不為空的索引上的所有節(jié)點(diǎn)就會全部遷移到 ht[1]->table 灶挟。
也就是在某次dictAdd 添加鍵值對時，觸發(fā)了rehash；后續(xù)add、delete揩徊、find命令在執(zhí)行前都會檢查走芋，如果dict正在rehash齿梁，就先不急去執(zhí)行自己的命令，先去幫忙搬運(yùn)一個bucket；
搬運(yùn)完一個bucket，再執(zhí)行add抬伺、delete、find命令 原有處理邏輯灾梦。
ps:實(shí)際上incremental rehashing增量/漸進(jìn)式rehash峡钓，只解決了第二個:耗時長的問題，將集中式的節(jié)點(diǎn)遷移分?jǐn)偟蕉嗖竭M(jìn)行若河，ht[1]占用的雙倍多內(nèi)存椒楣，還一直占用。
下面我們通過dict的查找（dictFind）來看漸進(jìn)式rehash過程牡肉；
dict的查找（dictFind）
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
unsigned int h, idx, table;
if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
if (dictIsRehashing(d)) _dictRehashStep(d);// 如果哈希表在rehashing，則執(zhí)行單步rehash
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
上述dictFind的源碼淆九，根據(jù)dict當(dāng)前是否正在rehash统锤，依次做了這么幾件事：
- 如果當(dāng)前正在進(jìn)行rehash，那么將rehash過程向前推進(jìn)一步（即調(diào)用_dictRehashStep）炭庙。實(shí)際上饲窿，除了查找，插入和刪除也都會觸發(fā)這一動作焕蹄。這就將rehash過程分散到各個查找逾雄、插入和刪除操作中去了，而不是集中在某一個操作中一次性做完。
- 計算key的哈希值（調(diào)用dictHashKey鸦泳，里面的實(shí)現(xiàn)會調(diào)用前面提到的hashFunction）银锻。
- 先在第一個哈希表ht[0]上進(jìn)行查找。在table數(shù)組上定位到哈希值對應(yīng)的位置（如前所述做鹰，通過哈希值與sizemask進(jìn)行按位與）击纬，然后在對應(yīng)的dictEntry鏈表上進(jìn)行查找。查找的時候需要對key進(jìn)行比較钾麸，這時候調(diào)用dictCompareKeys更振，它里面的實(shí)現(xiàn)會調(diào)用到前面提到的keyCompare。如果找到就返回該項(xiàng)饭尝。否則肯腕，進(jìn)行下一步。
- 判斷當(dāng)前是否在rehash钥平，如果沒有实撒，那么在ht[0]上的查找結(jié)果就是最終結(jié)果（沒找到，返回NULL）帖池。否則奈惑，在ht[1]上進(jìn)行查找（過程與上一步相同）。
下面我們有必要看一下增量式rehash的_dictRehashStep的實(shí)現(xiàn)睡汹。
static void _dictRehashStep(dict *d) {
if (d->iterators == 0) dictRehash(d,1);
}
/*
* Note that a rehashing step consists in moving a bucket (that may have more
* than one key as we use chaining) from the old to the new hash table, however
* since part of the hash table may be composed of empty spaces, it is not
* guaranteed that this function will rehash even a single bucket, since it
* will visit at max N*10 empty buckets in total, otherwise the amount of
* work it does would be unbound and the function may block for a long time.
*/
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
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;
}
/* More to rehash... */
return 1;
}
根據(jù)dictRehash函數(shù)的注釋肴甸，rehash的單位是bucket，也就是從老哈希表dictht中找到第一個非空的下標(biāo)囚巴，要把該下標(biāo)整個鏈表搬運(yùn)到新數(shù)組原在。
如果遍歷老數(shù)組，訪問的 前N*10 個都是空bucket彤叉，則不再繼續(xù)往下尋找庶柿。
dictAdd、dictDelete秽浇、dictFind在rehash過程中的特殊性
在哈希表進(jìn)行 rehash 時浮庐， 字典還會采取一些特別的措施， 確保 rehash 順利柬焕、正確地進(jìn)行：
- 因?yàn)樵?rehash 時审残，字典會同時使用兩個哈希表，所以在這期間的所有查找dictFind斑举、刪除dictDelete等操作搅轿，除了在 ht[0] 上進(jìn)行，還需要在 ht[1] 上進(jìn)行富玷。
- 在執(zhí)行添加操作dictAdd時璧坟，新的節(jié)點(diǎn)會直接添加到 ht[1] 而不是 ht[0] 既穆，這樣保證 ht[0] 的節(jié)點(diǎn)數(shù)量在整個 rehash 過程中都只減不增。
dict的縮容
上面關(guān)于 rehash 的章節(jié)描述了通過 rehash 對字典進(jìn)行擴(kuò)展（expand）的情況雀鹃， 如果哈希表的可用節(jié)點(diǎn)數(shù)比已用節(jié)點(diǎn)數(shù)大很多的話幻工， 那么也可以通過對哈希表進(jìn)行 rehash 來收縮（shrink）字典。
收縮 rehash 和上面展示的擴(kuò)展 rehash 的操作幾乎一樣褐澎，執(zhí)行以下步驟：
- 創(chuàng)建一個比 ht[0]->table 小的 ht[1]->table 会钝；
- 將 ht[0]->table 中的所有鍵值對遷移到 ht[1]->table ；
- 將原有 ht[0] 的數(shù)據(jù)清空工三，并將 ht[1] 替換為新的 ht[0] 迁酸；
小結(jié)
Redis的dict最顯著的一個特點(diǎn)，就在于它的rehash俭正。它采用了一種稱為增量式（incremental rehashing）的rehash方法奸鬓，在需要擴(kuò)容時避免一次性對所有key進(jìn)行rehash，而是將rehash操作分散到對于dict的各個增刪改查的操作中去掸读。
這種方法能做到每次只對一小部分key進(jìn)行rehash串远，而每次rehash之間不影響dict的操作。dict之所以這樣設(shè)計儿惫，是為了避免rehash期間單個請求的響應(yīng)時間劇烈增加澡罚，這與前面提到的“快速響應(yīng)時間”的設(shè)計原則是相符的。
- Redis的dict也是使用數(shù)組+鏈表實(shí)現(xiàn)肾请；
- 當(dāng)沖突增加留搔、鏈表增長，也是采用rehash(數(shù)組擴(kuò)容)來將鏈表變短铛铁；
- dict數(shù)組擴(kuò)容隔显，也是按2的指數(shù)次冪，使用位運(yùn)算饵逐，替代求余操作括眠，計算更快；
- 漸進(jìn)式rehash倍权，其實(shí)是輔助式的掷豺；不是讓觸發(fā)rehash的一個人搬運(yùn)完所有dictEntry，而是讓后來者一起參與搬運(yùn)薄声。
福利：關(guān)注公眾號当船，回復(fù)“Redis源碼”，即可獲得 Redis 3.0源碼注釋版~
本文首發(fā)于公眾號 架構(gòu)道與術(shù)(ToBeArchitecturer)奸柬，歡迎關(guān)注、學(xué)習(xí)更多干貨~
