集合
Go语言里的集合一般会用map[T]bool这种形式来表示，T代表元素类型。
集合用map类型来表示虽然非常灵活，但我们可以以一种更好的形式来表示它。例如：在数据流分析领域，集合元素通常是一个非负整数，集合会包含很多元素，并且集合会经常进行并集、交集操作，这种情况下，bit数组会比map表现更加理想
我们知道在go语言中，出了几本数据类型外； 还有slice，map，struct，interface这些复杂数据类型；
但是我们发现在go中好像没有集合（set）这种数据类型，那么我们该如何通过go的基础类型和复杂数据类型来实现集合呢？
下面看一个int类型集合的实现
type IntSet struct {
words []uint64
}
func (s *IntSet) Has(x int) bool {
word, bit := x/64, uint(x%64)
return word < len(s.words) && s.words[word]&(1<<bit) != 0
}
func (s *IntSet) Add(x int) {
word, bit := x/64 ,uint(x%64)
for word >= len(s.words) {
s.words = append(s.words, 0)
}
s.words[word] |= 1 << bit
}
func (s *IntSet) UnionWith(t *IntSet) {
for i, tword := range t.words {
if i < len(s.words) {
s.words[i] |= tword
} else {
s.words = append(s.words, tword)
}
}
}
func (s *IntSet) String() string {
var buf bytes.Buffer
buf.WriteByte('{')
for i, word := range s.words {
if word == 0 {
continue
}
for j := 0; j < 64; j++ {
if word&(1 << uint(j)) != 0 {
if buf.Len() > len("{") {
buf.WriteByte(' ')
}
fmt.Fprintf(&buf, "%d", 64 * i + j)
}
}
}
buf.WriteByte('}')
return buf.String()
}
方法
上面的代码定义了一个IntSet的结构体，结构体中的字段是一个[]int64的切片，用于存储int64类型的整型数据；
func (s *IntSet) Has(x int) bool 为IntSet结构体提供了一个方法，用于判断集合内是否有某个元素了；
func (s *IntSet) Add(x int) 为IntSet结构体提供了添加元素的方法；
func (s *IntSet) UnionWith(t *IntSet) 为IntSet结构体提供了一个方法，用于将2个IntSet类型的集合做并集；
设计思路
一个bit数组通常会用一个无符号数或者称之为“字”的slice来表示，每一个元素的每一位都表示集合里的一个值。当集合的第i位被设置时，我们才说这个集合包含元素i
因为每一个字都有64个二进制位，所以为了定位x的bit位，我们用了x/64的商作为字的下标，并且用x%64得到的值作为这个字内的bit的所在位置。
UnionWith这个方法里用到了bit位的“或”逻辑操作符号|来一次完成64个元素的或计算