redis對象——5種基本類型實現(xiàn)原理

Redis主要支持的數(shù)據(jù)類型有5種：String 形帮，Hash 劲赠，List ，Set ，和 Sorted Set纱新。

redis對象

一、對象類型與編碼

1.1. realObject對象結(jié)構(gòu)

Redis使用 string list zset hash set 五大數(shù)據(jù)類型來存儲鍵和值穆趴。在每次生成一個鍵值對時脸爱，都會生成兩個對象，一個儲存鍵一個儲存值未妹。redis定義了RealObject結(jié)構(gòu)體簿废。

typedef struct redisObject {
    //類型
    unsigned type:4;
    //編碼
    unsigned encoding:4;
    /* lru time (relative to server.lruclock) */
    unsigned lru:LRU_BITS; 
    //引用計數(shù)
    int refcount;
   //指向底層實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的指針
    void *ptr;
} robj;

1.1.1. type

redis 的對象有五種類型，分別是string list zset hash set络它，type就是用來標識這五種類型的族檬。

/* Object types */
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4

注：在redis中，鍵總是一個字符串對象化戳，而值可以是字符串单料、列表埋凯、集合等對象。

1.1.2.編碼類型encoding

redis的對象的實際編碼方式由encoding參數(shù)指定扫尖，也就是ptr指針指向的數(shù)據(jù)以何種底層實現(xiàn)存放白对。

`/* Objects encoding. Some kind of objects like Strings and Hashes can be`

`* internally represented in multiple ways. The 'encoding' field of the object`

`* is set to one of this fields for this object. */`

`#define OBJ_ENCODING_RAW 0     ``/* Raw representation -- 簡單動態(tài)字符串sds*/`

`#define OBJ_ENCODING_INT 1     ``/* Encoded as integer -- long類型的整數(shù)*/`

`#define OBJ_ENCODING_HT 2      ``/* Encoded as hash table -- 字典dict*/`

`#define OBJ_ENCODING_ZIPMAP 3  ``/* Encoded as zipmap -- 3.2.5版本后不再使用 */`

`#define OBJ_ENCODING_LINKEDLIST 4 ``/* Encoded as regular linked list -- 雙向鏈表*/`

`#define OBJ_ENCODING_ZIPLIST 5 ``/* Encoded as ziplist -- 壓縮列表*/`

`#define OBJ_ENCODING_INTSET 6  ``/* Encoded as intset -- 整數(shù)集合*/`

`#define OBJ_ENCODING_SKIPLIST 7  ``/* Encoded as skiplist -- 跳表*/`

`#define OBJ_ENCODING_EMBSTR 8  ``/* Embedded sds string encoding -- embstr編碼的sds*/`

`#define OBJ_ENCODING_QUICKLIST 9 ``/* Encoded as linked list of ziplists -- 由雙端鏈表和壓縮列表構(gòu)成的高速列表*/`

可以通過 object encoding key 指令查看值對象的編碼

對象的編碼

1.1.3. 訪問時間lru

表示該對象最后一次被訪問的時間，占用24bit换怖。保存該值的目的是為了計算對象的空轉(zhuǎn)時長甩恼，便于決定是否應(yīng)該釋放該鍵。

1.1.4.引用計數(shù)refcount

c語言不具備自動內(nèi)存回手機制沉颂，所以為每個對象設(shè)定了引用計數(shù)条摸。

當創(chuàng)建一個對象時，記為1铸屉；
當被一個新的程序使用時屈溉，引用計數(shù)++；
不再被一個程序使用時抬探，引用計數(shù)--子巾；
當引用計數(shù)為0時，釋放該對象小压，回收內(nèi)存线梗。

void decrRefCount(robj *o) {
    // 引用計數(shù)為小于等于0，報錯
    if (o->refcount <= 0) serverPanic("decrRefCount against refcount <= 0");
    // 引用計數(shù)等于1怠益，減1后為0
    // 須要釋放整個redis對象
    if (o->refcount == 1) {
        switch(o->type) {
        // 依據(jù)對象類型仪搔。調(diào)用不同的底層函數(shù)對對象中存放的數(shù)據(jù)結(jié)構(gòu)進行釋放
        case OBJ_STRING: freeStringObject(o); break;
        case OBJ_LIST: freeListObject(o); break;
        case OBJ_SET: freeSetObject(o); break;
        case OBJ_ZSET: freeZsetObject(o); break;
        case OBJ_HASH: freeHashObject(o); break;
        default: serverPanic("Unknown object type"); break;
        }
        // 釋放redis對象
        zfree(o);
    } else {
        // 引用計數(shù)減1
        o->refcount--;
    }
}

1.1.5.ptr指向?qū)嶋H存放的對象

指向底層實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的指針。

二蜻牢、字符串類型

字符串是 Redis最基本的數(shù)據(jù)類型烤咧，Redis 中字符串對象的編碼可以是 int，raw 或者 embstr 中的某一種抢呆，分別介紹如下：

int 編碼：保存long 型的64位有符號整數(shù)
embstr 編碼：保存長度小于44字節(jié)的字符串
raw 編碼：保存長度大于44字節(jié)的字符串

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

編碼的好處：

其中buf[]結(jié)束并不依賴于‘\0’,使用len判斷結(jié)束煮嫌，可以保存二進制流對象。其中buf[]是一個柔性數(shù)組抱虐。
預(yù)分配昌阿，可以減少修改字符串長度增長時造成的再次分配。

2.1 OBJ_ENCODING_INT

命令示例： set foo 123

當字符串鍵值的內(nèi)容可以用一個 64位有符號整形 來表示時恳邀，Redis會將鍵值轉(zhuǎn)化為 long型來進行存儲懦冰，此時即對應(yīng) OBJ_ENCODING_INT 編碼類型。

OBJ_ENCODING_INT 編碼類型內(nèi)部的內(nèi)存結(jié)構(gòu)可以形象地表示如下：

set foo 123 時鍵值的內(nèi)存結(jié)構(gòu)

而且 Redis 啟動時會預(yù)先建立 10000 個分別存儲 0~9999 的 redisObject 變量作為共享對象谣沸，這就意味著如果 set字符串的鍵值在 0~10000 之間的話刷钢，則可以 直接指向共享對象 而不需要再建立新對象，此時鍵值不占空間乳附！

因此内地，當執(zhí)行如下指令時：

set key1 100
set key2 100

其實 key1 和 key2 這兩個鍵值都直接引用了一個 Redis 預(yù)先已建立好的共享 redisObject 對象伴澄，就像下面這樣：

共享對象

源碼之前，了無秘密瓤鼻，我們再對照下面的源碼秉版，來理解一下上述過程

INT編碼的源碼

2.2 OBJ_ENCODING_RAW

指令示例： set foo abcdefghijklmnopqrstuvwxyzabcdeffasdffsdaadsx

正如指令示例，當字符串的鍵值為長度大于 44 的 超長字符串 時茬祷，Redis 則會將鍵值的內(nèi)部編碼方式改為 OBJ_ENCODING_RAW 格式清焕，這與上面的 OBJ_ENCODING_EMBSTR 編碼方式的不同之處在于此時動態(tài)字符串 sds 的內(nèi)存與其依賴的 redisObject 的 內(nèi)存不再連續(xù) 了，以 set foo abcdefghijklmnopqrstuvwxyzabcdeffasdffsdaadsx 為例祭犯，其鍵值的內(nèi)存結(jié)構(gòu)如下所示：

set foo abcdefghijklmnopqrstuvwxyzabcdeffasdffsdaadsx時鍵值的內(nèi)存結(jié)構(gòu)

2.3 OBJ_ENCODING_EMBSTR

2.3.1 低版本redis的OBJ_ENCODING_EMBSTR字符串長度39

從Redis 3.0 版本開始秸妥，字符串引入了embstr編碼方式，長度小于OBJ_ENCONDING_EMBSTR_SIZE_LIMIT的字符串將以EMBSTR方式存儲沃粗。

EMBSTR方式的意思是 embedded string粥惧，字符串的空間由redisObject和sdshdr組成，兩者分配在同一個內(nèi)存塊中最盅。

redis中內(nèi)存分配使用的是jemalloc突雪，jemalloc分配內(nèi)存的時候是按照8,16,32,64作為塊的單位進行分配的。為了保證采用這種編碼方式的字符串能被jemalloc分配在同一個塊(chunk)中涡贱，該塊長度不能超過64咏删，故字符串長度限制OBJ_ENCONDING_EMBSTR_SIZE_LIMIT = 64 - sizeof('\0') -sizeof(robj) -sizeof(sdshdr) =64-1-16-8=39。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

這樣可以有效減少內(nèi)存分配的次數(shù)问词，提高內(nèi)存分配的效率督函，降低碎片率。

2.3.2 版本3.2之后redis的OBJ_ENCODING_EMBSTR字符串長度44

版本3.2之前激挪，sdshdr使用unsigned記錄了len和free辰狡，但對于短的sds浪費不少空間(兩個unsigned int 8個字節(jié))。

redis3.2后將單位unsigned int 變成了uint8_t（還加了一個char flags）這樣更加優(yōu)化小sds的內(nèi)存使用垄分。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

struct sdshdr8 {
    uint8_t len;
    uint8_t free;
    char flags
    char buf[];
};

sdshdr8與之前的sdshdr相比正好減少了5個字節(jié)（sdsdr8 = uint8_t * 2 + char = 1*2+1 = 3, sdshdr = unsigned int * 2 = 4 * 2 = 8）,所以其能容納的字符串長度增加了5個字節(jié)變成了44宛篇。

set foo abc時的鍵值內(nèi)存結(jié)構(gòu)

三、列表類型

列表類型內(nèi)部使用雙向鏈表實現(xiàn)锋喜。內(nèi)部數(shù)據(jù)結(jié)構(gòu)如下圖些己。

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

3.1. 編碼轉(zhuǎn)換

value對象內(nèi)部以linkedlist或者ziplist來實現(xiàn)。

3.1.1 redis3.2之前

使用ziplist（壓縮列表）編碼必須同時滿足：

當list的元素個數(shù)小于512個
單個元素的長度小于64字節(jié)

否則就會采用linkedlist（雙向鏈表）結(jié)構(gòu)嘿般。

3.1.2. redis3.2之后

鏈表完全采用quicklist。

3.2.OBJ_ENCODING_ZIPLIST

Ziplist 壓縮列表是一種緊湊編碼格式涯冠，總體思想是時間換空間炉奴，即以部分讀寫性能為代價，來換取極高的內(nèi)存空間利用率蛇更，因此只會用于 字段個數(shù)少瞻赶，且字段值也較小 的場景赛糟。

壓縮列表內(nèi)存利用率極高的原因與其連續(xù)內(nèi)存的特性是分不開的，其典型的內(nèi)存結(jié)構(gòu)可以用下圖形象地展示出來：

ZIPLIST 內(nèi)存模型

所以如果用 Ziplist來存儲 Redis的散列類型的話砸逊，元素的排列方式就變成了如下圖所示的形象示意圖：即key和value都是邏輯連續(xù)內(nèi)存：

用 Ziplist來存儲 Redis的散列類型

3.3.OBJ_ENCODING_LINKEDLIST 和 OBJ_ENCODING_QUICKLIST

在redis 3.2之前一般的鏈表采用LINKEDLIST編碼璧南。

在redis 3.2版本開始，所有的鏈表都采用QUICKLIST編碼师逸。

兩者都是使用基本的雙端鏈表數(shù)據(jù)結(jié)構(gòu)司倚，區(qū)別是QUICKLIST每個結(jié)點的值都是使用ZIPLIST進行存儲的。

// 3.2版本之前
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr篓像，void *key);
    unsigned long len;
} list;
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
// 3.2版本
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

比如动知，一個包含三個結(jié)點的quicklist，如果每個結(jié)點的ziplist又包含四個數(shù)據(jù)項员辩，那么對外表現(xiàn)上盒粮，這個list就總共包含12個數(shù)據(jù)項。這樣的設(shè)計奠滑，實際上是對于時間和空間的一種折中丹皱。

linkedlist便于在表的兩端進行push和pop操作，但是它的內(nèi)存開銷較大宋税。首先摊崭，它的每個節(jié)點除了要保存數(shù)據(jù)之外還要額外保存兩個指針；其次弃甥，雙向鏈表的各個節(jié)點是單獨的內(nèi)存塊爽室，地址不連續(xù)，容易產(chǎn)生內(nèi)存碎片淆攻，還容易造成抖動阔墩。
ziplist由于是一整塊連續(xù)的內(nèi)存，存儲效率很高瓶珊，但不利于添加和刪除操作啸箫，每次都會重新realloc，尤其是當ziplist很長的時候伞芹，一次realloc造成的開銷特別的大忘苛，查詢的開銷也特別的大。

于是quicklist集合了兩個結(jié)構(gòu)的有點唱较，但多少是合理的長度呢扎唾，redis系統(tǒng)中用戶可以自定義這個值。

`list-``max``-ziplist-``size` `-2`

這個參數(shù)可正可負南缓，取正值 n 的時候胸遇，這個正值表示的就是每個ziplist的長度最多不能超過n。

當取復(fù)制的時候只能取 -1 ~ -5 這五個值汉形，表示按照字節(jié)數(shù)來限定每個ziplist節(jié)點的長度纸镊。

-1 每個quicklist節(jié)點大小不能超過4Kb
-2 每個quicklist節(jié)點大小不能超過8Kb
-3 每個quicklist節(jié)點大小不能超過16Kb
-4 每個quicklist節(jié)點大小不能超過32Kb
-5 每個quicklist節(jié)點大小不能超過64Kb

3.3.1. 節(jié)點的壓縮

另外倍阐，quicklist的設(shè)計目標是用來存儲很長的數(shù)據(jù)鏈表的，當鏈表很長的時候逗威，最容易被訪問的是兩端的數(shù)據(jù)峰搪，中間的數(shù)據(jù)被訪問的概率比較低，如果應(yīng)用場景符合這個特點凯旭，list還提供了一個選項概耻，可以把中間的數(shù)據(jù)節(jié)點進行壓縮，而兩邊不被壓縮尽纽，參數(shù)

`list-compress-depth 0`

就是用來完成這個設(shè)置的咐蚯，數(shù)值表示兩邊不被壓縮的節(jié)點個數(shù)

其中 0 是個特殊值，表示都不壓縮弄贿，這是 redis的默認值春锋。
1表示quicklist兩端各有1個節(jié)點不壓縮，中間的節(jié)點壓縮差凹。
2表示quicklist兩端各有2個節(jié)點不壓縮期奔，中間的節(jié)點壓縮
3......
對于quicklist的壓縮算法，采用LZF---一種無損壓縮算法危尿。https://www.cnblogs.com/pengze0902/p/5998843.html

3.3.2. quicklist的數(shù)據(jù)結(jié)構(gòu)(quicklist.h)

`/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.`

`* We use bit fields keep the quicklistNode at 32 bytes.`

`* count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).`

`* encoding: 2 bits, RAW=1, LZF=2.`

`* container: 2 bits, NONE=1, ZIPLIST=2.`

`* recompress: 1 bit, bool, true if node is temporarry decompressed for usage.`

`* attempted_compress: 1 bit, boolean, used for verifying during testing.`

`* extra: 12 bits, free for future use; pads out the remainder of 32 bits */`

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

`/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.`

`* 'sz' is byte length of 'compressed' field.`

`* 'compressed' is LZF data with total (compressed) length 'sz'`

`* NOTE: uncompressed length is stored in quicklistNode->sz.`

`* When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */`

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

`/* quicklist is a 32 byte struct (on 64-bit systems) describing a quicklist.`

`* 'count' is the number of total entries.`

`* 'len' is the number of quicklist nodes.`

`* 'compress' is: -1 if compression disabled, otherwise it's the number`

`*                of quicklistNodes to leave uncompressed at ends of quicklist.`

`* 'fill' is the user-requested (or default) fill factor. */`

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklistNode結(jié)構(gòu)代表quicklist的一個節(jié)點

prev 指向前一個節(jié)點
next 指向后一個節(jié)點
zl 數(shù)據(jù)指針呐萌。如果當前節(jié)點沒有被壓縮，它指向一個ziplist谊娇；否則肺孤，它指向一個quicklistLZF結(jié)構(gòu)
sz 表示zl指向的ziplist的總大小，如果他被壓縮了济欢，那么它指壓縮前的ziplist大小赠堵。
count表示ziplist里面包含的數(shù)據(jù)項的個數(shù)，
encoding 表示ziplist是否被壓縮
container 保留字段法褥，表示一個quicklistNode是直接存數(shù)據(jù)茫叭，還是使用ziplist存數(shù)據(jù)，或者采用其他結(jié)構(gòu)類存數(shù)據(jù)半等。但是在目前實現(xiàn)中是一個固定值2揍愁，表示ziplist存數(shù)據(jù)
recompress 這個節(jié)點之前被壓縮沒有，當我們使用lindex這樣的命令查看某一項本來被壓縮的數(shù)據(jù)時杀饵，需要把數(shù)據(jù)暫時解壓莽囤，這時就設(shè)置recompress=1 做一個標記，等空閑時候再次把數(shù)據(jù)重新壓縮切距。
attemped_compress
extra 其他擴展字段目前棄用

quicklistLZF結(jié)構(gòu)表示一個被壓縮的ziplist烁登。

sz 表示壓縮后的ziplist大小
compress 柔性數(shù)組（flexible array member）存放數(shù)據(jù)壓縮后的ziplist字節(jié)數(shù)組

quicklist是真正的保存quicklist的結(jié)構(gòu)

count 所有ziplist數(shù)據(jù)項的總和
len quicklistNode節(jié)點的個數(shù)
fill ziplist大小的攝者存放 list-max-ziplist-size
compress 節(jié)點壓縮深度存放 list-compress-depth

上圖為一個quicklist結(jié)構(gòu)圖對應(yīng)的fill和compress 配置為

list-max-ziplist-size 3
list-compress-depth 2

其中左右兩端各有兩個黃色節(jié)點，是沒有被壓縮的蔚舀，他們的數(shù)據(jù)指針zl直接指向ziplist結(jié)構(gòu)饵沧。中間的藍色節(jié)點是lzf壓縮過的，zl指針指向quicklistLZF結(jié)構(gòu)赌躺。

左側(cè)頭結(jié)點上的ziplist有兩項數(shù)據(jù)狼牺，右側(cè)頭結(jié)點有1項。

3.3.3. quicklist插入

頭尾節(jié)點插入時礼患，如果對應(yīng)節(jié)點的ziplist大小沒有超過限制是钥，則新數(shù)據(jù)直接被插入對應(yīng)ziplist；如果超過限制缅叠，那么新建一個quicklistNode節(jié)點悄泥，把待插入節(jié)點插入新的ziplist中。
如果插入的位置是鏈表中間部分肤粱，當插入位置所在的ziplist沒達到大小限制弹囚，直接插入對應(yīng)ziplist；
當所在的ziplist大小超過了限制领曼，但插入的位置在ziplist兩端鸥鹉，如果相鄰節(jié)點的ziplist沒有超過大小限制，那么就插入相鄰節(jié)點
如果相鄰節(jié)點的大小超過了限制庶骄，那么新建一個quicklistNode毁渗，插入對應(yīng)節(jié)點
對其他情況，需要吧當前ziplist分裂成兩個節(jié)點单刁，然后在其中一個節(jié)點中插入數(shù)據(jù)灸异。

可參見http://www.reibang.com/p/0df2b3cb749f

四、hash類型

hash類型

4.1.hash的數(shù)據(jù)結(jié)構(gòu)

map提供兩種結(jié)構(gòu)來存儲：

hashtable
ziplist

4.2.編碼轉(zhuǎn)換

同時滿足以下兩個條件羔飞，使用ziplist編碼：

鍵值對的鍵和值字符串長度小于64字節(jié)
鍵值對數(shù)量小于512個

否則使用hashtable肺樟。

這里成員"較少"，成員值"較小"的標準可以通過如下配置項進行配置：

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

Redis 默認給出了默認值褥傍，當然用戶可根據(jù)實際情況自行配置儡嘶。

4.3.OBJ_ENCODING_ZIPLIST

同上

4.3.OBJ_ENCODING_HT

OBJ_ENCODING_HT 這種編碼方式內(nèi)部才是真正的哈希表結(jié)構(gòu)，或稱為字典結(jié)構(gòu)恍风，其可以實現(xiàn)O(1)復(fù)雜度的讀寫操作蹦狂，因此效率很高。

在 Redis內(nèi)部朋贬，從 OBJ_ENCODING_HT類型到底層真正的散列表數(shù)據(jù)結(jié)構(gòu)是一層層嵌套下去的凯楔，關(guān)系如下：

Redis哈希嵌套關(guān)系

這一關(guān)系我們可以從 Redis哈希表定義部分的源碼來看出：

image

下面來詳解一下各個部分：

關(guān)于哈希節(jié)點（dictEntry）

dictEntry

關(guān)于哈希表（dictht）和字典（dict）

dictht 和 dict

關(guān)于dictType

dictType

Redis如何計算Hash值

Redis計算Hash的源代碼如下：

計算Hash值

這是一個 C語言宏定義，其實幕后真正承擔 Hash值計算的是上面介紹的 dictType結(jié)構(gòu)體中的函數(shù)指針 hashFunction锦募。

而該 hashFunction函數(shù)指針在初始化時會對應(yīng)被賦值為一個個真實的計算 Hash值的實際函數(shù)摆屯，就像下面這樣：

hashFunction 函數(shù)指針賦值

Redis如何計算存取索引Index值

Index值的計算依賴于上面計算得出的 Hash值，代碼如下：

Redis計算索引Index值的源碼

五、集合類型

不能有重復(fù)數(shù)據(jù)虐骑，
同時集合類型中的數(shù)據(jù)是無序的
集合類型和列表類型的最大的區(qū)別是
- 有序性
  - 列表有序
- 唯一性
  - 集合唯一
使用的值為空的散列表(hash table)准验，
- 所以這些操作的時間復(fù)雜度都是O(1).

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

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

intset
hashtable

5.2.編碼轉(zhuǎn)換

同時滿足以下兩個條件，使用intset編碼：

集合所有元素為整型
集合元素數(shù)量小于512個
否則使用hashtable編碼廷没。

5.3 OBJ_ENCODING_INTSET

redis中使用intset實現(xiàn)數(shù)量較少數(shù)字的set糊饱。

set-max-intset-entries 512

實際上 intset是一個由整數(shù)組成的有序集合，為了快速查找元素颠黎，數(shù)組是有序的另锋，用二分查找判斷一個元素是否在這個結(jié)合上。在內(nèi)存分配上與ziplist類似狭归，用一塊連續(xù)的內(nèi)存保存數(shù)組元素夭坪，并且對于大整數(shù)和小證書采用了不同的編碼。

結(jié)構(gòu)如下

//intset.h
typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

encoding 數(shù)據(jù)編碼表示intset中的每個元素用幾個字節(jié)存儲过椎。(INTSET_ENC_INT16 用兩個字節(jié)存儲室梅，即兩個contents數(shù)組位置 INTSET_ENC_INT32表示4個字節(jié) INTSET_ENC_INT64表示8個字節(jié))

length 表示inset中元素的個數(shù)

contents 柔性數(shù)組，表示存儲的實際數(shù)據(jù)潭流，數(shù)組長度 = encoding * length竞惋。
另外，intset可能會隨著數(shù)據(jù)的添加改編他的編碼灰嫉，最開始創(chuàng)建的inset使用 INTSET_ENC_INT16編碼拆宛。如果要添加的元素編碼比當前intset的編碼大。調(diào)用intsetUpgradeAndAdd將intset的編碼進行增長讼撒，然后插入浑厚。

如上圖 intset采用小端存儲。

5.4 OBJ_ENCODING_HT

同上

六根盒、有序集合

有序集合類型為集合中的每個元素都關(guān)聯(lián)了一個分數(shù)

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

ziplist
skiplist+hashtable來實現(xiàn)

跳躍表是一種隨機化的數(shù)據(jù)結(jié)構(gòu)
在查找钳幅、插入和刪除這些字典操作上
其效率可比擬于平衡二叉樹（如紅黑樹）

6.2.編碼轉(zhuǎn)換

同時滿足以下兩個條件，使用ziplist編碼：

有序集合所有元素成員長度小于64字節(jié)
有序集合元素數(shù)量小于128個
否則使用skiplist編碼炎滞。

6.3. OBJ_ENCODING_ZIPLIST

同上

6.4. OBJ_ENCODING_SKIPLIST

redis里面是用skiplist是為了實現(xiàn)zset這種對外的數(shù)據(jù)結(jié)構(gòu)敢艰。zset提供的操作非常豐富，可以滿足許多業(yè)務(wù)場景册赛，同時也意味著zset相對來說實現(xiàn)比較復(fù)雜钠导。

6.4.1. skiplist數(shù)據(jù)結(jié)構(gòu)簡介

如圖，跳表的底層是一個順序鏈表森瘪，每隔一個節(jié)點有一個上層的指針指向下下一個節(jié)點牡属，并層層向上遞歸。這樣設(shè)計成類似樹形的結(jié)構(gòu)扼睬，可以使得對于鏈表的查找可以到達二分查找的時間復(fù)雜度逮栅。

按照上面的生成跳表的方式上面每一層節(jié)點的個數(shù)是下層節(jié)點個數(shù)的一半，這種方式在插入數(shù)據(jù)的時候有很大的問題。就是插入一個新節(jié)點會打亂上下相鄰兩層鏈表節(jié)點個數(shù)嚴格的2:1的對應(yīng)關(guān)系措伐。如果要維持這種嚴格對應(yīng)關(guān)系特纤，就必須重新調(diào)整整個跳表，這會讓插入/刪除的時間復(fù)雜度重新退化為O(n)废士。

為了解決這一問題叫潦，skiplist他不要求上下兩層鏈表之間個數(shù)的嚴格對應(yīng)關(guān)系，他為每個節(jié)點隨機出一個層數(shù)官硝。比如，一個節(jié)點的隨機出的層數(shù)是3短蜕，那么就把它插入到三層的空間上氢架，如下圖。

那么朋魔，這就產(chǎn)生了一個問題岖研，每次插入節(jié)點時隨機出一個層數(shù)，真的能保證跳表良好的性能能么?

首先跳表隨機數(shù)的產(chǎn)生警检，不是一次執(zhí)行就產(chǎn)生的孙援，他有自己嚴格的計算過程，

首先每個節(jié)點都有最下層(第1層)指針
如果一個節(jié)點有第i層指針扇雕，那么他有第i層指針的概率為p拓售。
節(jié)點的最大層數(shù)不超過MaxLevel

我們注意到，每個節(jié)點的插入過程都是隨機的镶奉，他不依賴于其他節(jié)點的情況础淤，即skiplist形成的結(jié)構(gòu)和節(jié)點插入的順序無關(guān)。

這樣形成的skiplist查找的時間復(fù)雜度約為O(log n)哨苛。