Redis Set 用了兩種數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)，到現(xiàn)在才知道
Sets 無序集合，他的功能就好像你熟悉的 Java 中的 HashSet 一樣。集合是通過散列表實(shí)現(xiàn)的，所以添加、刪除、查找元素的時(shí)間復(fù)雜度是 O(1)。
1. 是什么
Sets 是 String 類型的無序集合，集合中的元素是唯一的，集合中不會(huì)出現(xiàn)重復(fù)的數(shù)據(jù)。
Java 的 HashSet 底層是用 HashMap 實(shí)現(xiàn)，Sets 的底層數(shù)據(jù)結(jié)構(gòu)也是用 Hashtable（散列表）實(shí)現(xiàn)，散列表的 key 存的是 Sets 集合元素的 value，散列表的 value 則指向 NULL。
不同的是，當(dāng)元素內(nèi)容都是 64 位以內(nèi)的十進(jìn)制整數(shù)的時(shí)候，并且元素個(gè)數(shù)不超過 set-max-intset-entries 配置的值（默認(rèn) 512）的時(shí)候，會(huì)使用更加省內(nèi)存的 intset（整形數(shù)組）來存儲(chǔ)。
圖2-15
使用場(chǎng)景
當(dāng)你需要存儲(chǔ)多個(gè)元素，并且要求不能出現(xiàn)重復(fù)數(shù)據(jù)，無需考慮元素的有序時(shí)，就可以使用 Sets 來存儲(chǔ)，這樣能利用我對(duì)單個(gè)元素操作 O(1) 時(shí)間復(fù)雜度帶來的性能優(yōu)勢(shì)。
并且 Sets 還支持在集合之間做交集、并集、差集操作，比如當(dāng)你遇到如下場(chǎng)景，需要統(tǒng)計(jì)多個(gè)集合元素的聚合結(jié)果。
- 統(tǒng)計(jì)多個(gè)元素的共有數(shù)據(jù)（交集）。
- 統(tǒng)計(jì)兩個(gè)集合其中的一個(gè)獨(dú)有元素（差集統(tǒng)計(jì)）。
- 統(tǒng)計(jì)多個(gè)集合的所有元素（并集統(tǒng)計(jì)）。
常見的使用場(chǎng)景。
- 社交軟件中共同關(guān)注，通過交集實(shí)現(xiàn)。
- 每日新增關(guān)注數(shù)，只需要對(duì)近兩天的總注冊(cè)用戶量集合取差集即可。
- 打標(biāo)簽：比如微信收藏功能，你可以為自己收藏的每一篇文章打標(biāo)簽，這樣你可以快速的找到被添加了某個(gè)標(biāo)簽的所有文章。
2. 修煉心法
關(guān)于散列表結(jié)構(gòu)我會(huì)在專門的章節(jié)介紹，先看 intset 結(jié)構(gòu)，結(jié)構(gòu)體定義在源碼 intset.h中。
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;- length，記錄整數(shù)集合存儲(chǔ)的元素個(gè)數(shù)，其實(shí)就是 contents 數(shù)組的長(zhǎng)度。
- contents，真正存儲(chǔ)整數(shù)集合的數(shù)組，是一塊連續(xù)內(nèi)存區(qū)域。每個(gè)元素都是數(shù)組的一個(gè)數(shù)組元素，數(shù)組中的元素會(huì)按照值的大小從小到大有序排列存儲(chǔ)，并且不會(huì)有重復(fù)元素。
- encoding，編碼格式，決定數(shù)組類型，一共有三種不同的值。
- INTSET_ENC_INT16，表示 contents 數(shù)組的存儲(chǔ)元素是 int16_t 類型，每 2 字節(jié)表示一個(gè)整數(shù)元素。
- INTSET_ENC_INT32，表示 contents 數(shù)組的存儲(chǔ)元素是 int32_t 類型，每 4 字節(jié)表示一個(gè)元素。
- INTSET_ENC_INT64，表示 contents 數(shù)組的存儲(chǔ)元素是 int64_t 類型，每 8 字節(jié)表示一個(gè)元素。
圖2-16
MySQL：“如果在一個(gè) int16_t 類型的整數(shù)集合中插入一個(gè) int64_t 類型的值會(huì)怎樣？”
這個(gè)問題問得好，下次可以繼續(xù)保持。
這種情況會(huì)觸發(fā)整數(shù)集合升級(jí)，也就是集合的所有元素都會(huì)轉(zhuǎn)換成 int64_t 類型，步驟如下。
- 根據(jù)新元素的類型，以及集合元素的數(shù)量，包括新添加的元素在內(nèi)，計(jì)算新的空間大小，對(duì)底層數(shù)組空間擴(kuò)容，進(jìn)行空間重新分配。
- 將數(shù)組原有的元素都轉(zhuǎn)換成新元素類型，把轉(zhuǎn)換后的元素按照從大到小的順序放到正確的位置上，需要保證數(shù)組元素的有序性。
- 修改 encoding 的值，length + 1。
所以每次向整形數(shù)組集合添加新元素都可能會(huì)引起升級(jí)，升級(jí)又會(huì)對(duì)原始數(shù)據(jù)進(jìn)行類型轉(zhuǎn)換，時(shí)間復(fù)雜度是 O(N)。
MySQL：“如果刪除剛剛添加的 int64_t 類型元素，會(huì)執(zhí)行降級(jí)操作么?”
整形數(shù)組不支持降級(jí)操作。
MySQL：“Sets 是無序集合，為何存儲(chǔ)整形數(shù)字的場(chǎng)景下 contents 數(shù)組元素需要有序？”
為了查詢?cè)厮俣?，?shù)組有序我就能使用二分法來提高查詢效率。insetFind() 函數(shù)返回值等于 0 表示集合中沒有目標(biāo)數(shù)據(jù)，反之 1 存在目標(biāo)數(shù)據(jù)。方法的內(nèi)部會(huì)調(diào)用 intsetSearch() 函數(shù)使用二分法來實(shí)現(xiàn)。
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
int64_t cur = -1;
// 省略一些檢查代碼
while(max >= min) {
mid = ((unsigned int)min + (unsigned int)max) >> 1;
cur = _intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value < cur) {
max = mid-1;
} else {
break;
}
}
// 修改 pos 指針
if (value == cur) {
if (pos) *pos = mid;
return 1;
} else {
if (pos) *pos = min;
return 0;
}
}pos 指針的作用有兩個(gè)，如果查找到目標(biāo)值， pos 記錄目標(biāo)值的位置；查找不到目標(biāo)值，pos 記錄的就是這個(gè)目標(biāo)值插入到 intset 的位置。
3. 出招實(shí)戰(zhàn)：共同好友
三國(guó)天下有限公司開發(fā)了一個(gè)名叫“三國(guó)戀”的社交 APP，想要實(shí)現(xiàn)共同好友功能，這個(gè)場(chǎng)景就能使用集合交集來實(shí)現(xiàn)。為每個(gè)用戶創(chuàng)建一個(gè) Sets 集合，賬號(hào)名作為集合的 key，集合 value 存儲(chǔ)該賬號(hào)的好友。
如下指令構(gòu)建劉備和曹操的好友集合。
SADD user:劉備 趙子龍 張飛 關(guān)羽 貂蟬
SADD user:曹操 貂蟬 夏侯惇 典韋 張遼想要知道兩個(gè)人的共同好友，也就是兩個(gè)集合的交集，只需要使用 SINTERSTORE指令。
SINTERSTORE user:曹劉好友 user:劉備 user:曹操命令執(zhí)行后，劉備與曹操兩個(gè)集合的交集數(shù)據(jù)就存儲(chǔ)到了“user:曹劉好友”集合中。使用 SMEMBERS 查看曹操與劉備的共同好友。
redis> SMEMBERS user:曹劉好友
1) "貂蟬"好家伙，他們都喜歡貂蟬，你喜不喜歡呢？
