本文轉(zhuǎn)載自微信公眾號(hào)「學(xué)習(xí)Java的小姐姐」，作者學(xué)習(xí)Java的小姐姐0618 。轉(zhuǎn)載本文請(qǐng)聯(lián)系學(xué)習(xí)Java的小姐姐公眾號(hào)。

[[332012]]

前言

hello，各位小可愛們，又見面了。今天這篇文章來(lái)自去年面試閱文的面試題，結(jié)果被虐了。這一part不說(shuō)了，下次專門開一篇，寫下我面試被虐的名場(chǎng)面，尷尬的不行，全程尬聊。哈哈哈哈，話不多說(shuō)，開始把。😂

 

在Redis中Hash類型的應(yīng)用非常廣泛，其中key到value的映射就通過(guò)字典結(jié)構(gòu)來(lái)維護(hù)的。記筆記，此處要考。

 

API使用

API的使用比較簡(jiǎn)單，所以以下就粗略的寫了。

插入數(shù)據(jù)hset

使用hset命令往myhash中插入兩個(gè)key，value的鍵值對(duì)，分別是(name,zhangsan)和(age,20)，返回值當(dāng)前的myhash的長(zhǎng)度。

 

獲取數(shù)據(jù)hget

使用hget命令獲取myhash中key為name的value值。

 

獲取所有數(shù)據(jù)hgetall

使用hgetall命令獲取myhash中所有的key和value值。

 

獲取所有key

使用hkeys命令獲取myhash中所有的key值。

 

獲取長(zhǎng)度

使用hlen命令獲取myhash的長(zhǎng)度。

 

獲取所有value

使用hvals命令獲取myhash中所有的value值。

 

具體邏輯圖

正文要開始了哈。hash的底層主要是采用字典dict的結(jié)構(gòu)，整體呈現(xiàn)層層封裝。

 

首先dict有四個(gè)部分組成，分別是dictType(類型，不咋重要),dictht(核心)，rehashidx(漸進(jìn)式hash的標(biāo)志)，iterators(迭代器)，這里面最重要的就是dictht和rehashidx。

接下來(lái)是dictht，其有兩個(gè)數(shù)組構(gòu)成，一個(gè)是真正的數(shù)據(jù)存儲(chǔ)位置，還有一個(gè)用于hash過(guò)程，包括的變量分別是真正的數(shù)據(jù)table和一些常見變量。

最后數(shù)據(jù)節(jié)點(diǎn)，和上篇說(shuō)的雙向鏈表一樣，每個(gè)節(jié)點(diǎn)都有next指針，方便指向下一個(gè)節(jié)點(diǎn)，這樣目的是為了解決hash碰撞。具體的可以看下圖。

這邊看不懂沒(méi)關(guān)系，后面會(huì)針對(duì)每個(gè)模塊詳細(xì)說(shuō)明。(千萬(wàn)不要看到這里就跳過(guò)啦)

 

雙向鏈表的定義

字典結(jié)構(gòu)體dict

我們先看字典結(jié)構(gòu)體dict，其包括四個(gè)部分，重點(diǎn)是dictht[2](真正的數(shù)據(jù))和rehashidx(漸進(jìn)式hash的標(biāo)志)。具體圖如下。

 

具體代碼如下：

//字典結(jié)構(gòu)體 
typedef struct dict { 
dictType *type;//類型，包括一些自定義函數(shù)，這些函數(shù)使得key和value能夠存儲(chǔ) 
void *privdata;//私有數(shù)據(jù) 
dictht ht[2];//兩張hash表 
long rehashidx; //漸進(jìn)式hash標(biāo)記，如果為-1，說(shuō)明沒(méi)在進(jìn)行hash 
unsigned long iterators; //正在迭代的迭代器數(shù)量 
} dict; 

數(shù)組結(jié)構(gòu)體dictht

dictht主要包括四個(gè)部分，1是真正的數(shù)據(jù)dictEntry類型的數(shù)組，里面存放的是數(shù)據(jù)節(jié)點(diǎn);2是數(shù)組長(zhǎng)度size;3是進(jìn)行hash運(yùn)算的參數(shù)sizemask，這個(gè)不咋重要，只要記住等于size-1;4是數(shù)據(jù)節(jié)點(diǎn)數(shù)量used，當(dāng)前有多少個(gè)數(shù)據(jù)節(jié)點(diǎn)。

 

具體代碼如下：

//hash結(jié)構(gòu)體 
typedef struct dictht { 
dictEntry **table;//真正數(shù)據(jù)的數(shù)組 
unsigned long size;//數(shù)組的大小 
unsigned long sizemask;//用戶將hash映射到table的位置索引，他的值總是等于size-1 
unsigned long used;//已用節(jié)點(diǎn)數(shù)量 
} dictht; 

數(shù)據(jù)節(jié)點(diǎn)dictEntry

dictEntry為真正的數(shù)據(jù)節(jié)點(diǎn)，包括key，value和next節(jié)點(diǎn)。

//每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)體 
typedef struct dictEntry { 
   void *key; //key 
   union { 
          void *val; 
          uint64_t u64; 
          int64_t s64; 
          double d; 
   } v;//value 
  struct dictEntry *next; //下一個(gè)數(shù)據(jù)節(jié)點(diǎn)的地址 
} dictEntry; 

擴(kuò)容過(guò)程和漸進(jìn)式Hash圖解

我們先來(lái)第一個(gè)部分，dictht[2]為什么會(huì)要2個(gè)數(shù)組存放，真正的數(shù)據(jù)只要一個(gè)數(shù)組就夠了?

 

這其實(shí)和Java的HashMap相似，都是數(shù)據(jù)加鏈表的結(jié)構(gòu)，隨著數(shù)據(jù)量的增加，hash碰撞發(fā)生的就越頻繁，每個(gè)數(shù)組后面的鏈表就越長(zhǎng)，整個(gè)鏈表顯得非常累贅。如果業(yè)務(wù)需要大量查詢操作，因?yàn)槭擎湵恚荒軓念^部開始查詢，等一個(gè)數(shù)組的鏈表全部查詢完才能開始下一個(gè)數(shù)組，這樣查詢時(shí)間將無(wú)限拉長(zhǎng)。

這無(wú)疑是要進(jìn)行擴(kuò)容，所以第一個(gè)數(shù)組存放真正的數(shù)據(jù)，第二個(gè)數(shù)組用于擴(kuò)容用。第一個(gè)數(shù)組中的節(jié)點(diǎn)經(jīng)過(guò)hash運(yùn)算映射到第二個(gè)數(shù)組上，然后依次進(jìn)行。那么過(guò)程中還能對(duì)外提供服務(wù)嗎?答案是可以的，因?yàn)樗梢噪S時(shí)停止，這就到了下一個(gè)變量rehashidx。(一點(diǎn)都不生硬的轉(zhuǎn)場(chǎng)，哈哈哈）

 

rehashidx其實(shí)是一個(gè)標(biāo)志量，如果為-1說(shuō)明當(dāng)前沒(méi)有擴(kuò)容，如果不為-1則表示當(dāng)前擴(kuò)容到哪個(gè)下標(biāo)位置，方便下次進(jìn)行從該下標(biāo)位置繼續(xù)擴(kuò)容。

 

這樣說(shuō)是不是太抽象了，還是一臉懵逼，貼心的送上擴(kuò)容過(guò)程全解，一定要點(diǎn)贊評(píng)論多夸夸我哦。

 

步驟1

首先是未擴(kuò)容前，rehashidx為-1，表示未擴(kuò)容，第一個(gè)數(shù)組的dictEntry長(zhǎng)度為4，一共有5個(gè)節(jié)點(diǎn)，所以u(píng)sed為5。

 

步驟2

當(dāng)發(fā)生擴(kuò)容了，rahashidx為第一個(gè)數(shù)組的第一個(gè)下標(biāo)位置，即0。擴(kuò)容之后的大小為大于used*2的2的n次方的最小值，即能包含這些節(jié)點(diǎn)*2的2的倍數(shù)的最小值。因?yàn)楫?dāng)前為5個(gè)數(shù)據(jù)節(jié)點(diǎn)，所以u(píng)sed*2=10，擴(kuò)容后的數(shù)組大小為大于10的2的次方的最小值，為16。從第一個(gè)數(shù)組0下標(biāo)位置開始，查找第一個(gè)元素，找到key為name，value為張三的節(jié)點(diǎn)，將其hash過(guò)，找到在第二個(gè)數(shù)組的下標(biāo)為1的位置，將節(jié)點(diǎn)移過(guò)去，其實(shí)是指針的移動(dòng)。這邊就簡(jiǎn)單說(shuō)了。

 

步驟3

key為name，value為張三的節(jié)點(diǎn)移動(dòng)結(jié)束后，繼續(xù)移動(dòng)第一個(gè)數(shù)組dictht[0]的下標(biāo)為0的后續(xù)節(jié)點(diǎn)，移動(dòng)步驟和上面相同。

 

步驟4

繼續(xù)移動(dòng)第一個(gè)數(shù)組dictht[0]的下標(biāo)為0的后續(xù)節(jié)點(diǎn)都移動(dòng)完了，開始移動(dòng)下標(biāo)為1的節(jié)點(diǎn)，發(fā)現(xiàn)其沒(méi)有數(shù)據(jù)，所以移動(dòng)下標(biāo)為2的節(jié)點(diǎn)，同時(shí)修改rehashidx為2，移動(dòng)步驟和上面相同。

 

整個(gè)過(guò)程的重點(diǎn)在于rehashidx，其為第一個(gè)數(shù)組正在移動(dòng)的下標(biāo)位置，如果當(dāng)前內(nèi)存不夠，或者操作系統(tǒng)繁忙，擴(kuò)容的過(guò)程可以隨時(shí)停止。

停止之后如果對(duì)該對(duì)象進(jìn)行操作，那是什么樣子的呢?

• 如果是新增，則直接新增后第二個(gè)數(shù)組，因?yàn)槿绻略龅降谝粋€(gè)數(shù)組，以后還是要移過(guò)來(lái)，沒(méi)必要浪費(fèi)時(shí)間
• 如果是刪除，更新，查詢，則先查找第一個(gè)數(shù)組，如果沒(méi)找到，則再查詢第二個(gè)數(shù)組。

字典的實(shí)現(xiàn)(源碼分析)

創(chuàng)建并初始化字典

首先分配內(nèi)存，接著調(diào)用初始化方法_dictInit，主要是賦值操作，重點(diǎn)看下rehashidx賦值為-1(這驗(yàn)證了剛才的圖解，-1表示未進(jìn)行hash擴(kuò)容)，最后返回是否創(chuàng)建成功。

/* 創(chuàng)建并初始化字典 */ 
dict *dictCreate(dictType *type,void *privDataPtr) 
{ 
     dict *d = zmalloc(sizeof(*d)); 
     _dictInit(d,type,privDataPtr); 
     return d; 
} 
 
/* Initialize the hash table */ 
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;//賦值為-1，表示未進(jìn)行hash 
     d->iterators = 0; 
return DICT_OK; 
} 

擴(kuò)容

dict里面有一個(gè)靜態(tài)方法_dictExpandIfNeed，判斷是否需要擴(kuò)容。

首先判斷通過(guò)dictIsRehashing方法，判斷是否處于hash狀態(tài)，其調(diào)用的是宏常量#define dictIsRehashing(d) ((d)->rehashidx != -1)，即判斷rehashidx是否為-1，如果為-1，即不處于hash狀態(tài)，if條件為false，可以進(jìn)行擴(kuò)容，如果不為-1，即處于hash狀態(tài)，if條件為true，不可以進(jìn)行擴(kuò)容，直接返回常量DICT_OK。

接著判斷第一個(gè)數(shù)組的size是否為0，如果為0，則擴(kuò)容為默認(rèn)大小4，如果不為0，則執(zhí)行下面的代碼。

再接著判斷是否需要擴(kuò)容，if中有三個(gè)條件，具體的分析如下。

最后就是調(diào)用dictExpand擴(kuò)容方法了，參數(shù)為數(shù)據(jù)節(jié)點(diǎn)的雙倍大小ht[0].used*2。此處驗(yàn)證了上面擴(kuò)容過(guò)程的數(shù)組大小16。

擴(kuò)容方法比較簡(jiǎn)單點(diǎn)，獲取擴(kuò)容后的大小，將第二個(gè)設(shè)置新的大小。

這樣講感覺(jué)有點(diǎn)空，看下流程圖。

擴(kuò)容流程圖

 

具體代碼：

static int _dictExpandIfNeeded(dict *d) 
{ 
      //判斷是否處于擴(kuò)容狀態(tài)中，通過(guò)調(diào)用宏常量#define                                                  
      dictIsRehashing(d) ((d)->rehashidx != -1) 
      //來(lái)判斷是否可以擴(kuò)容 
      if (dictIsRehashing(d)) return DICT_OK; 
 
      //判斷第一個(gè)數(shù)組size是否為0,如果為0，則調(diào)用擴(kuò)容方法，大小為宏常量 
      //#define DICT_HT_INITIAL_SIZE 4 
      if (d->ht[0].size == 0)  
             return dictExpand(d, DICT_HT_INITIAL_SIZE); 
 
      //下面先列出if條件中所使用到的參數(shù) 
      // static int dict_can_resize = 1;數(shù)值為1表示可以擴(kuò)容 
      //static unsigned int dict_force_resize_ratio = 5; 
      //我們來(lái)分析if條件，如果第一個(gè)數(shù)組的所有節(jié)點(diǎn)數(shù)量大于等于第一個(gè)數(shù)組的大小（表      示節(jié)點(diǎn)數(shù)據(jù)已經(jīng)有些多） 
      //并且可用擴(kuò)容（數(shù)值為1）或者所有節(jié)點(diǎn)數(shù)量除以數(shù)組大小大于5 
      //這個(gè)條件表示擴(kuò)容那個(gè)的條件，第一個(gè)就是節(jié)點(diǎn)必要大于等于數(shù)組長(zhǎng)度， 
      //第二點(diǎn)就再可以擴(kuò)容和數(shù)據(jù)太多，超過(guò)5兩個(gè)中選其一 
      if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize || 
      d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) 
      { 
            //調(diào)用擴(kuò)容方法 
            return dictExpand(d, d->ht[0].used*2); 
      } 
return DICT_OK; 
} 
 
int dictExpand(dict *d, unsigned long size) 
{ 
      dictht n; 
      //獲取擴(kuò)容后真正的大小，找到比size大的最小值，且是2的倍數(shù) 
      unsigned long realsize = _dictNextPower(size); 
 
      //一些判斷條件 
      if (dictIsRehashing(d) || d->ht[0].used > size) 
            return DICT_ERR; 
 
      if (realsize == d->ht[0].size) return DICT_ERR; 
 
      n.size = realsize; 
      n.sizemask = realsize-1; 
      n.table = zcalloc(realsize*sizeof(dictEntry*)); 
      n.used = 0; 
 
      //第一個(gè)hash為null，說(shuō)明在初始化 
      if (d->ht[0].table == NULL) { 
            d->ht[0] = n; 
      return DICT_OK; 
      } 
 
      //正在hash，給第二個(gè)hash的長(zhǎng)度設(shè)置新的， 
      d->ht[1] = n; 
      d->rehashidx = 0;//設(shè)置當(dāng)前正在hash 
return DICT_OK; 
} 
 
/* 找到比size大的最小值，且是2的倍數(shù) */ 
static unsigned long _dictNextPower(unsigned long size) 
{ 
      unsigned long i = DICT_HT_INITIAL_SIZE; 
 
      if (size >= LONG_MAX) return LONG_MAX; 
      while(1) { 
            if (i >= size) 
                  return i; 
      i *= 2; 
      } 
} 

漸進(jìn)式hash

漸進(jìn)式hash過(guò)程已經(jīng)通過(guò)上面圖解說(shuō)明，以下主要看下代碼是如何實(shí)現(xiàn)的，以及過(guò)程是不是對(duì)的。

擴(kuò)容之后就是執(zhí)行dictRehash方法，參數(shù)包括待移動(dòng)的哈希表d和步驟數(shù)字n。

首先判斷標(biāo)志量rehashidx是否等于-1，如果等于-1，則表示hash完成，如果不等于-1，則執(zhí)行下面的代碼。

接著進(jìn)行循環(huán)，遍歷第一個(gè)數(shù)組上的每個(gè)下標(biāo)，每次移動(dòng)下標(biāo)位置，都需要更新rehashidx值，每次加1。

再接著進(jìn)行第二個(gè)循環(huán)，遍歷下標(biāo)的鏈表每個(gè)節(jié)點(diǎn)，完成數(shù)據(jù)的遷移，主要是指針的移動(dòng)和一些參數(shù)的修改。

最后，返回int數(shù)值，如果為0表示整個(gè)數(shù)據(jù)全部hash完成，如果返回1則表示部分hash結(jié)束，并沒(méi)有全部完成，下次可以通過(guò)rehashidx值繼續(xù)hash。

具體代碼如下：

     //重新hash這個(gè)哈希表 
// Redis的哈希表結(jié)構(gòu)共有兩個(gè)table數(shù)組，t0和t1，平常只使用一個(gè)t0，當(dāng)需要重hash時(shí)則重hash到另一個(gè)table數(shù)組中 
//參數(shù)列表 
// 1. d: 待移動(dòng)的哈希表，結(jié)構(gòu)中存有目前已經(jīng)重hash到哪個(gè)桶了 
// 2. n: N步進(jìn)行rehash 
// 返回值 返回0說(shuō)明整個(gè)表都重hash完成了，返回1代表未完成 
int dictRehash(dict *d, int n) { 
      int empty_visits = n*10; 
      //如果當(dāng)前rehashidx=-1,則返回0，表示hash完成 
      if (!dictIsRehashing(d)) return 0; 
      //分n步，而且ht[0]還有沒(méi)有移動(dòng)的節(jié)點(diǎn) 
      while(n-- && d->ht[0].used != 0) { 
            dictEntry *de, *nextde; 
            assert(d->ht[0].size > (unsigned long)d->rehashidx); 
            //第一個(gè)循環(huán)用來(lái)更新 rehashidx 的值，因?yàn)橛行┩盀榭?，所?nbsp;rehashidx并非每次都比原來(lái)前進(jìn)一個(gè)位置，而是有可能前進(jìn)幾個(gè)位置，但最多不超過(guò) 10。 
            //將rehashidx移動(dòng)到ht[0]有節(jié)點(diǎn)的下標(biāo)，也就是table[d->rehashidx]非空 
      while(d->ht[0].table[d->rehashidx] == NULL) { 
            d->rehashidx++; 
            if (--empty_visits == 0) return 1; 
      } 
     //第二個(gè)循環(huán)用來(lái)將ht[0]表中每次找到的非空桶中的鏈表（或者就是單個(gè)節(jié)點(diǎn)）拷貝到ht[1]中 
      de = d->ht[0].table[d->rehashidx];  
 
     /* 利用循環(huán)將數(shù)據(jù)節(jié)點(diǎn)移過(guò)去 */ 
     while(de) { 
          unsigned int h; 
 
          nextde = de->next; 
          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++; 
    } 
 
     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; 
} 
 
return 1; 
} 

總結(jié)

 

該篇主要講了Redis的Hash數(shù)據(jù)類型的底層實(shí)現(xiàn)字典結(jié)構(gòu)Dict，先從Hash的一些API使用，引出字典結(jié)構(gòu)Dict，剖析了其三個(gè)主要組成部分，字典結(jié)構(gòu)體Dict，數(shù)組結(jié)構(gòu)體Dictht，數(shù)據(jù)節(jié)點(diǎn)結(jié)構(gòu)體DictEntry，進(jìn)而通過(guò)多幅過(guò)程圖解釋了擴(kuò)容過(guò)程和rehash過(guò)程，最后結(jié)合源碼對(duì)字典進(jìn)行描述，如創(chuàng)建過(guò)程，擴(kuò)容過(guò)程，漸進(jìn)式hash過(guò)程，中間穿插流程圖講解。