引入字典

從本文開(kāi)始慢慢揭開(kāi)Redis字典的神秘面紗钠怯，字典又稱(chēng)為散列表玻驻，用來(lái)存儲(chǔ)鍵值對(duì)的一種數(shù)據(jù)結(jié)構(gòu)供常，在很多高級(jí)語(yǔ)言中都有實(shí)現(xiàn)摊聋，比如PHP的數(shù)組，Redis的整個(gè)數(shù)據(jù)庫(kù)都是用字典來(lái)進(jìn)行存儲(chǔ)的栈暇，對(duì)Redis數(shù)據(jù)庫(kù)的CURD操作麻裁，實(shí)際就是對(duì)字典中的數(shù)據(jù)進(jìn)行CURD。
由此可以得出字典的特征

1). 可以存儲(chǔ)海量數(shù)據(jù)源祈，KV對(duì)是映射關(guān)系煎源，可以根據(jù)鍵以O(shè)(1)的時(shí)間復(fù)雜度讀取或者插入KV對(duì)。
2). KV對(duì)的鍵的類(lèi)型可以是字符串香缺，整型等手销，且唯一。
3). KV對(duì)中值的類(lèi)型可以是String图张，Hash锋拖，List诈悍，Set，SortedSet兽埃。

哈希表介紹

Redis 本質(zhì)上就是在字典上面掛載著各種數(shù)據(jù)結(jié)構(gòu)侥钳，我們先來(lái)看看 字典 這種數(shù)據(jù)結(jié)構(gòu)。Redis中的 字典 其實(shí)是就是 哈希表（HashTable）讲仰，我們來(lái)看看 哈希表 的定義：

哈希表（HashTable）是根據(jù)鍵值(Key)直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)慕趴。也就是說(shuō)，它通過(guò)把鍵值映射到哈希表
中一個(gè)位置來(lái)訪問(wèn)記錄鄙陡，以加快查找的速度冕房。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表趁矾。

參考:數(shù)據(jù)結(jié)構(gòu)與算法（11）：哈希表

Redis字典介紹

Redis的字典也是通過(guò)哈希表設(shè)計(jì)來(lái)實(shí)現(xiàn)的耙册。當(dāng)然在通用性和性能上面考慮并優(yōu)化了一些。接下來(lái)讓我們來(lái)看下Redis字典的具體實(shí)現(xiàn)毫捣。

首先讓我們來(lái)看看在Redis中字典數(shù)據(jù)結(jié)構(gòu)的定義：

typedef struct dictEntry {
    void *key;  /*存儲(chǔ)鍵*/
    union {    
        void *val;      /*db.dict中的val*/
        uint64_t u64;
        int64_t s64;   /*db.expires中存儲(chǔ)過(guò)期時(shí)間*/
        double d;
    } v;     /*值是個(gè)聯(lián)合體*/
    struct dictEntry *next;  /*當(dāng)hash沖突時(shí)详拙，指向沖突的元素，形成單鏈表*/
} dictEntry;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;     /*指針數(shù)組蔓同，用于存儲(chǔ)鍵值對(duì)*/
    unsigned long size;  /*table數(shù)組的大小*/
    unsigned long sizemask;  /*掩碼 = size - 1*/
    unsigned long used;  /*table數(shù)組已存元素個(gè)數(shù)饶辙，包含next單鏈表的數(shù)據(jù)*/
} dictht;

typedef struct dict {
    dictType *type;  /*該字典對(duì)應(yīng)的特定操作函數(shù)*/
    void *privdata;   /*該字典依賴(lài)的數(shù)據(jù)*/
    dictht ht[2];   /*Hash表，鍵值對(duì)存儲(chǔ)在這里*/
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* 當(dāng)前運(yùn)行的迭代函數(shù) */
} dict;

關(guān)系結(jié)構(gòu)圖如下:

Redis字典結(jié)構(gòu)圖

Redis的字典實(shí)現(xiàn)主要依賴(lài)的數(shù)據(jù)結(jié)構(gòu)包括三部分：dict斑粱，dictht弃揽，dictEntry節(jié)點(diǎn)。dict中嵌入了2個(gè)
dictht表则北，dictht表中的table字典存放著dictEntry

下面介紹一下這些結(jié)構(gòu)體的各個(gè)字段作用：

dict結(jié)構(gòu)
    type：是用戶(hù)自定義的函數(shù)列表矿微，主要用于插入數(shù)據(jù)到字典時(shí)進(jìn)行的一些操作，比如計(jì)算key哈希值的
 hashFunction 函數(shù)句柄尚揣。
    privdata：創(chuàng)建字典時(shí)指定的私有數(shù)據(jù)涌矢，一般提供給 type 字段中的函數(shù)句柄使用。
    ht[2]：類(lèi)型為 dictht 結(jié)構(gòu)的數(shù)組快骗，這個(gè)數(shù)組有兩個(gè)元素娜庇，而 dictht 結(jié)構(gòu)主要用于保存數(shù)據(jù)，一
 般情況下只用ht[0],只有當(dāng)字典擴(kuò)容方篮，縮容需要進(jìn)行rehash時(shí)才會(huì)用到ht[1].
    rehashidx：rehash操作過(guò)程中最后一次處理的桶索引思灌。
    iterators：用于迭代字典中的數(shù)據(jù)。

dictht結(jié)構(gòu)
    table：類(lèi)型為 dictEntry 結(jié)構(gòu)指針的數(shù)組恭取，用于保存數(shù)據(jù)，每個(gè) key-value 的數(shù)據(jù)對(duì)通過(guò)類(lèi)型為
 dictEntry 的結(jié)構(gòu)來(lái)存儲(chǔ)熄守。
    size：table數(shù)組的大小蜈垮。
    sizemark：用于取模耗跛，得到一個(gè) 0 ～ size 的索引值。恒等于size-1
    used：表示字典中有多少個(gè)元素攒发。包含next單鏈表數(shù)據(jù)

dictEntry結(jié)構(gòu)
    key：數(shù)據(jù)的鍵调塌，主要用于查找數(shù)據(jù)。
    v：數(shù)據(jù)的值惠猿，數(shù)據(jù)主要通過(guò)這個(gè)字段來(lái)存儲(chǔ)羔砾。
    next：用于解決Hash沖突，把沖突的key連接起來(lái)（拉鏈法）偶妖。

字典初始化

在redis-server啟動(dòng)中姜凄，整個(gè)數(shù)據(jù)庫(kù)會(huì)先初始化一個(gè)空的字典用于存儲(chǔ)整個(gè)數(shù)據(jù)庫(kù)的鍵值對(duì)，初始化一個(gè)空字典趾访，主要調(diào)用的是dict.h文件中的dictCreate函數(shù)态秧，對(duì)應(yīng)的源碼為:

/* Reset a hash table already initialized with ht_init().
 * NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

/* 創(chuàng)建一個(gè)新的hash表 */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));  //96字節(jié)
    _dictInit(d,type,privDataPtr);  //結(jié)構(gòu)體初始化值
    return d;
}

/* 初始化hash表 */
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;
}

dictCreate函數(shù)初始化一個(gè)空字典的主要步驟為：申請(qǐng)空間，調(diào)用_dictInit函數(shù)扼鞋，給字典的各個(gè)字段賦予初始值申鱼。初始化后，一個(gè)字典內(nèi)存占用情況如下圖所示：

初始化示意圖

下面來(lái)看看在Redis中怎么創(chuàng)建一個(gè)字典的：

------server.c------
/* Command table. sds string -> command struct pointer. */
dictType commandTableDictType = {
    dictSdsCaseHash,            /* hash function */
    NULL,                       /* key dup */
    NULL,                       /* val dup */
    dictSdsKeyCaseCompare,      /* key compare */
    dictSdsDestructor,          /* key destructor */
    NULL                        /* val destructor */
};

/*初始化服務(wù)端配置*/
void initServerConfig(void) {
    ........
    server.commands = dictCreate(&commandTableDictType,NULL);
    server.orig_commands = dictCreate(&commandTableDictType,NULL);
    ........
}

創(chuàng)建字典時(shí)云头，需要提供 dictType 參數(shù)捐友，而這個(gè)參數(shù)主要定義了插入數(shù)據(jù)到字典時(shí)進(jìn)行的一些操作，比如插入數(shù)據(jù)時(shí)key是否要進(jìn)行復(fù)制的keyDup函數(shù)溃槐，那么我們來(lái)看看 dictType 的定義：

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);  /*用于計(jì)算鍵的哈希值*/
    void *(*keyDup)(void *privdata, const void *key);  /*用于復(fù)制數(shù)據(jù)的鍵*/
    void *(*valDup)(void *privdata, const void *obj);  /*用于復(fù)制數(shù)據(jù)的值*/
    /*用于比較鍵是否相等*/
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);  /*用于釋放復(fù)制出來(lái)的鍵的內(nèi)存*/
    void (*valDestructor)(void *privdata, void *obj);  /*用于釋放復(fù)制出來(lái)的值的內(nèi)存*/
} dictType;

插入元素

redis-server啟動(dòng)后匣砖，再啟動(dòng)redis-client連上server，執(zhí)行命令 “set hello world”：
127.0.0.1:6379> set hello world
Server端收到命令后竿痰，會(huì)執(zhí)行void setKey(redisDb *db, robj *key, robj *val);根據(jù)之前介紹字典的特性脆粥，每個(gè)鍵必須是唯一的，主要流程如下:

1). 調(diào)用dictFind函數(shù)影涉，查找鍵是否存在变隔，則調(diào)用dbOverwrite函數(shù)修改鍵值對(duì)，否則調(diào)用dictAdd函數(shù)
添加元素
2). dbAdd會(huì)調(diào)用dict.h中的dictAdd函數(shù)插入鍵值對(duì).

dictAdd函數(shù)源碼如下：

/* 調(diào)用之前會(huì)查找key是否存在蟹倾，不存在則調(diào)用dictAdd函數(shù) */
int dictAdd(dict *d, void *key, void *val)
{
    /*添加鍵匣缘，字典中鍵已存在則返回NULL,否則添加鍵到新節(jié)點(diǎn)中，返回新節(jié)點(diǎn)*/
    dictEntry *entry = dictAddRaw(d,key,NULL); 
    if (!entry) return DICT_ERR;   /*鍵存在則返回錯(cuò)誤*/
    dictSetVal(d, entry, val);  /*設(shè)置新值*/
    return DICT_OK;
}

而dictAdd() 函數(shù)主要還是通過(guò)調(diào)用 dictAddRaw() 函數(shù)來(lái)完成插入操作鲜棠，dictAddRaw() 函數(shù)的代碼如下：

 /*入?yún)⒆值浼〕I，Hash表節(jié)點(diǎn)地址*/
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) 
{
    long index;
    dictEntry *entry;
    dictht *ht;
    /*該字典是否在進(jìn)行rehash操作豁陆，如果是則執(zhí)行一次rehash*/
    if (dictIsRehashing(d)) _dictRehashStep(d);
    /*查找鍵柑爸，找到則直接返回-1，并把老節(jié)點(diǎn)存入existing字段盒音，否則把新節(jié)點(diǎn)的索引值返回表鳍，
    如果遇到Hash表容量不足馅而，則進(jìn)行擴(kuò)容*/
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;
    /*是否進(jìn)行rehash操作中，如果是則插入到散列表ht[1]中譬圣，否則插入到散列表ht[0]*/
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    /*申請(qǐng)新節(jié)點(diǎn)內(nèi)存瓮恭，插入散列表中，給新節(jié)點(diǎn)存入鍵信息*/
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

dictAddRaw() 函數(shù)主要完成以下幾個(gè)工作：

1). 判斷是否正在進(jìn)行rehash操作（dictIsRehashing() 判斷為真）厘熟，如果是就調(diào)用 
_dictRehashStep() 函數(shù)進(jìn)行rehash屯蹦。
2). 通過(guò)調(diào)用 _dictKeyIndex() 函數(shù)計(jì)算key對(duì)應(yīng)所在哈希表的位置（索引）index。
3).如果正在進(jìn)行rehash绳姨，那么就使用ht數(shù)組的第二個(gè)哈希表登澜，否則就用第一個(gè)
4).創(chuàng)建一個(gè) dictEntry 結(jié)構(gòu)用于保存數(shù)據(jù)的鍵和值。

dictAddRaw() 函數(shù)會(huì)返回一個(gè)類(lèi)型為 dictEntry 結(jié)構(gòu)的值就缆，然后 dictAdd() 函數(shù)通過(guò)調(diào)用 dictSetVal() 函數(shù)設(shè)置其值帖渠。
插入元素，字典對(duì)應(yīng)的內(nèi)存占用結(jié)構(gòu)如下圖:

字典添加一個(gè)元素后(結(jié)構(gòu)示意圖)

字典擴(kuò)容

當(dāng)哈希表中的數(shù)據(jù)個(gè)數(shù)超過(guò)一定數(shù)量時(shí)竭宰，哈希沖突的鏈表過(guò)長(zhǎng)空郊，從而導(dǎo)致查詢(xún)效率降低，這個(gè)時(shí)候就需要Rehash操作切揭。Rehash操作是將哈希表的數(shù)組擴(kuò)大狞甚，從而減少哈希沖突的比率。當(dāng)然擴(kuò)大哈希表的數(shù)組會(huì)導(dǎo)致之前的映射關(guān)系無(wú)效廓旬，所以需要把舊數(shù)據(jù)重新遷移到新的哈希表數(shù)組中哼审。

Redis在插入數(shù)據(jù)到字典時(shí)，會(huì)通過(guò) _dictExpandIfNeeded() 函數(shù)來(lái)判斷是否需要進(jìn)行Rehash操作孕豹，_dictExpandIfNeeded() 函數(shù)代碼如下：

static int _dictExpandIfNeeded(dict *d)
{
    if (dictIsRehashing(d)) return DICT_OK;

    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

_dictExpandIfNeeded() 函數(shù)主要完成3個(gè)工作：

1). 通過(guò) dictIsRehashing() 來(lái)判斷字典是否正在Rehash操作涩盾，如果是就直接返回OK，不需要再進(jìn)行
Rehash励背。
2). 如果字典的第一個(gè)哈希表的大小為0春霍，表示需要對(duì)第一個(gè)哈希表進(jìn)行初始化。
3). 如果第一個(gè)哈希表的元素個(gè)數(shù)大于等于哈希表的大小叶眉，那么就對(duì)第一個(gè)哈希表進(jìn)行Rehash操作（把
哈希表的大小擴(kuò)大為原來(lái)的2倍）址儒。

進(jìn)行Rehash操作通過(guò)調(diào)用 dictExpand() 函數(shù)來(lái)完成，擴(kuò)容對(duì)應(yīng)的源碼是dict.h文件中的dictExpand函數(shù)衅疙，源碼如下:

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)   /*傳入size = d->ht[0].used * 2 */
{
    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size) 
        return DICT_ERR;

    dictht n; /* the new hash table */
    /*重新計(jì)算擴(kuò)容后的值莲趣，必須為2的N次方冪*/
    unsigned long realsize = _dictNextPower(size);

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;  /*擴(kuò)容后的新內(nèi)存放入ht[1]中*/
    d->rehashidx = 0; /*非-1，表示需要進(jìn)行rehash*/
    return DICT_OK;
}

dictExpand() 函數(shù)比較簡(jiǎn)單饱溢，就是申請(qǐng)一個(gè)更大的哈希數(shù)組喧伞，如果第一個(gè)哈希表的哈希數(shù)組為空，那么就把第一個(gè)哈希表的哈希數(shù)組設(shè)置為新的哈希數(shù)組。否則將第二個(gè)哈希表的哈希數(shù)組設(shè)置為新的哈希數(shù)組絮识。

擴(kuò)容的主要流程如下:

1). 申請(qǐng)一塊新內(nèi)存后绿聘，初次申請(qǐng)是默認(rèn)大小為4個(gè)dictEntry；非初次申請(qǐng)時(shí)次舌，申請(qǐng)內(nèi)存的大小為當(dāng)前
Hash表容量的一倍。
2）把新申請(qǐng)的內(nèi)存地址賦值給ht[1],并把字典的rehashidx標(biāo)識(shí)從-1改為0兽愤，表示只有需要進(jìn)行rehash
操作彼念，此時(shí)字典的內(nèi)存結(jié)構(gòu)如下

擴(kuò)容后示意圖

漸進(jìn)式Rehash操作

從 dictExpand() 函數(shù)的實(shí)現(xiàn)來(lái)看，并沒(méi)有在這里對(duì)數(shù)據(jù)進(jìn)行Rehash操作浅萧，只是把哈希數(shù)組擴(kuò)大2倍而已逐沙，那么Rehash操作在什么時(shí)候進(jìn)行呢？對(duì)數(shù)據(jù)進(jìn)行Rehash操作的觸發(fā)點(diǎn)有很多個(gè)洼畅，如插入吩案、刪除和查找，當(dāng)然最后都會(huì)調(diào)用 dictRehash() 函數(shù)來(lái)完成帝簇，我們來(lái)看看 dictRehash() 函數(shù)的實(shí)現(xiàn)： rehash 擴(kuò)縮容操作都會(huì)進(jìn)行觸發(fā)徘郭。Redis的整個(gè)rehash實(shí)現(xiàn)，源碼如下：

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * 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) {
            uint64_t 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;
}

dictRehash() 函數(shù)的第二個(gè)參數(shù)是指定了每次要對(duì)多少個(gè)槽進(jìn)行Rehash（也就是沖突鏈表）丧肴，Rehash操作就是遍歷第一個(gè)哈希表的所有數(shù)據(jù)残揉，然后重新計(jì)算key的哈希值，保存到第二個(gè)哈希表中芋浮，并且從第一個(gè)哈希表中刪除抱环。當(dāng)?shù)谝粋€(gè)哈希表的元素個(gè)數(shù)為0時(shí)，就將第一個(gè)哈希表替換成第二個(gè)哈希表纸巷，并且完成Rehash操作镇草。

漸進(jìn)式Rehash后示意圖

查找元素

我們看下查找元素，從客戶(hù)端讀取hello的值：
127.0.0.1:6379> get hello
“world”
Server端收到get命令后瘤旨，最終要在字典中查找某個(gè)key鍵值對(duì)會(huì)執(zhí)行dict.h中的dictFind()函數(shù)梯啤，源碼如下:

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);    /*得到鍵的Hash值*/
    for (table = 0; table <= 1; table++) {  /*遍歷查找Hash表  ht[0]與ht[1]*/
        idx = h & d->ht[table].sizemask;  /*根據(jù)Hash值獲取到對(duì)應(yīng)的索引值*/
        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;  /*如果未進(jìn)行rehash操作裆站，則只讀取ht[0]*/
    }
    return NULL;
}

通過(guò)上面的介紹說(shuō)明条辟，dictFind() 函數(shù)的實(shí)現(xiàn)也比較容易理解，主要進(jìn)行了如下操作:

1). 如果字典中第一個(gè)和第二個(gè)哈希表都為空宏胯，那么就返回NULL羽嫡。
2). 如果判斷正在進(jìn)行Rehash操作，調(diào)用 _dictRehashStep() 對(duì)數(shù)據(jù)進(jìn)行分步Rehash肩袍。
3). 根據(jù)鍵調(diào)用Hash函數(shù)取得其Hash值
4). 遍歷字典的2個(gè)Hash表杭棵，讀取索引對(duì)應(yīng)的元素
5). 根據(jù)Hash值取到索引值
6). 根據(jù)索引在hash表中找到元素值，并先在第一個(gè)哈希表中查找是否存在，如果存在就返回key對(duì)應(yīng)的
值魂爪。如果key不在第一個(gè)哈希表中先舷，那么就要判斷當(dāng)前是否正在Rehash操作，如果是就在第二個(gè)哈希表中查
找key是否存在滓侍。因?yàn)樵赗ehash的過(guò)程中蒋川，key有可能被移動(dòng)到第二個(gè)哈希表中。
7). 找不到則返回NULL

修改元素

說(shuō)完查找元素后撩笆，繼續(xù)跟進(jìn)修改字典中的鍵值對(duì)元素捺球，客戶(hù)端執(zhí)行命令:
127.0.0.1:6379> set hello world2
OK
Server端收到set命令后，會(huì)查詢(xún)鍵是否已經(jīng)在數(shù)據(jù)庫(kù)中存在夕冲，存在則執(zhí)行db.c文件中的dbOverwrite函數(shù)氮兵，源碼如下:

/* Overwrite an existing key with a new value. Incrementing the reference
 * count of the new value is up to the caller.
 * This function does not modify the expire time of the existing key.
 * The program is aborted if the key was not already present. */
void dbOverwrite(redisDb *db, robj *key, robj *val) {
    dictEntry *de = dictFind(db->dict,key->ptr);  /*查找鍵是否存在，返回存在的節(jié)點(diǎn)*/
    serverAssertWithInfo(NULL,key,de != NULL); /*不存在則中斷執(zhí)行*/
    dictEntry auxentry = *de;
    robj *old = dictGetVal(de);   /*獲取老節(jié)點(diǎn)val字段值*/
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        val->lru = old->lru;
    }
    dictSetVal(db->dict, de, val);   /*給節(jié)點(diǎn)設(shè)置新的值*/
    if (server.lazyfree_lazy_server_del) {
        freeObjAsync(old);
        dictSetVal(db->dict, &auxentry, NULL);
    }
    dictFreeVal(db->dict, &auxentry);   /*釋放節(jié)點(diǎn)中舊val內(nèi)存*/
}

刪除元素

繼續(xù)跟進(jìn)刪除字典中鍵值對(duì)歹鱼，客戶(hù)端執(zhí)行命令：
127.0.0.1:6379> del hello
（integer）1
Server收到del命令后泣栈，刪除鍵值對(duì)會(huì)執(zhí)行dict.h文件中的dictDelete函數(shù),源碼如下：

/* 查找并刪除元素 */
static int dictDelete(dict *ht, const void *key) {
    unsigned int h;
    dictEntry *de, *prevde;

    if (ht->size == 0)
        return DICT_ERR;
    h = dictHashKey(ht, key) & ht->sizemask;
    de = ht->table[h];

    prevde = NULL;
    while(de) {
        if (dictCompareHashKeys(ht,key,de->key)) {  /*比對(duì)hash值*/
            /* Unlink the element from the list */
            if (prevde)
                prevde->next = de->next;
            else
                ht->table[h] = de->next;

            dictFreeEntryKey(ht,de);  /*釋放該節(jié)點(diǎn)對(duì)應(yīng)的鍵占用的內(nèi)存*/
            dictFreeEntryVal(ht,de);  /*釋放該節(jié)點(diǎn)對(duì)應(yīng)的值占用的內(nèi)存*/
            free(de);   /*釋放本身占用內(nèi)存*/
            ht->used--;  /*used -1*/
            return DICT_OK;
        }
        prevde = de;
        de = de->next;
    }
    return DICT_ERR; /* not found */
}

刪除函數(shù)主要進(jìn)行以下操作：

1). 查找該鍵釋放存在該字典中。
2). 存在則把該節(jié)點(diǎn)從單鏈表中刪除弥姻。
3). 釋放該節(jié)點(diǎn)對(duì)應(yīng)鍵占用的內(nèi)存南片，值占用的內(nèi)存，以及本身占用的內(nèi)存蚁阳。
4). 給對(duì)應(yīng)的Hash表的used字典減1操作

API列表

前面講解了字典概念以及難點(diǎn)铃绒，在此開(kāi)始介紹字典相關(guān)的API函數(shù)列表，主要聲明在dict.h中：

/* API */
dict *dictCreate(dictType *type, void *privDataPtr); /*初始化字典*/
int dictExpand(dict *d, unsigned long size);  /*字典擴(kuò)容*/
int dictAdd(dict *d, void *key, void *val); /*添加鍵值對(duì)螺捐，已存在則不加*/
 /*添加key颠悬，并返回新添加的key對(duì)應(yīng)的節(jié)點(diǎn)。若已存在定血，則存入existing字段中赔癌，并返回-1*/
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing);
dictEntry *dictAddOrFind(dict *d, void *key); /*添加或者查找key*/
int dictReplace(dict *d, void *key, void *val);  /*添加鍵值對(duì)，若存在則修改澜沟，否則添加*/
int dictDelete(dict *d, const void *key);  /*刪除元素*/
dictEntry *dictUnlink(dict *ht, const void *key);  /*刪除key灾票，但不釋放內(nèi)存*/
void dictFreeUnlinkedEntry(dict *d, dictEntry *he); /*釋放dictUnlink函數(shù)刪除key的內(nèi)存*/
void dictRelease(dict *d);   /*釋放字典*/
dictEntry * dictFind(dict *d, const void *key);  /*根據(jù)鍵查找元素*/
void *dictFetchValue(dict *d, const void *key);  /*根據(jù)鍵查找出值*/
int dictResize(dict *d);   /*擴(kuò)縮容字典*/
dictIterator *dictGetIterator(dict *d); /*初始化普通迭代器*/
dictIterator *dictGetSafeIterator(dict *d);   /*初始化安全迭代器*/
dictEntry *dictNext(dictIterator *iter);  /*通過(guò)迭代器獲取下一個(gè)節(jié)點(diǎn)*/
void dictReleaseIterator(dictIterator *iter);  /*釋放迭代器*/
dictEntry *dictGetRandomKey(dict *d);  /*隨機(jī)得到一個(gè)鍵*/
dictEntry *dictGetFairRandomKey(dict *d); 
/*隨機(jī)得到一些鍵*/
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count);
void dictGetStats(char *buf, size_t bufsize, dict *d);  /*讀取字典的狀態(tài)，使用情況等*/
uint64_t dictGenHashFunction(const void *key, int len); /*hash函數(shù) 字母大小寫(xiě)敏感*/
/*hash函數(shù) 字母大小寫(xiě)不敏感*/
uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len);
void dictEmpty(dict *d, void(callback)(void*));  /*清空一個(gè)字典*/
void dictEnableResize(void); /*開(kāi)啟Resize*/
void dictDisableResize(void); /*關(guān)閉Resize*/
int dictRehash(dict *d, int n);  /*漸進(jìn)式rehash, n為進(jìn)行幾步*/
int dictRehashMilliseconds(dict *d, int ms);   /*持續(xù)性rehash茫虽， ms為持續(xù)多久*/
void dictSetHashFunctionSeed(uint8_t *seed);  /*設(shè)置新的散列種子*/
uint8_t *dictGetHashFunctionSeed(void);  /*獲取當(dāng)前散列種子值*/
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, 
dictScanBucketFunction *bucketfn, void *privdata);  /*間斷性的迭代字段數(shù)據(jù)*/
uint64_t dictGetHash(dict *d, const void *key);  /*得到鍵的hash值*/
 /*使用指針+hash值去查找元素*/
dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash); 

總結(jié)

字典在Redis數(shù)據(jù)庫(kù)中起到了很重要的作用刊苍，本文主要介紹了哈希表和Redis字典的設(shè)計(jì)與實(shí)現(xiàn)。其中Redis字典對(duì)普通哈希表進(jìn)行優(yōu)化和改進(jìn)濒析，以減少Rehash操作對(duì)服務(wù)造成的阻塞正什。后面會(huì)繼續(xù)介紹Hash的一些命令講解。

參考資料： 陳雷老師的Redis5設(shè)計(jì)與源碼分析