Redis數(shù)據(jù)結(jié)構(gòu)中鏈表與字典的使用案例

這篇文章主要介紹了Redis數(shù)據(jù)結(jié)構(gòu)中鏈表與字典的使用案例，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

鏈表

關(guān)于鏈表的基礎(chǔ)概念其實(shí)你在學(xué)習(xí)Redis之前一定積累了不少，所以本文將默認(rèn)你已經(jīng)掌握了鏈表相關(guān)的基礎(chǔ)知識(shí)，而Redis的鏈表其實(shí)也就是普通的鏈表~

因?yàn)镽edis是使用C語(yǔ)言編寫的，因此Redis的數(shù)據(jù)結(jié)構(gòu)的定義都是使用C語(yǔ)法定義的，你不需要完全理解下方C語(yǔ)言聲明結(jié)構(gòu)體的語(yǔ)法，但我認(rèn)為依靠大家的Java知識(shí)也能理解這就像是在Java中定義了一個(gè)鏈表對(duì)象

Redis鏈表節(jié)點(diǎn)的結(jié)構(gòu)

typedef struct listNode {
	struct listNode *prev;	//指向前一個(gè)鏈表節(jié)點(diǎn)
	struct listNode *next;	//指向后一個(gè)鏈表節(jié)點(diǎn)
	void *value;			//當(dāng)前節(jié)點(diǎn)的值(可以按需設(shè)定不同數(shù)據(jù)類型的value)
} listNode;

很明顯，當(dāng)每一個(gè)節(jié)點(diǎn)內(nèi)記錄了前后兩個(gè)節(jié)點(diǎn)位置之后，鏈表節(jié)點(diǎn)之間就能夠彼此前后相連，組成雙向通行車道（可以雙向遍歷）

Redis鏈表的表示

上面講解了Redis的鏈表的節(jié)點(diǎn)表示，并由此引申了一下可以借此構(gòu)建Redis雙端鏈表，而事實(shí)上，對(duì)于每一個(gè)存在的雙端鏈表，Redis使用一個(gè)list結(jié)構(gòu)來表示

typedef struct list {
	listNode *head;			//表頭節(jié)點(diǎn)
	listNode *tail;			//表尾節(jié)點(diǎn)
	unsigned long len;		//鏈表所包含的節(jié)點(diǎn)的數(shù)量
	void *(*dup)(void *ptr);	//節(jié)點(diǎn)復(fù)制函數(shù)
	void (*free)(void *ptr);	//節(jié)點(diǎn)釋放函數(shù)
	void (*match)(void *ptr, void *key);//節(jié)點(diǎn)值對(duì)比函數(shù)
} list;

很明顯，你看到三個(gè)好像是返回值為void的函數(shù)，但是看不懂C語(yǔ)法，沒關(guān)系，傳統(tǒng)后端功夫，自然是點(diǎn)到為止

Redis鏈表用在哪

我不想現(xiàn)在就告訴你，鏈表被廣泛用于實(shí)現(xiàn)Redis的各種功能，比如列表鍵、發(fā)布于訂閱、慢查詢、監(jiān)視器等，等我們后面講到這幾部分的時(shí)候，白澤再結(jié)合鏈表和你細(xì)說~

字典

和鏈表一樣，Redis所使用的C語(yǔ)言并沒有內(nèi)置字典這種數(shù)據(jù)結(jié)構(gòu)，因此Redis構(gòu)建了自己的字典實(shí)現(xiàn)。如果你學(xué)過數(shù)據(jù)結(jié)構(gòu)，你會(huì)發(fā)現(xiàn)Redis的字典事實(shí)上就是數(shù)據(jù)結(jié)構(gòu)中的鄰接表，即使沒學(xué)過，往下看就好啦~

Redis字典結(jié)構(gòu)總覽

數(shù)組 + 鏈表 ==> 鄰接表，實(shí)錘

Redis字典結(jié)構(gòu)分解

還記得嗎，上面我們說Redis鏈表可以用list描述，但是鏈表存儲(chǔ)的數(shù)據(jù)本質(zhì)上，是由一系列l(wèi)istNode節(jié)點(diǎn)通過前后指針相連存儲(chǔ)的；類似的，Redis字典可以用如下dict描述，但是字典存儲(chǔ)的數(shù)據(jù)本質(zhì)上，是由數(shù)組 + 若干鏈表組合得到的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的，字典dict結(jié)構(gòu)如下：

typedef struct dict {
	dictType *type;			//類型特定函數(shù)
	void *privdata;			//私有數(shù)據(jù)
	dictht ht[2];			//哈希表數(shù)組
	int trehashidx;			//rehash索引，當(dāng)rehash不在進(jìn)行時(shí)，值為-1
} dict;

現(xiàn)在你只需要關(guān)注其中的哈希表數(shù)組ht[2]，它的數(shù)據(jù)類型為dictht，因此也是一種復(fù)合的數(shù)據(jù)結(jié)構(gòu)，如下：

typedef struct dictht {
	dictEntry **table;		//哈希表數(shù)組
	unsigned long size;		//哈希表大小
	unsigned long sizemax;	//哈希表大小掩碼，用于計(jì)算索引值，等于size - 1
	unsigned long used;		//該哈希表已有節(jié)點(diǎn)的數(shù)量
} dictht;

哈希表dictht是Redis字典的核心，dictht的四個(gè)屬性中，size、sizemax、used都是用于描述table屬性整體狀態(tài)?？吹竭@你就明白了，dictht的核心是dictEntry類型的table屬性（再次提醒，如果沒有C語(yǔ)言的基礎(chǔ)，本文中一切你看不懂的語(yǔ)法，包括數(shù)據(jù)類型，你只需要一眼帶過即可，我們的目的是學(xué)習(xí)Redis的設(shè)計(jì)思想）

table屬性是一個(gè)數(shù)組，數(shù)組中的每個(gè)元素都是一個(gè)指向dictEntry結(jié)構(gòu)的指針，每個(gè)dictEntry結(jié)構(gòu)保存一個(gè)鍵值對(duì)，并含有一個(gè)指向下一個(gè)dictEntry的指針，結(jié)構(gòu)如下：

typedef struct dictEntry {
	void *key;	//鍵
	union {		//值（可以是一個(gè)指針，可以是一個(gè)uint64_t類型的整數(shù)，也可以是一個(gè)int64_t類型的整數(shù)）
		void *val;
		uint64_t u64;
		int64_t s64;
	} v;
	struct dictEntry *next;//指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
} dictEntry;

哈希算法

我們知道，字典是用來存儲(chǔ)數(shù)據(jù)的，并且是以鍵值對(duì)的形式存儲(chǔ)的，那么我每次存入一個(gè)鍵值對(duì)放在字典的哪里？這就是哈希算法為你解決的事情：程序需要先根據(jù)鍵值對(duì)的鍵計(jì)算出哈希值和索引值，然后再根據(jù)索引值，將包含新鍵值對(duì)的哈希表節(jié)點(diǎn)放到哈希表數(shù)組的指定索引上面

比如我已經(jīng)有下面這個(gè)字典，然后要插入一個(gè)鍵值對(duì)數(shù)據(jù)：k1 : v1，則程序有如下計(jì)算過程：（用戶只是往Redis服務(wù)器中插入了一條數(shù)據(jù)，下面都是程序內(nèi)部的工作~）

hash = dict->type->hashFunction(k1);		//計(jì)算k1鍵的hash值（得到某個(gè)數(shù)值）
index = hash & dict->ht[0].sizemask = 1;	//計(jì)算k1鍵插入位置的索引值

解決鍵沖突

鍵沖突：當(dāng)不同的key值計(jì)算得到的dictEntry索引值相同時(shí)，就稱發(fā)生鍵沖突（我要插入的位置已經(jīng)被占用了，插入使得鏈表長(zhǎng)度由1變多，當(dāng)然第一次插入不算沖突）

解決方法：

就像上面我要插入一個(gè)k1 ：v1的鍵值對(duì)，并計(jì)算得到插入位置的索引為1（但是distEntry數(shù)組中索引為1的位置已經(jīng)有k0 ：v0鍵值對(duì)存放了），因此程序會(huì)在哈希表ht[0]的dictEntry數(shù)組的索引為1的位置上插入一個(gè)dictEntry節(jié)點(diǎn)，放在原本鏈表首部的前一位置（搶占首位），其中存放著k1 ： v1鍵值對(duì)，插入后的圖如下：

你可能疑惑新插入的鍵值對(duì)的位置在每個(gè)dictEntry鏈表的最前面，而不是尾部，原因是每個(gè)dictEntry中除了保存鍵值對(duì)之外，只記錄了下一個(gè)dictEntry的地址（上面我已經(jīng)給出了dictEntry的結(jié)構(gòu)了~），程序無(wú)法直接得到dictEntry鏈表的最后一個(gè)節(jié)點(diǎn)，但可以直接得到第一個(gè)節(jié)點(diǎn)（通過dictEntry數(shù)組索引直接定位），因此每次插入的dictEntry節(jié)點(diǎn)（鍵值對(duì)）都將直接插入到對(duì)應(yīng)索引的鏈表的頭部（因此dictEntry數(shù)組的內(nèi)容是不斷在變的）

一句話來說：distEntry數(shù)組幫助使用索引定位，distEntry鏈表，用于處理沖突，不斷維護(hù)所存儲(chǔ)的鍵值對(duì)數(shù)據(jù)

rehash

隨著操作的不斷執(zhí)行（增、刪、改、查），哈希表保存的鍵值對(duì)會(huì)逐漸增多或者減少，為了讓哈希表的負(fù)載因子維持在一個(gè)合理范圍內(nèi)，當(dāng)哈希表保存的鍵值對(duì)數(shù)量太多或太少時(shí)，程序會(huì)對(duì)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者收縮（不知道你是否記得還有一個(gè)哈希表ht[1]的存在，這個(gè)表就是為了和ht[0]配合進(jìn)行rehash而存在的）

rehash步驟：

為字典的ht[1]哈希表分配空間

如果程序執(zhí)行擴(kuò)展操作：

ht[1].size = 第一個(gè)大于等于ht[0].used * 2（ht[0]已經(jīng)使用的空間大小乘2）的2的n次方冪

如果程序執(zhí)行收縮操作：

ht[1].size = 第一個(gè)大于等于ht[0].used（ht[0]已經(jīng)使用的空間大小）的2的n次方冪

將保存在ht[0]上的鍵值對(duì)rehash到ht[1]上，因?yàn)閟ize不同，所以是重新hash，而不是整體復(fù)制

當(dāng)ht[0]內(nèi)鍵值對(duì)全部遷移到ht[1]中后，釋放ht[0]，然后將ht[1]和ht[0]的互換（rehash結(jié)束），此時(shí)ht[0]就是一個(gè)rehash后的哈希表，而ht[1]依舊為空表，為下次rehash做準(zhǔn)備

漸進(jìn)式rehash

上面提到的在哈希表ht[0]的負(fù)載因子過大或者過小會(huì)觸發(fā)rehash，但是，事實(shí)上rehash遷移的過程不是一蹴而就的（很明顯，如果數(shù)據(jù)ht[0]的數(shù)據(jù)很多，每次rehash如果都遷移全部數(shù)據(jù)，需要花費(fèi)較大時(shí)間等待，用戶在rehash期間訪問Redis服務(wù)器將會(huì)陷入無(wú)響應(yīng)的狀態(tài)）

漸進(jìn)式過程：

將rehash的過程分?jǐn)傇诤罄m(xù)的每次增、刪、改、查操作上，在rehash期間，每次對(duì)字典執(zhí)行操作，程序除了執(zhí)行指定操作外，還會(huì)順帶將ht[0]哈希表在rehashidx索引（從0開始，-1表示rehash未開始）上的所有鍵值對(duì)rehash到ht[1]，當(dāng)每次局部rehash工作完成后，程序?qū)ehashidx屬性的值增一

注意：每次對(duì)字典進(jìn)行增、刪、改、查會(huì)在ht[0]和ht[1]上同時(shí)進(jìn)行，比如查找一個(gè)鍵，則會(huì)現(xiàn)在ht[0]上查找，沒找到再去ht[1]上查找，諸如此類，除了增加操作每次都將直接hash到ht[1]上，不會(huì)對(duì)ht[0]執(zhí)行任何添加操作

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Redis數(shù)據(jù)結(jié)構(gòu)中鏈表與字典的使用案例”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!