字典梗肝，又稱為符號(hào)表，關(guān)聯(lián)數(shù)組巫击，映射禀晓，是一種用于保存鍵值對(duì)的抽象數(shù)據(jù)結(jié)構(gòu)

字典中一個(gè)鍵key和一個(gè)值value進(jìn)行關(guān)聯(lián)凫乖，這些關(guān)聯(lián)的鍵和值稱為鍵值對(duì)帽芽，每個(gè)鍵都是唯一的，可以根據(jù)鍵來(lái)查找與之對(duì)應(yīng)的值款票，或者通過(guò)鍵來(lái)更新值，或者通過(guò)鍵來(lái)刪除鍵值對(duì)

Redis所使用的C語(yǔ)言沒(méi)有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)泽论，因此Redis構(gòu)建了自己的字典實(shí)現(xiàn)

字典在Redis中的應(yīng)用

Redis的數(shù)據(jù)庫(kù)就是使用字典來(lái)作為底層實(shí)現(xiàn)的艾少，對(duì)數(shù)據(jù)庫(kù)的增刪改查操作也是構(gòu)建在對(duì)字典的操作之上的
字典也是哈希鍵的底層實(shí)現(xiàn)之一，當(dāng)一個(gè)哈希鍵包含的鍵值對(duì)多的時(shí)候翼悴，或者鍵值對(duì)中的元素都是比較長(zhǎng)的字符串的時(shí)候缚够，Redis就會(huì)使用字典作為哈希鍵的底層實(shí)現(xiàn)

字典的實(shí)現(xiàn)

Redis的字典使用哈希表作為底層實(shí)現(xiàn)，一個(gè)哈希表里面可以有多個(gè)哈希表節(jié)點(diǎn)抄瓦，而每個(gè)哈希表節(jié)點(diǎn)就保存了字典中的一個(gè)鍵值對(duì)

哈希表

哈希表dict.h/dictht

typedef struct dictht{
  //哈希表數(shù)組
  dictEntry **table;
  //哈希表大小
  unsigned long size;
  //哈希表大小掩碼潮瓶，用于計(jì)算索引值，size-1
  unsigned long sizemask;
  //該哈希表已有節(jié)點(diǎn)數(shù)量
  unsigned long used;
}dictht;

一個(gè)大小為4空的哈希表

table屬性是一個(gè)數(shù)組钙姊，數(shù)組中的每一個(gè)元素都是一個(gè)指向dictEntry結(jié)構(gòu)的一個(gè)指針，每個(gè)dictEntry結(jié)構(gòu)保存著一個(gè)鍵值對(duì)
size屬性記錄了哈希表的大小埂伦，也就是當(dāng)前table的大小
used屬性記錄了哈希表目前已有節(jié)點(diǎn)（鍵值對(duì)）的數(shù)量
sizemask屬性的值是size-1煞额，這個(gè)屬性和哈希值一起決定一個(gè)鍵應(yīng)該被放到table數(shù)組的那個(gè)索引上面

哈希表節(jié)點(diǎn)

哈希表節(jié)點(diǎn)使用dictEntry結(jié)構(gòu)保存，每個(gè)dictEntry結(jié)構(gòu)都保存著一個(gè)鍵值對(duì)

typedef struct dictEntry{
  //鍵
  void *key沾谜；
  //值
  union{
    void *val;
    uint64_tu64;
    int64_ts64;
  }v;
  //指向下個(gè)哈希表節(jié)點(diǎn)膊毁，形成鏈表
  struct dictEntry *next;
}dictEntry;

連接在一起的鍵K1和鍵K0

key：保存著鍵值對(duì)中的鍵
v:保存鍵值對(duì)中的值，可以是一個(gè)指針基跑，或uint64_t整數(shù)婚温，或int64_t整數(shù)
next:指向另一個(gè)哈希表節(jié)點(diǎn)的指針，這個(gè)這種可以將多個(gè)哈希值相同的鍵值對(duì)連接到一起媳否，來(lái)解決鍵沖突問(wèn)題

字典

字典使用dict.h/dict結(jié)構(gòu)表示

typedef struct dict{
  //類型特定函數(shù)
  dictType *type;
  //私有數(shù)據(jù)
  void *privdata;
  //哈希表
  dictht ht[2];
  //rehash 索引栅螟，當(dāng)rehash不在進(jìn)行時(shí)，值為-1
  int rehashidx;    
}dict;

普通狀態(tài)下的字典

type和privdata屬性是針對(duì)不同類型的鍵值對(duì)篱竭，為創(chuàng)建多態(tài)字典而設(shè)置的
type屬性是一個(gè)指向dictType結(jié)構(gòu)的指針力图，每個(gè)dictType結(jié)構(gòu)保存了一族用于操作特定類型鍵值對(duì)的函數(shù)，Redis會(huì)為用途不同的字典設(shè)置不同的類型特定函數(shù)
privdata屬性保存了需要傳給那些特定函數(shù)的可選參數(shù)

typedef struct dictType{
  //計(jì)算哈希值的函數(shù)
  unsigned int (*hashFunction)(const void *key);
  //復(fù)制鍵的函數(shù)
  void *(*keyDup)(void *privdata,const void *key);
  //復(fù)制值的函數(shù)
  void *(*valDup)(void *privdata,const void *obj);
  //對(duì)比鍵的函數(shù)
  int (*keyCompare)(void *privdata,const void *key1,const void *key2);
  //銷毀鍵的函數(shù)
  void (*keyDestructor)(void *privdata,void *key);
  //銷毀值的函數(shù)
  void (*valDestructor)(void *privdata,void *obj);
}dictType;

ht屬性是一個(gè)包含兩個(gè)項(xiàng)的數(shù)組掺逼，數(shù)組中的每個(gè)項(xiàng)都是一個(gè)dictht哈希表吃媒，一般情況下，字典只使用ht[0]哈希表吕喘，ht[1]哈希表只會(huì)在對(duì)ht[0]進(jìn)行rehash是使用
rehashidx記錄了目前的進(jìn)度赘那，如果目前沒(méi)有在進(jìn)行的rehash，那么他的值為-1

哈希算法

如果要將一個(gè)新的鍵值對(duì)添加到字典中的時(shí)候氯质，程序需要先根據(jù)鍵值對(duì)的鍵計(jì)算出哈希值和索引值募舟，然后根據(jù)索引值，將包含新鍵值對(duì)的哈希表節(jié)點(diǎn)放到哈希表數(shù)組的指定索引上面

Redis計(jì)算哈希值和索引值的方法：

• 使用字典設(shè)置的哈希函數(shù)病梢，計(jì)算key的哈希值
  hash=dict->type->hashFunction(key);
• 使用哈希表的sizemask屬性和哈希值胃珍，計(jì)算出索引值梁肿，根據(jù)情況不同，ht[x]可以是ht[0]或者h(yuǎn)t[1]
  index=hash & dict->ht[x].sizemask;

當(dāng)字典被用作數(shù)據(jù)庫(kù)的底層實(shí)現(xiàn)觅彰，或者哈希鍵的底層實(shí)現(xiàn)時(shí)吩蔑，Redis使用MurmurHash2算法來(lái)計(jì)算鍵的哈希值，這種算法的優(yōu)點(diǎn)在于填抬，即使輸入的鍵是有規(guī)律的烛芬，算法仍然能給出一個(gè)很好的隨機(jī)分布性，并且算法的計(jì)算速度非踌穑快

解決鍵沖突

當(dāng)有兩個(gè)或兩個(gè)以上數(shù)量的鍵被分配到了哈希表數(shù)組的同一個(gè)索引上面時(shí)赘娄，這些鍵就發(fā)生了沖突

Redis的哈希表使用鏈地址法來(lái)解決沖突，每個(gè)哈希表節(jié)點(diǎn)都有一個(gè)next指針宏蛉，多個(gè)哈希表節(jié)點(diǎn)可以用next指針構(gòu)成一個(gè)單向鏈表遣臼，被分配到同一個(gè)索引上的多個(gè)節(jié)點(diǎn)可以用這個(gè)單向鏈表連接起來(lái)，這就解決了鍵沖突的問(wèn)題

rehash

隨著操作的不斷進(jìn)行拾并，哈希表保存的鍵值對(duì)會(huì)逐漸增多或減少揍堰，為了讓哈希表的負(fù)載因子維持在一個(gè)合理的范圍內(nèi)，當(dāng)哈希表保存的鍵值對(duì)數(shù)量太多或太少嗅义，程序需要對(duì)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者收縮

擴(kuò)展和收縮哈希表可以通過(guò)執(zhí)行rehash（重新散列）操作來(lái)完成

• Redis對(duì)字典的哈希表執(zhí)行rehash的步驟如下：

1. 為字典的ht[1]哈希表分配空間屏歹，這個(gè)哈希表的空間大小取決于要執(zhí)行的操作，以及ht[0]當(dāng)前包含的鍵值對(duì)數(shù)量（ht[0].used屬性的值）：

• 如果執(zhí)行的是擴(kuò)展操作之碗，那么ht[1]的大小為第一個(gè)大于等于ht[0].used*2的2^n(2的n次方冪)
• 如果執(zhí)行的是收縮操作蝙眶，那么ht[1]的大小為第一個(gè)大于等于ht[0].used的2^n

2. 將保存在ht[0]中的所有鍵值對(duì)rehash到ht[1]上面：

• rehash指的是重新計(jì)算鍵的哈希值和索引值，然后將鍵值對(duì)放到ht[1]哈希表的指定位置上

3. 當(dāng)ht[0]包含的所有鍵值對(duì)都遷移到了ht[1]之后（ht[0]變?yōu)榭毡恚┩誓牵尫舎t[0],將ht[1]設(shè)置為ht[0],并在ht[1]新建一個(gè)空白哈希表幽纷，為下一次rehash做準(zhǔn)備

• 對(duì)字典的ht[0]進(jìn)行擴(kuò)展操作

  
  
  執(zhí)行rehash之前的字典

1. ht[0].used的值為4,4*2=8，而2^3=8>=8,所以ht[1]哈希表的大小設(shè)置為8

   
   
   為字典的ht[1]哈希表分配空間

2. 將ht[0]包含的四個(gè)鍵值對(duì)都rehash到ht[1]

   
   
   ht[0]所有鍵值對(duì)都被遷移到ht[1]

3. 釋放ht[0],并將ht[1]設(shè)置為ht[0],然后為ht[1]分配一個(gè)空的哈希表武通，此時(shí)哈希表擴(kuò)展完成霹崎，程序?qū)⒐１淼拇笮脑瓉?lái)的4擴(kuò)展為8

   
   
   完成rehash之后的字典

當(dāng)滿足以下任意一個(gè)條件，程序自動(dòng)開(kāi)始對(duì)哈希表執(zhí)行擴(kuò)展操作

1. 服務(wù)器目前沒(méi)有執(zhí)行BGSAVE命令或者BGREWRITEAOF命令冶忱，并且哈希表的負(fù)載因子大于等于1
2. 服務(wù)器目前正在執(zhí)行BGSAVE命令尾菇，或者BGREWRITEAOF命令，并且哈希表負(fù)載因子大于等于5
   負(fù)載因子=ht[0].used/ht[0].size

當(dāng)哈希表的負(fù)載因子小于0.1囚枪，程序自動(dòng)開(kāi)始對(duì)哈希表執(zhí)行收縮操作

漸進(jìn)式rehash

rehash動(dòng)作并不是一次性的派诬，集中式的完成，而是分多次链沼，漸進(jìn)式完成的

因?yàn)槿绻１碇械逆I值對(duì)數(shù)量很多的時(shí)候默赂，那么一次性將這些鍵值對(duì)全部rehash到ht[1]上龐大的計(jì)算量會(huì)導(dǎo)致服務(wù)器在一段時(shí)間內(nèi)停止服務(wù)，因此為了避免rehash對(duì)服務(wù)器性能造成影響括勺，服務(wù)器不是一次性將ht[0]里面的鍵值對(duì)全部rehash到ht[1]上缆八，而是分多次曲掰，漸進(jìn)式第的將ht[0]里面的數(shù)據(jù)慢慢的rehash到ht[1]中

• 哈希表漸進(jìn)式rehash步驟

1. 為ht[1]分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表

2. 在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx奈辰，并將他設(shè)為0栏妖，表示rehash正式開(kāi)始

3. 在rehash進(jìn)行期間，每次對(duì)字典執(zhí)行添加奖恰，刪除吊趾，查找，或者更新操作瑟啃，程序除了執(zhí)行指定的操作之外论泛，還會(huì)順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對(duì)rehash到ht[1]上，當(dāng)rehash完成之后蛹屿，程序?qū)ehashidx屬性的值加1

4. 隨著字典操作的不斷執(zhí)行屁奏，最終在某個(gè)時(shí)間點(diǎn)上，ht[0]的所有鍵值對(duì)都會(huì)被rehash到ht[1]上错负，這時(shí)程序?qū)ehashidx屬性的值設(shè)為-1了袁，表示rehash完成了

好處：采取分而治之的方式，將rehash鍵值對(duì)所需的計(jì)算工作均攤到對(duì)字典的每個(gè)添加湿颅，刪除，查找粥诫，和更新操作上油航，從而避免了集中式rehash帶來(lái)的龐大計(jì)算量

漸進(jìn)式rehash圖解

準(zhǔn)備開(kāi)始rehash

rehash索引0上的鍵值對(duì)

rehash索引1上的鍵值對(duì)

rehash索引2上的鍵值對(duì)

rehash索引3上的鍵值對(duì)

rehash執(zhí)行完畢

漸進(jìn)式rehash執(zhí)行期間哈希表的操作

在執(zhí)行過(guò)程中，字典會(huì)同時(shí)使用ht[0]和ht[1]兩個(gè)哈希表怀浆，所以在漸進(jìn)rehash期間谊囚，字典的刪除，查找执赡，更新會(huì)在兩個(gè)哈希表上進(jìn)行

例如：

1. 在字典中查找一個(gè)鍵镰踏，程序會(huì)現(xiàn)在ht[0]里面查找，如果沒(méi)有找到沙合，就會(huì)繼續(xù)在ht[1]中查找
2. 新添加到字典的鍵值對(duì)一律會(huì)被保存到ht[1]中奠伪，而ht[0]不會(huì)進(jìn)行任何操作，保證了ht[0]包含的鍵值對(duì)數(shù)量只會(huì)減少首懈，不會(huì)增加绊率，并隨著rehash操作的執(zhí)行最終變?yōu)榭毡?/li>

字典API