集合

---

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<
    
     = 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个元素的或计算