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