Redis資料結構（二）字典

redis字典其實就是hash表，其實作和java語言中的hashmap結構大同小異，按key-value方式存儲鍵值對，但是又存在一定的差異。

java中的hashmap結構即包含hash表，又實作了rehash自我擴充；

而redis字典則通過dictht結構實作hash表，通過字典（dict）實作rehash（字典中包含一個dictht數組dictht ht[2]）。

redis字典的實作

redis字典所使用的哈希表由dict.h/dictht結構定義：

table為一個dictentry結構的數組，每個dictentry結構儲存着一個key-value對。size為table數組的大小（注意不是key-value對的個數）；used才是key-value對的個數；sizemask為size-1，用途後面會提到；

dictentry結構定義如下：

key即為鍵，v即為值，由定義可以看出，v既可以是一個指針，也可以是一個uint64_t整數或者int64_t整數。

next屬性指向下一個dictentry，形成連結清單結構。在字典結構中，每一個key-value中的key的hash值映射到table的下标，如果有多個key的hash值映射到table的同一個下标，則這些key-value對将通過 next指針形成一個連結清單，存到table的目前下标中。

redis中的字典由dict.h/dict結構表示：

注意到，其中：

dictht即為前面介紹的哈希表結構；

type指針為一個dicttype結構，該結構儲存了一些用于操作特定類型鍵值對的函數，redis會為用途不同的字典設定不同的類型特定函數；

privdata則儲存了需要傳遞給type中特定函數的可選參數；

dicttype結構如下：

ht數組則包含2個dictht結構，平時隻使用ht[0]，在rehash的時候使用ht[1]；

rehashidx則為一個标志位，如果目前沒有在進行rehash，則值為-1；redis通過漸進方式進行rehash，rehash期間，每執行一次操作，則rehashidx值加1；

redis雜湊演算法

（未完待續。。。）