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