Golang理解-集合

一时失言乱红尘 2023-08-17 17:24 111阅读 0赞

## **集合** ##

--------------------

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

转载于:https://www.cnblogs.com/vinsent/p/11555412.html