Question

Set

set 是指数学名词“集合”。在这裡我们只考虑元素为整数的集合。集合有几点特性：

一、空集合。

二、集合中的元素不会重複。

Set 资料结构: 循序储存

Array

要表达一个集合，可以直观的用一条一维的 int 阵列：将集合裡的所有元素，依序放进阵列中。再用一个变数，记录元素总数。

如果你对 C++ STL 很熟，用 vector 就更方便了！

然而，以这种资料结构，做联集、交集、差集之类的运算，则会相当麻烦，也会比较慢。各位可以自己试试看！

可以直接使用 STL 的 set_union()、set_intersection()。

UVa 496 12069

List

原理就和 Array 完全一样。Array 是一个一个数字连著放，List 则是一个一个数字连成串。

Binary Search Tree

只要是可以储存大量数字的资料结构，都可以用来储存一个集合。因此二元搜寻树当然也能胜任这项任务！

可以直接使用 STL 的 set，不过它没有联集、交集、差集等功能，必须自己另外设计程式码。也许你内心有点芥蒂；没错，STL 的 set，的确是名不符实的 set。

Set 资料结构: 索引储存

Array

另外一种表达集合的方法，是用一条一维的 bool 阵列：集合裡若有 x 这个元素，就让 array[x]这个位置为 true，否则为 false。

它的坏处就是数值有界限、受阵列大小影响。但是，以这种资料结构，做联集、交集、差集之类的运算，则会比较快，时间複杂度为 O(阵列大小)。

Set 资料结构: Hash Table

Hash Function【这不是资料结构】

int hash(一笔资料) {return 一个数值;}

一笔资料重新表示成一个数值。该数值称作杂凑值。

资料库的观点：资料进行索引，以利管理。密码学的观点：资料进行编码，以求隐蔽。

理想情况是相同资料有著相同杂凑值、相异资料有著相异杂凑值，如此就能直接使用杂凑值来分辨资料。

可以直接使用 STL 的 hash。

Hashing【这不是资料结构】

array[ hash(一笔资料) ] = 一笔资料;

繁中“杂凑”，简中“散列”。一笔资料套用 hash function 得到杂凑值，作为阵列索引值，用阵列储存资料。设计 hash function 时，必须确保杂凑值不会超出阵列边界。

无论是相同资料、相异资料，只要有著相同杂凑值，就会储存到阵列的同一个格子。此时有三种应对方案：

一、每个阵列元素皆改为 List，串接资料。

二、放到下一格；如果下一格已经使用，就再往下一格。

三、新资料直接覆盖旧资料。

此处以一为主。插入的时间複杂度是 O(1)。删除、搜寻的最佳时间複杂度是 O(1)，相异资料有著相异杂凑值；最差时间複杂度是 O(N)，相异资料有著相同杂凑值。

Hash Table

当元素的数值范围很大，甚至元素不是整数，此时可以利用 hash function 得到一个索引值，而不会超出阵列边界。

数值范围小，索引储存是首选，省时间费空间；数值范围大，循序储存是首选，省空间费时间。hash table 两者兼具，介于中间。

可以直接使用 STL 的 unordered_set、unordered_multiset。

Cuckoo Filter

建立多个 hash function。当阵列格子已有资料，就换 hash function、换杂凑值。

有兴趣的读者，可以自行上网搜寻资料。

Bloom Filter

套用多个 hash function，同时储存于多个栏位，分散风险。只要发现对应栏位几乎都是 1，就推定元素存在于集合当中。缺点是可能制造原本不存在的元素。

如果懒得设计 hash function，可以用两个凑出多个：hashi(n) = hash1(n) + i * hash2(n)。关键字 Kirsch-Mitzenmacher。

有兴趣的读者，可以自行上网搜寻资料。

Disjoint Sets

Disjoint Sets

“互斥集”的意思是一堆集合们，大家拥有的元素都不相同，也就是说这些集合们之间都没有交集。

A = {1, 3, 7, 8}
B = {4, 5}
C = {2}
A、B、C 构成 Disjoint sets。

D = {1, 2, 3}
A、B、C、D 不是 Disjoint sets。

举例来说，有十个学生，要制作分组报告，分成四组，这四组就是 Disjoint sets。

甲君、乙君、丙君、丁君、戊君、己君、庚君、辛君、壬君、癸君
共十人，分成了四组：

第一组：甲君、丙君、辛君、壬君
第二组：乙君
第三组：丁君、戊君、己君
第四组：庚君、癸君

这四组构成 Disjoint sets。

union、find、split

由于集合们都没有交集，因此诸如交集运算、差集运算等等结果很明显的运算，就不必特别说明。这裡只谈 union、find、split 这三个运算：union 就是将两个集合做联集，合併成一个集合。find 就是找找看一个元素是在哪个集合裡面。split 就是把一个集合拆成两个集合。

以下只谈 union、find，暂不介绍 split。

Disjoint Sets 资料结构: List

Disjoint-sets List

其原理正是先前介绍的“循序储存”。

Disjoint Sets 资料结构: Array

Disjoint-sets Array

其原理正是先前介绍的“索引储存”。

让一条 int 阵列的第 x 格代表第 x 人，格子裡填上这个人所属的团体编号。若两个人在同一团体，他们的格子裡就会有相同的团体编号。这是很直观的方式。

初始化

一开始大家还没开始分团的时候，其实可以想做是：每个人都不同团，每个人都是自己一人一团。有个方便的初始值设定方法，就是将第 x 格的值设成 x，这样每个人就都是不同团体的了。

Disjoint Sets 资料结构: Forest

Disjoint-sets Forest

其原理正是图论的“有向森林”。

让一条 int 阵列的第 x 格代表第 x 人──不过，格子裡改成填上 x 的老大是谁：

彷彿是老鼠会，以万流归宗的方式，来代表这个人是团体的大头目。团体的所有成员，他们往上追溯之后，都是同一个头目。一个团体中，只会有一个头目，由他来支配团体、作为团体的代表。

各位可能会有一个疑问：一个团体之中，每个人都有一个头目，那麽头目的老大是谁呢？可以姑且设定成自己。

一个团体就像是一棵分支很複杂的有根树。这些团体构成了一丛森林，故名 Disjoint-sets Forest。

初始化

一开始大家还没开始分团的时候，可以想成是：每个人都不同团，每个人都是自己一人一团，自己当头目。将第 x 格的值设成 x，这样每个人都是不同团体的头目了。