使用場景：

# set person name "tom"

# set person name "jerry"

1. 字典結(jié)構(gòu)：

哈希表數(shù)據(jù)結(jié)構(gòu)typedef struct dictht {//哈希表數(shù)組，存的是哈希值dictEntrry **table;//哈希表大小(table的大小)unsigned long size;//哈希表大小掩碼，用于計(jì)算索引值，總是等于size-1unsigned long sizemask;//該哈希表已有節(jié)點(diǎn)的數(shù)量unsigned long used;} dictht; 哈希表節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)typedef struct dictEntry {//鍵void *key;//值 union {
//值可以是一個指針void *val;//也可以是一個uint64_t整數(shù)uint64_tu64;//也可以是int64_t整數(shù)int64_ts64;} v;//指向下個哈希表節(jié)點(diǎn)，形成鏈表，用來使用拉鏈法解決哈希沖突struct dictEntry *next;} dictEntry; 字典數(shù)據(jù)結(jié)構(gòu)typedef struct dict {//類型特定函數(shù)(保存了一些操作特定類型鍵值對函數(shù))dictType *type;//私有數(shù)據(jù)(保存了傳給特定函數(shù)的一些參數(shù))void *privdata;//哈希表(一般使用ht[0]哈希表，ht[1]是在rehash時使用)dictht ht[2];//rehash 索引(記錄了rehash的進(jìn)度，不rehash時，值為-1)int trehashidx;} dict;

2. 哈希算法：

當(dāng)添加一個新鍵值時，會先根據(jù)鍵計(jì)算出哈希值和索引值，然后將新鍵值節(jié)點(diǎn)放到指定索引上(dictEntry*[index])。

計(jì)算哈希值：hash = dict -> type -> hashFunction(key);

計(jì)算索引值：index = hash & dict -> ht[x].sizemask;

3. 解決哈希沖突：

當(dāng)鍵沖突時，使用next指針將新鍵連接起來。注意：為了速度考慮，程序會將新節(jié)點(diǎn)添加到鏈表的表頭位置。

4. rehash：

隨著數(shù)據(jù)的增多和減少，為了讓哈希表的負(fù)載因子維持在一個合理的范圍，需要對哈希表進(jìn)行擴(kuò)展和收縮。

負(fù)載因子：load_factor = ht[0].used / ht[0].size

rehash擴(kuò)展觸發(fā)條件：

1). 服務(wù)器目前沒有在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且負(fù)載因子大于等于1。

2). 服務(wù)器目前正在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且負(fù)載因子大于等于0.5。

rehash收縮觸發(fā)條件：負(fù)載因子小于0.1。

步驟如下：

1). 在沒有rehash時，字典只使用ht[0]。在rehash時，程序會對ht[1]分配空間。

擴(kuò)展：ht[1]的大小為第一個大于等于ht[0].used * 2的2^n (2的n次方冪)；

收縮：ht[1]的大小為第一個大于等于ht[0].used的2^n；

2).? 將ht[0]的所有數(shù)據(jù)全部rehash到ht[1]上面，rehash指的是重新計(jì)算鍵的哈希值和索引值，然后放到ht[1]的指定位置上。

3). 當(dāng)ht[0]上的數(shù)據(jù)全部遷移到ht[1]后，釋放ht[0]，將ht[1]置為ht[0]，并在ht[1]上新建一個空的哈希表，為下一次rehash做準(zhǔn)備。

5.? 漸進(jìn)式rehash（rehash的優(yōu)化，觸發(fā)條件由負(fù)載因子決定，如上）

當(dāng)哈希表的鍵值對數(shù)量巨大時，一次rehash會非常耗時，為了避免對服務(wù)器性能造成影響，服務(wù)器采用分批次、漸進(jìn)式的將ht[0]里面的鍵值對慢慢的rehash到ht[1]。

步驟：

1）為ht[1]分配空間，字典同時持有ht[0]和ht[1]。

2）字典中設(shè)置一個計(jì)數(shù)器rehashidx，當(dāng)值為0時，表示rehash開始。

3）在rehash期間，每次增刪改查時，程序還會順帶將ht[0]在rehashidx索引上的所有鍵值對rehash到ht[1]，當(dāng)rehash完成后，rehashidx增一。(這里是將table上對應(yīng)的某條索引值指向的數(shù)據(jù)節(jié)點(diǎn)鏈表遷移到ht[1]中，th[0].table[rehashidx]數(shù)據(jù)就空了)

4）隨著操作的不斷執(zhí)行，ht[0]上的所有鍵值對都會被rehash到ht[1]上，這時rehashidx為-1，表示rehash完成。

注意：

1）在rehash執(zhí)行期間，新數(shù)據(jù)會保存到ht[1]里面，而ht[0]不進(jìn)行添加操作，這樣，ht[0]里的數(shù)據(jù)會逐漸遷移到ht[1]，直到ht[0]清空。

2）在rehash執(zhí)行期間，查找某個鍵時，會先從ht[0]中查找，如果沒找到就去ht[1]里面查找。

?

轉(zhuǎn)載于:https://www.cnblogs.com/wwzyy/p/10615939.html

總結(jié)

以上是生活随笔為你收集整理的Redis数据结构：字典（hash表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。