面試官:說說Redis的Hash底層 我:……(來自閱文的面試題)

3{icon} {views}

redis源碼分析系列文章

[Redis源碼系列]在Liunx安裝和常見API 

為什麼要從Redis源碼分析 

String底層實現——動態字符串SDS 

Redis的雙向鏈表一文全知道

前言

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

 

今天要寫Redis的Hash類型,如果有對Redis不熟悉,或者對其他數據類型感興趣的,可以移步上面的系列文章。(最上面的最上面最上面,重要的事情說三遍)

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

API使用

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

插入數據hset

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

獲取數據hget

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

獲取所有數據hgetall

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

獲取所有key

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

獲取長度

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

獲取所有value

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

具體邏輯圖

hash的底層主要是採用字典dict的結構,整體呈現層層封裝。

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

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

最後數據節點,和上篇說的雙向鏈表一樣,每個節點都有next指針,方便指向下一個節點,這樣目的是為了解決hash碰撞。具體的可以看下圖。

這邊看不懂沒關係,後面會針對每個模塊詳細說明。(千萬不要看到這裏就跳過啦)

雙向鏈表的定義

字典結構體dict

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

具體代碼如下:

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

 

數組結構體dictht

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

具體代碼如下:

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

 

數據節點dictEntry

dictEntry為真正的數據節點,包括key,value和next節點。

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

 

 

 

擴容過程和漸進式Hash圖解

我們先來第一個部分,dictht[2]為什麼會要2個數組存放,真正的數據只要一個數組就夠了?

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

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

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

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

步驟1

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

步驟2

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

 

步驟3

key為name,value為張三的節點移動結束后,繼續移動第一個數組dictht[0]的下標為0的後續節點,移動步驟和上面相同。

步驟4

繼續移動第一個數組dictht[0]的下標為0的後續節點都移動完了,開始移動下標為1的節點,發現其沒有數據,所以移動下標為2的節點,同時修改rehashidx為2,移動步驟和上面相同。

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

停止之後如果對該對象進行操作,那是什麼樣子的呢?

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

字典的實現(源碼分析)

創建並初始化字典

首先分配內存,接着調用初始化方法_dictInit,主要是賦值操作,重點看下rehashidx賦值為-1(這驗證了剛才的圖解,-1表示未進行hash擴容),最後返回是否創建成功。

/* 創建並初始化字典 */
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裏面有一個靜態方法_dictExpandIfNeed,判斷是否需要擴容。

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

接着判斷第一個數組的size是否為0,如果為0,則擴容為默認大小4,如果不為0,則執行下面的代碼。

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

最後就是調用dictExpand擴容方法了,參數為數據節點的雙倍大小ht[0].used*2。此處驗證了上面擴容過程的數組大小16。

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

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

擴容流程圖

具體代碼:

static int _dictExpandIfNeeded(dict *d)
{
    //判斷是否處於擴容狀態中,通過調用宏常量#define dictIsRehashing(d) ((d)->rehashidx != -1)
    //來判斷是否可以擴容
    if (dictIsRehashing(d)) return DICT_OK;

    //判斷第一個數組size是否為0,如果為0,則調用擴容方法,大小為宏常量
    //#define DICT_HT_INITIAL_SIZE     4
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    //下面先列出if條件中所使用到的參數 
    // static int dict_can_resize = 1;數值為1表示可以擴容
    //static unsigned int dict_force_resize_ratio = 5;
    //我們來分析if條件,如果第一個數組的所有節點數量大於等於第一個數組的大小(表示節點數據已經有些多)
    //並且可用擴容(數值為1)或者所有節點數量除以數組大小大於5
    //這個條件表示擴容那個的條件,第一個就是節點必要大於等於數組長度,
    //第二點就再可以擴容和數據太多,超過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的倍數
    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的倍數 */
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過程已經通過上面圖解說明,以下主要看下代碼是如何實現的,以及過程是不是對的。

擴容之後就是執行dictRehash方法,參數包括待移動的哈希表d和步驟数字n。

首先判斷標誌量rehashidx是否等於-1,如果等於-1,則表示hash完成,如果不等於-1,則執行下面的代碼。

接着進行循環,遍歷第一個數組上的每個下標,每次移動下標位置,都需要更新rehashidx值,每次加1。

再接着進行第二個循環,遍歷下標的鏈表每個節點,完成數據的遷移,主要是指針的移動和一些參數的修改。

最後,返回int數值,如果為0表示整個數據全部hash完成,如果返回1則表示部分hash結束,並沒有全部完成,下次可以通過rehashidx值繼續hash。

具體代碼如下:

//重新hash這個哈希表
 // Redis的哈希表結構公有兩個table數組,t0和t1,平常只使用一個t0,當需要重hash時則重hash到另一個table數組中
 //參數列表
 // 1. d: 待移動的哈希表,結構中存有目前已經重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]還有沒有移動的節點 
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        //第一個循環用來更新 rehashidx 的值,因為有些桶為空,所以 rehashidx並非每次都比原來前進一個位置,而是有可能前進幾個位置,但最多不超過 10。
        //將rehashidx移動到ht[0]有節點的下標,也就是table[d->rehashidx]非空
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];  //第二個循環用來將ht[0]表中每次找到的非空桶中的鏈表(或者就是單個節點)拷貝到ht[1]中

        /* 利用循環講數據節點移過去 */
        while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            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數據類型的底層實現字典結構Dict,先從Hash的一些API使用,引出字典結構Dict,剖析了其三個主要組成部分,字典結構體Dict,數組結構體Dictht,數據節點結構體DictEntry,進而通過多幅過程圖解釋了擴容過程和rehash過程,最後結合源碼對字典進行描述,如創建過程,擴容過程,漸進式hash過程,中間穿插流程圖講解。

如果覺得寫得還行,麻煩給個贊,您的認可才是我寫作的動力!

如果覺得有說的不對的地方,歡迎評論指出。

好了,拜拜咯。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※想知道最厲害的網頁設計公司"嚨底家"!

※別再煩惱如何寫文案,掌握八大原則!

※產品缺大量曝光嗎?你需要的是一流包裝設計!