本文轉載自微信公眾號「學習Java的小姐姐」，作者學習Java的小姐姐0618 。轉載本文請聯(lián)系學習Java的小姐姐公眾號。

[[332012]]

前言

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

 

在Redis中Hash類型的應用非常廣泛，其中key到value的映射就通過字典結構來維護的。記筆記，此處要考。

 

API使用

API的使用比較簡單，所以以下就粗略的寫了。

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

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

 

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

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

 

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

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

 

獲取所有key

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

 

獲取長度

使用hlen命令獲取myhash的長度。

 

獲取所有value

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

 

具體邏輯圖

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

 

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

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

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

這邊看不懂沒關系，后面會針對每個模塊詳細說明。(千萬不要看到這里就跳過啦)

 

雙向鏈表的定義

字典結構體dict

我們先看字典結構體dict，其包括四個部分，重點是dictht[2](真正的數(shù)據(jù))和rehashidx(漸進式hash的標志)。具體圖如下。

 

具體代碼如下：

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

數(shù)組結構體dictht

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

 

具體代碼如下：

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

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

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

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

擴容過程和漸進式Hash圖解

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

 

這其實和Java的HashMap相似，都是數(shù)據(jù)加鏈表的結構，隨著數(shù)據(jù)量的增加，hash碰撞發(fā)生的就越頻繁，每個數(shù)組后面的鏈表就越長，整個鏈表顯得非常累贅。如果業(yè)務需要大量查詢操作，因為是鏈表，只能從頭部開始查詢，等一個數(shù)組的鏈表全部查詢完才能開始下一個數(shù)組，這樣查詢時間將無限拉長。

這無疑是要進行擴容，所以第一個數(shù)組存放真正的數(shù)據(jù)，第二個數(shù)組用于擴容用。第一個數(shù)組中的節(jié)點經(jīng)過hash運算映射到第二個數(shù)組上，然后依次進行。那么過程中還能對外提供服務嗎?答案是可以的，因為他可以隨時停止，這就到了下一個變量rehashidx。(一點都不生硬的轉場，哈哈哈）

 

rehashidx其實是一個標志量，如果為-1說明當前沒有擴容，如果不為-1則表示當前擴容到哪個下標位置，方便下次進行從該下標位置繼續(xù)擴容。

 

這樣說是不是太抽象了，還是一臉懵逼，貼心的送上擴容過程全解，一定要點贊評論多夸夸我哦。

 

步驟1

首先是未擴容前，rehashidx為-1，表示未擴容，第一個數(shù)組的dictEntry長度為4，一共有5個節(jié)點，所以used為5。

 

步驟2

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

 

步驟3

key為name，value為張三的節(jié)點移動結束后，繼續(xù)移動第一個數(shù)組dictht[0]的下標為0的后續(xù)節(jié)點，移動步驟和上面相同。

 

步驟4

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

 

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

停止之后如果對該對象進行操作，那是什么樣子的呢?

• 如果是新增，則直接新增后第二個數(shù)組，因為如果新增到第一個數(shù)組，以后還是要移過來，沒必要浪費時間
• 如果是刪除，更新，查詢，則先查找第一個數(shù)組，如果沒找到，則再查詢第二個數(shù)組。

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

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

首先分配內存，接著調用初始化方法_dictInit，主要是賦值操作，重點看下rehashidx賦值為-1(這驗證了剛才的圖解，-1表示未進行hash擴容)，最后返回是否創(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，表示未進行hash 
     d->iterators = 0; 
return DICT_OK; 
} 

擴容

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

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

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

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

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

擴容方法比較簡單點，獲取擴容后的大小，將第二個設置新的大小。

這樣講感覺有點空，看下流程圖。

擴容流程圖

 

具體代碼：

static int _dictExpandIfNeeded(dict *d) 
{ 
      //判斷是否處于擴容狀態(tài)中，通過調用宏常量#define                                                  
      dictIsRehashing(d) ((d)->rehashidx != -1) 
      //來判斷是否可以擴容 
      if (dictIsRehashing(d)) return DICT_OK; 
 
      //判斷第一個數(shù)組size是否為0,如果為0，則調用擴容方法，大小為宏常量 
      //#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表示可以擴容 
      //static unsigned int dict_force_resize_ratio = 5; 
      //我們來分析if條件，如果第一個數(shù)組的所有節(jié)點數(shù)量大于等于第一個數(shù)組的大?。ū?nbsp;     示節(jié)點數(shù)據(jù)已經(jīng)有些多） 
      //并且可用擴容（數(shù)值為1）或者所有節(jié)點數(shù)量除以數(shù)組大小大于5 
      //這個條件表示擴容那個的條件，第一個就是節(jié)點必要大于等于數(shù)組長度， 
      //第二點就再可以擴容和數(shù)據(jù)太多，超過5兩個中選其一 
      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; 
} 
 
int dictExpand(dict *d, unsigned long size) 
{ 
      dictht n; 
      //獲取擴容后真正的大小，找到比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; 
 
      //第一個hash為null，說明在初始化 
      if (d->ht[0].table == NULL) { 
            d->ht[0] = n; 
      return DICT_OK; 
      } 
 
      //正在hash，給第二個hash的長度設置新的， 
      d->ht[1] = n; 
      d->rehashidx = 0;//設置當前正在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; 
      } 
} 

漸進式hash

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

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

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

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

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

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

具體代碼如下：

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

總結

 

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