# 集合
[TOC=2,3]
`REDIS_SET` （集合）是 [SADD](http://redis.readthedocs.org/en/latest/set/sadd.html#sadd "(in Redis 命令參考 v2.8)") 、 [SRANDMEMBER](http://redis.readthedocs.org/en/latest/set/srandmember.html#srandmember "(in Redis 命令參考 v2.8)") 等命令的操作對象，它使用 `REDIS_ENCODING_INTSET` 和 `REDIS_ENCODING_HT` 兩種方式編碼：
![digraph redis_set { node [shape=plaintext, style = filled]; edge [style = bold]; // type REDIS_SET [label="集合\nREDIS_SET", fillcolor = "#95BBE3"]; // encoding REDIS_ENCODING_INTSET [label="intset\nREDIS_ENCODING_INTSET", fillcolor = "#FADCAD"]; REDIS_ENCODING_HT [label="字典\nREDIS_ENCODING_HT", fillcolor = "#FADCAD"]; // edge REDIS_SET -> REDIS_ENCODING_INTSET; REDIS_SET -> REDIS_ENCODING_HT; // datastruct 1 intset [label="intset.h/intset"]; REDIS_ENCODING_INTSET -> intset; // datastruct 2 dict [label="dict.h/dict"]; REDIS_ENCODING_HT -> dict;}](https://box.kancloud.cn/2015-09-13_55f4effcd9127.svg)
### 編碼的選擇
第一個添加到集合的元素，決定了創建集合時所使用的編碼：
- 如果第一個元素可以表示為 `long long` 類型值（也即是，它是一個整數）， 那么集合的初始編碼為 `REDIS_ENCODING_INTSET` 。
- 否則，集合的初始編碼為 `REDIS_ENCODING_HT` 。
### 編碼的切換
如果一個集合使用 `REDIS_ENCODING_INTSET` 編碼，那么當以下任何一個條件被滿足時，這個集合會被轉換成 `REDIS_ENCODING_HT` 編碼：
- `intset` 保存的整數值個數超過 `server.set_max_intset_entries` （默認值為 `512` ）。
- 試圖往集合里添加一個新元素，并且這個元素不能被表示為 `long long` 類型（也即是，它不是一個整數）。
### 字典編碼的集合
當使用 `REDIS_ENCODING_HT` 編碼時，集合將元素保存到字典的鍵里面，而字典的值則統一設為 `NULL` 。
作為例子，以下圖片展示了一個以 `REDIS_ENCODING_HT` 編碼表示的集合，集合的成員為 `elem1` 、 `elem2` 和 `elem3` ：
![digraph hash_table_example { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes ht1 [label="<dictht>dictht |<table> table | size:4 | sizemask:3 | used:3", fillcolor = "#A8E270"]; bucket [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 ", fillcolor = "#95BBE3"]; pair_1 [label="<head>dictEntry |{<key>key\nelem1 |<value>value\nNULL |<next>next\nNULL}", fillcolor = "#FADCAD"]; pair_2 [label="<head>dictEntry |{<key>key\nelem2 |<value>value\nNULL |<next>next\nNULL}", fillcolor = "#FADCAD"]; pair_3 [label="<head>dictEntry |{<key>key\nelem3 |<value>value\nNULL |<next>next\nNULL}", fillcolor = "#FADCAD"]; null1 [label="NULL", shape=plaintext]; // lines ht1:table -> bucket:head; bucket:table0 -> pair_1:head; bucket:table1 -> null1; bucket:table2 -> pair_2:head; bucket:table3 -> pair_3:head;}](https://box.kancloud.cn/2015-09-13_55f4effce3008.svg)
### 集合命令的實現
Redis 集合類型命令的實現，主要是對 `intset` 和 `dict` 兩個數據結構的操作函數的包裝，以及一些在兩種編碼之間進行轉換的函數，大部分都沒有什么需要解釋的地方，唯一比較有趣的是 [SINTER](http://redis.readthedocs.org/en/latest/set/sinter.html#sinter "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/set/sinter.html#sinter] 、 [SUNION](http://redis.readthedocs.org/en/latest/set/sunion.html#sunion "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/set/sunion.html#sunion] 等命令之下的算法實現，以下三個小節就分別討論它們所使用的算法。
### 求交集算法
[SINTER](http://redis.readthedocs.org/en/latest/set/sinter.html#sinter "(in Redis 命令參考 v2.8)") 和 [SINTERSTORE](http://redis.readthedocs.org/en/latest/set/sinterstore.html#sinterstore "(in Redis 命令參考 v2.8)") 兩個命令所使用的求并交集算法可以用 Python 表示如下：
~~~
# coding: utf-8
def sinter(*multi_set):
# 根據集合的基數進行排序
sorted_multi_set = sorted(multi_set, lambda x, y: len(x) - len(y))
# 使用基數最小的集合作為基礎結果集，有助于降低常數項
result = sorted_multi_set[0].copy()
# 剔除所有在 sorted_multi_set[0] 中存在
# 但在其他某個集合中不存在的元素
for elem in sorted_multi_set[0]:
for s in sorted_multi_set[1:]:
if (not elem in s):
result.remove(elem)
break
return result
~~~
算法的復雜度為 \(O(N^2)\) ，執行步數為 \(S * T\) ，其中 \(S\) 為輸入集合中基數最小的集合，而 \(T\) 則為輸入集合的數量。
### 求并集算法
[SUNION](http://redis.readthedocs.org/en/latest/set/sunion.html#sunion "(in Redis 命令參考 v2.8)") 和 [SUNIONSTORE](http://redis.readthedocs.org/en/latest/set/sunionstore.html#sunionstore "(in Redis 命令參考 v2.8)") 兩個命令所使用的求并集算法可以用 Python 表示如下：
~~~
# coding: utf-8
def sunion(*multi_set):
result = set()
for s in multi_set:
for elem in s:
# 重復的元素會被自動忽略
result.add(elem)
return result
~~~
算法的復雜度為 \(O(N)\) 。
### 求差集算法
Redis 為 [SDIFF](http://redis.readthedocs.org/en/latest/set/sdiff.html#sdiff "(in Redis 命令參考 v2.8)") 和 [SDIFFSTORE](http://redis.readthedocs.org/en/latest/set/sdiffstore.html#sdiffstore "(in Redis 命令參考 v2.8)") 兩個命令準備了兩種求集合差的算法。
以 Python 代碼表示的算法一定義如下：
~~~
# coding: utf-8
def sdiff_1(*multi_set):
result = multi_set[0].copy()
sorted_multi_set = sorted(multi_set[1:], lambda x, y: len(x) - len(y))
# 當 elem 存在于除 multi_set[0] 之外的集合時
# 將 elem 從 result 中刪除
for elem in multi_set[0]:
for s in sorted_multi_set:
if elem in s:
result.remove(elem)
break
return result
~~~
這個算法的復雜度為 \(O(N^2)\) ，執行步數為 \(S*T\) ，其中 \(S\) 為輸入集合中基數最小的集合，而 \(T\) 則為除第一個集合之外，其他集合的數量。
以 Python 代碼表示的算法二定于如下：
~~~
# coding: utf-8
def sdiff_2(*multi_set):
# 用第一個集合作為結果集的起始值
result = multi_set[0].copy()
for s in multi_set[1:]:
for elem in s:
# 從結果集中刪去其他集合中包含的元素
if elem in result:
result.remove(elem)
return result
~~~
這個算法的復雜度同樣為 \(O(N^2)\) ，執行步數為 \(S\) ，其中 \(S\) 為所有集合的基數總和。
Redis 使用一個程序決定該使用那個求差集算法，程序用 Python 表示如下：
~~~
# coding: utf-8
from sdiff_1 import sdiff_1
from sdiff_2 import sdiff_2
def sdiff(*multi_set):
# 算法一的常數項較低，給它一點額外的優先級
algo_one_advantage = 2
algo_one_weight = len(multi_set[0]) * len(multi_set[1:]) / algo_one_advantage
algo_two_weight = sum(map(len, multi_set))
if algo_one_weight <= algo_two_weight:
return sdiff_1(*multi_set)
else:
return sdiff_2(*multi_set)
~~~
