數(shù)據(jù)結(jié)構(gòu)

凡是Hash字典，首先得有一個(gè)數(shù)組，這個(gè)數(shù)組是用來存儲(chǔ)<Key, Value>對中的Value。
<Key, Value>對中的Key，是用來計(jì)算Value在數(shù)組中的下標(biāo)位置。
一般的做法是，將Key通過特定的Hash算法得到一個(gè)整數(shù)值，然后將這個(gè)整數(shù)值與數(shù)組長度求余，計(jì)算的結(jié)果就是這個(gè)Value在數(shù)組中的位置。
然而當(dāng)出現(xiàn)Hash沖突，也就是不同的Key得到相同的Hash值的時(shí)候，不同的Value將會(huì)保存到數(shù)組中的同一個(gè)位置。那么這個(gè)時(shí)候數(shù)組中就不能單純的只存儲(chǔ)Value了，就要將數(shù)組中的元素鏈表化，變成如下圖所示：

image.png

數(shù)組中的每個(gè)元素，不僅要保存Value，還需要保存Key，以及指向下一個(gè)節(jié)點(diǎn)的指針。
所以當(dāng)出現(xiàn)Hash沖突的時(shí)候，不同的<Key, Value>對都分配到了同一個(gè)數(shù)組下標(biāo)位置，這時(shí)候這些不同的<Key, Value>對組成了一個(gè)鏈表，這個(gè)數(shù)組下標(biāo)下存儲(chǔ)的是一個(gè)鏈表。

Redis中的Hash字典，原理上是類似的，只是在上面包裝了一下，加了一些特有的工程信息。
主要包含三部分：字典，Hash表，Hash表節(jié)點(diǎn)

Hash表

typedef struct dictht {
  dictEntry **table; //指針數(shù)組，用于存儲(chǔ)鍵值對
  unsigned long size; //table數(shù)組的大小
  unsigned long sizemask; //掩碼 = size - 1
  unsigned long used; //table數(shù)組中已存元素個(gè)數(shù)
} dictht

這里的sizemask的用途是，某個(gè)<Kev, Value>對的數(shù)組下標(biāo)值 = Hash(Key) & sizemask。其計(jì)算結(jié)果等同于Hash(Key)%size，但是因?yàn)槭俏贿\(yùn)算，計(jì)算效率要比求余運(yùn)算快得多。

Hash表節(jié)點(diǎn)

Hash表中的元素是用dictEntry來封裝的。

typedef struct dictEntry{
  void *key;
  union {
    void *val;
    uint64_t u64;
    int64_t s64;
    double d;
  } v;
  struct dictEntry *next;
} dictEntry

簡單點(diǎn)理解就是，dictEntry里面包含了key, value，以及指向下一個(gè)dictEntry的next指針。

字典

對hash表進(jìn)行一層封裝，把一些特殊的操作封裝到字典里面，比如計(jì)算hash值，rehash等。

typedef struct dict{
  dictType *type;  //dictType里面封裝了這個(gè)字典需要的一些特殊的操作，比如計(jì)算key的hash值
  void *privatedata;  //傳給dictType里面那些操作所需的參數(shù)數(shù)據(jù)
  dictht ht[2];  //兩個(gè)hash表，大部分情況下只使用ht[0]，在擴(kuò)容的情況下需要用到另外一個(gè)
  long rehashidx;  //rehash的進(jìn)度，也就是記錄目前ht[0]這個(gè)table里面哪個(gè)數(shù)組下標(biāo)正在rehash
  unsigned long iterators; //當(dāng)前運(yùn)行的迭代器數(shù)
} dict;

所以Redis Hash字典的整個(gè)結(jié)構(gòu)圖如下：

image.png

1. 當(dāng)往Hash字典中加入<Key, Value>對時(shí)，首先在Dict的type中根據(jù)Key計(jì)算出Hash值；
2. 然后獲取dictht[0].sizemask，通過Hash(key)&dictht[0].sizemask，得到這個(gè)<Key, Value>對在dictht[0].table數(shù)組中的位置。
3. 將傳入的<Key, Value>封裝成一個(gè)新的dictEntry存入計(jì)算出來的位置。

擴(kuò)容和縮容

當(dāng)持續(xù)往字典里面添加<Key, Value>對后，字典空間慢慢會(huì)不夠，這個(gè)時(shí)候就需要擴(kuò)容。

1. 申請一塊新空間，大小為原來的兩倍，并且往上取2的N次方。比如原來字典里面的數(shù)組長度是3，擴(kuò)容的時(shí)候要申請大小為8的空間，因?yàn)?的兩倍是6，6不是2的N次方，所以往上到8;
2. 將字典的rehashidx設(shè)置為0. 并將ht[1]指向這塊擴(kuò)容后的新空間， ht[1]的size, sizemask， used都相應(yīng)的更新；
3. 所有的插入操作都rehash到ht[1]。查找，刪除，更新則兼顧ht[0]和ht[1];
4. 最后把ht[0]里面老的元素都rehash到ht[1]，rehashidx設(shè)置為正在rehash的ht[0]里面元素的下標(biāo)值；
5. 刪除ht[0]里面的元素，對調(diào)ht[0]和ht[1]，將rehashidx設(shè)置為-1；
   縮容也是類似的流程。