4.4　实战演练——Set

从本节开始，我们就要运用之前了解到的Go语言基础知识来实际开发一些高级数据结构。这些数据结构都是Go语言本身及其标准库中没有涉及的。

在很多编程语言中，集合（Set）的底层都是由哈希表（Hash Table）来实现的。比如，C++语言的代码库STL中的数据结构hash_set、Java语言的标准库中的java.util.HashSet类，以及Python语句的标准数据结构set，等等。

在Go语言的标准数据类型中并没有集合这种数据类型。但是，它却拥有作为Hash Table实现的字典（Map）类型。我们在对Set和Map进行比较之后会发现它们在一些主要特性上是极其相似的，如下所示。

  • 它们中的元素都是不可重复的。

  • 它们都只能用迭代的方式取出其中的所有元素。

  • 对它们中的元素进行迭代的顺序都是与元素插入顺序无关的，同时也不保证任何有序性。

但是，它们之间也有一些区别。

  • Set的元素是一个单一的值，而Map的元素则是一个键值对。

  • Set的元素不可重复指的是不能存在任意两个单一值相等的情况。Map的元素不可重复指的是任意两个键值对中的键的值不能相等。

仔细看过上面罗列的这些异同点之后，我们会发现Set更像是Map的一种简化版本。我们可不可以利用Map来编写一个Set的实现呢？答案当然是肯定的。实际上，在Java语言中，java.util.HashSet类就是用java.util.HashMap类作为底层支持的。java.util.HashSet相当于是java.util.HashMap类的一个代理类。

1. 基本定义

首先，我们创建一个名为hash_set.go的源码文件，并把它放在goc2p项目的代码包basic/set中。我们需要首先在这个源码文件的第一行上写入这样一行代码：

  1. package set

这是为了声明源码文件hash_set.go是代码包basic/set中的一员。我们刚才说过，可以把集合类型作为字典类型的一个简化版本。那么我们就声明一个其中包含了一个字典类型的字段的结构体类型。它的声明如下：

  1. type HashSet struct {
  2.     m map[interface{}]bool
  3. }

这个类型声明中的唯一的字段的类型是map[interface{}]bool。之所以选择这样的一个字典类型是有原因的。因为我们希望HashSet类型的元素可以是任何类型的，所以我们将字典m的键类型设置为了interface{}。又由于我们只需要用到m的值中的键来存储HashSet类型的元素值，所以就应该选用值占用空间最小的类型来作为m的值的元素类型。这里使用bool类型有3个好处。

  • 从值的存储形式的角度看，bool类型值的占用空间是最小的（之一），只占用一个字节。

  • 从值的表示形式的角度看，bool类型的值只有两个——true和false。并且，这两个值都是预定义常量。

  • 把bool类型作为值类型更有利于判断字典类型值中是否存在某个键。例如，如果我们在向m的值添加键值对的时候总是以true作为其中的元素的值，那么索引表达式

  1. m["a"]

的结果值就总能够直接体现出在m的值中是否包含键为"a"的键值对。但是，如果m的类型是map[interface{}]byte的话，那么我们只有通过

  1. v, ok := m["a"]

才能确切地得出上述判断的结果。虽然在向map[interface{}]byte类型的m的值添加键值对的时候，我们可以总以非零值的byte类型值作为其中的元素的值，但是我们在做判断的时候依然需要编写更多的代码：

  1. if v := m["a"]; v != 0 { // 如果“m”中不存在以“a”作为键的键值对
  2.     // 省略若干条语句
  3. }

而对于map[interface{}]bool类型的m的值来说，如此即可：

  1. if m["a"] { // 如果“m”中不存在以“a”作为键的键值对
  2.     // 省略若干条语句
  3. }

现在，HashSet类型的基本结构已经被确定。我们下面需要考虑初始化HashSet类型值的问题了。由于字典类型值的零值为nil，所以我们不能简单地使用new函数来创建一个HashSet类型值。换句话说，与HashSet类型声明处在同一个代码包中的表达式

  1. new(HashSet).m

的求值结果会是nil。因此，我们需要编写一个专门用于创建和初始化HashSet类型值的函数。这个函数的声明如下：

  1. func NewHashSet() *HashSet {
  2.     return &HashSet{m: make(map[interface{}]bool)}
  3. }

可以看到，我们使用make函数对字段m进行了初始化。注意，函数NewHashSet的结果声明的类型是HashSet而不是HashSet。这是因为，我们希望在这个结果值的方法集合中包含调用接收者类型为HashSet或HashSet的所有方法。至于这么做的好处，我们在后面编写Set接口类型的时候再予以说明。

2. 基本功能

现在，我们就需要为HashSet类型编写方法了。不过，在这之前我们先需要明确一下它都需要提供哪些功能。HashSet类型应该提供的基本功能如下。

  • 添加元素值。

  • 删除元素值。

  • 清除所有元素值。

  • 判断是否包含某个元素值。

  • 获取元素值的数量。

  • 判断与其他HashSet类型值是否相同。

  • 获取所有元素值，即生成可迭代的快照。

  • 获取自身的字符串表示形式。

上述功能中的绝大部分都是在其他编程语言的Set类型上已经提供的功能。作为一个可用和好用的Set类型，我们当然需要它们。

首先需要编写的是向HashSet类型值中添加元素值的方法，其声明如下：

  1. func (set *HashSet) Add(e interface{}) bool {
  2.     if !set.m[e] {
  3.         set.m[e] = true
  4.         return true
  5.     }
  6.     return false
  7. }

方法Add会返回一个bool类型的结果值，以表示添加元素值的操作是否成功。如果当前的m的值中还未包含以e的值为键的键值对，那么就将键为e（代表的值）、元素为true的键值对添加到m的值当中并返回true。否则，就直接返回false。

在这里需要注意的是，Add方法的声明中的接收者类型是HashSet。这里将其类型设置为HashSet而不是HashSet，主要原因是减少复制接收者值时对系统能够资源的耗费。我们在上一章中说过，方法的接收者值只是当前值的一个复制品。所以，当Add方法的接收者的类型为HashSet的时候，对它的每一次调用都需要对当前值（当前的HashSet类型值）进行一次复制。虽然，在HashSet类型中只有一个引用类型的字段，但是这终归是一种开销。并且，我们还未考虑HashSet类型中的字段可能会变得更多的情况。当Add方法的接收者的类型为HashSet的时候，对它进行调用时复制的当前值（当前的HashSet类型值）只是一个指针值。在大多数情况下，一个指针值占用的内存空间总会比它指向的那个其他类型的值所占用的内存空间小。指针值所占用的内存空间的大小与且只与当前计算机的计算架构中的字长（32比特或64比特）相对应。也就是说，无论一个指针值指向的那个其他类型值所需的内存空间有多么大，它所占用的内存空间总是不变的。因此，从节约内存空间的角度出发，建议尽量将方法的接收者类型设置为相应的指针类型。关于指针的更多知识请参见3.2.8节。

从HashSet类型值中删除元素值的操作是非常简单的。因为我们是用字典值作为HashSet类型的内部支持的，所以我们调用delete函数就可以达到删除元素值的目的。删除元素值的方法的声明如下：

  1. func (set *HashSet) Remove(e interface{}) {
  2.     delete(set.m, e)
  3. }

编写实现清除所有元素值功能的方法会用到一个小技巧。由于Go语言本身并没有提供可以清除字典值中的所有键值对的方法和内建函数，所以我们需要自己编码完成这一功能。迭代出其中的所有键值对并逐一删除它们当然是不可取的。这样做可能会在并发访问和修改的情况下引发问题，并且不一定总能把所有的键值对都删除掉。最干脆和简洁的方法就是为字段m重新赋值。依此实现的Clear方法如下：

  1. func (set *HashSet) Clear() {
  2.     set.m = make(map[interface{}]bool)
  3. }

对字段m赋值的效果的达成也得益于Clear方法的接收者类型*HashSet。如果接收者类型是HashSet，那么该方法中的这条赋值语句的作用只是为当前值的某个复制品中的字段m赋值而已，而当前值中的字段m则不会被重新赋值。

方法Clear中的这条赋值语句被执行之后，当前的HashSet类型值中的元素就相当于被清空了，就像刚刚被初始化过的值一样。已经与字段m解除绑定的那个旧的字典值由于不再与任何程序实体存在绑定关系而成为了无用的数据。它会在之后的某一时刻被Go语言的垃圾回收器发现并回收。

附属于HashSet类型的Contains方法用于判断其值是否包含某个元素值。它同样只包含一条语句。这也是得益于元素类型为bool的字段m。其声明如下：

  1. func (set *HashSet) Contains(e interface{}) bool {
  2.     return set.m[e]
  3. }

读者可能会有疑问，Go语言是怎样生成interface{}类型值的hash值的？对于一个interface{}类型值来说，Go语言总能正确地判断出在一个字典值中是否包含与之相对应的键吗？我通过查看Go语言的源代码获知，当我们把一个interface{}类型值作为键添加到一个字典值的时候，Go语言会先获取这个interface{}类型值的实际类型（即动态类型），然后再使用与之相对应的hash函数对该值进行hash运算。所以，interface{}类型值总是能够被正确地计算出hash值。显然，在之后的键查找的过程中也会存在这样的hash运算。但是，请注意，我们在上一章讲字典类型的时候说过，字典类型的键不能是函数类型、字典类型或切片类型。这种限制总是存在的。因此，Contains方法的参数e的值的动态类型一定不能是上面这几种类型，否则就会引发一个运行时恐慌并有如下提示：

  1. panic: runtime error: hash of unhashable type <某个函数类型、字典类型或切片类型的名称>

现在我们继续编码。与Remove方法类似，被用于获取元素值数量的方法Len也是利用Go语言的内建函数来完成功能的：

  1. func (set *HashSet) Len() int {
  2.     return len(set.m)
  3. }

合理利用Go语言的内建函数是我们编写Go语言代码的最基本的要求。Go语言内建函数的汇总请参见3.3.5节。

下面是对另一个方法的考虑。两个HashSet类型值相同的必要条件是，它们包含的元素值应该是完全相同的。由于HashSet类型值中的元素的迭代顺序总是不确定的，所以我们也就不用在意两个值在这方面是否一致。因此，刚才所说的那个必要条件也就成为了唯一的充分条件。下面的Same方法用来判断两个HashSet类型值是否相同：

  1. func (set *HashSet) Same(other *HashSet) bool {
  2.     if other == nil {
  3.         return false
  4.     }
  5.     if set.Len() != other.Len() {
  6.         return false
  7.     }
  8.     for key := range set.m {
  9.         if !other.Contains(key) {
  10.             return false
  11.         }
  12.     }
  13.     return true
  14. }

虽然Same方法中的语句稍微多了一些，但是其中的逻辑依然是非常简单和清晰的。我们利用了之前声明的Len方法和Contains方法完成了Same方法中最核心的逻辑。在大多数情况下，这种相同性判断就已经足够了。如果要判断两个HashSet类型值是否是同一个值，就需要利用指针运算进行内存地址的比较。不过我们在这里并不需要这种判断方式。

我们刚刚讲过，HashSet类型值的元素迭代顺序的不确定性。这种不确定性会使我们无法通过索引值获取某一个元素值。并且，我们也已经知道for语句和range子句只能够对数组类型、切片类型、字典类型和通道类型的值起作用。那么我们怎样对一个HashSet类型值进行迭代呢？或者说，我们怎样取出其中的值呢？一个简单可行的解决方案就是先生成一个它的快照，然后再在这个快照之上进行迭代操作。所谓快照，就是目标值在某一个时刻的映像。对于一个HashSet类型值来说，它的快照中的元素迭代顺序是总是可以确定的，这正是由于快照只反映了该HashSet类型值在某一个时刻的状态。另外，我们还需要从元素可迭代且顺序可确定的数据类型中选取一个作为快照的类型。这个类型必须是以单值作为元素的，所以字典类型最先被排除。又由于HashSet类型值中的元素数量总是不固定的，所以也就无法用一个数组类型的值来表示它的快照。因此，快照的类型应该是一个切片类型或者通道类型。我们这里以切片类型为例。

我们为这个被用于生成快照的方法起了一个比较通用的名字——Elements。我们根据前面对Elements方法的描述和分析编写出了它的声明：

  1. func (set *HashSet) Elements() []interface{} {
  2.     initialLen := len(set.m)
  3.     snapshot := make([]interface{}, initialLen)
  4.     actualLen := 0
  5.     for key := range set.m {
  6.         if actualLen < initialLen {
  7.             snapshot[actualLen] = key
  8.         } else {
  9.             snapshot = append(snapshot, key)
  10.         }
  11.         actualLen++
  12.     }
  13.     if actualLen < initialLen {
  14.         snapshot = snapshot[:actualLen]
  15.     }
  16.     return snapshot
  17. }

之所以我们使用这么多条语句来实现这个方法是因为需要考虑到在从获取字段m的值的长度到对m的值迭代完成的这个时间段内，m的值中的元素数量可能会发生变化。

我们每次调用append函数的时候，都会有一个新的切片值创建出来，并且有时候还会导致新的切片值的底层数组被替换。显然，这会降低生成快照的效率。因此，我们先获取字段m的值的长度，并以此初始化一个[]interface{}类型的变量snapshot来存储m的值中的元素值。在正常情况下，我们仅仅把迭代值按照既定顺序设置到快照值（变量snapshot的值）的指定元素位置上即可。这一过程并不会创建任何新值。如果在迭代完成之前，m的值中的元素数量有所增加，致使实际迭代的次数大于先前初始化的快照值的长度，那么我们再使用append函数向快照值追加元素值。这样做既提高了快照生成的效率，又不至于在元素数量增加时引发索引越界的运行时恐慌。

对于已被初始化的[]interface{}类型的切片值来说，未被显式初始化的元素位置上的值均为nil。如果在迭代完成之前，m的值中的元素数量有所减少，致使快照值的尾部存在若干个没有任何意义的值为nil的元素，那么我们就应该把这些无用的元素值从快照值中去掉。我们使用切片表达式和赋值语句snapshot = snapshot[:actualLen]达到了这一目的。

注意，虽然我们在Elements方法中针对并发访问和修改m的值的情况采取了一些措施。但是由于m的值本身不是并发安全的，所以我们并不能保证Elements方法的执行总会准确无误。要做到真正的并发安全，还需要一些辅助的手段，比如使用在上一章讲字典类型时提到的读写互斥量。

现在我们来编写最后一个提供基本功能的方法。它的功能是获取自身的字符串表示形式。这个方法的声明如下：

  1. func (set *HashSet) String() string {
  2.     var buf bytes.Buffer
  3.     buf.WriteString("Set{")
  4.     first := true
  5.     for key := range set.m {
  6.         if first {
  7.             first = false
  8.         } else {
  9.             buf.WriteString(" ")
  10.         }
  11.         buf.WriteString(fmt.Sprintf("%v", key))
  12.     }
  13.     buf.WriteString("}")
  14.     return buf.String()
  15. }

这个String方法的签名也算是一个惯用法。代码包fmt中的打印函数总会使用参数值附带的具有如此签名的String方法的结果值作为该参数值的字符串表示形式。当然，前提是那个数据类型声明了这个名为String的方法。所以，如果我们想让自定义类型值的字符串表示形式有更好的可读性，就需要声明这样的一个方法。顺便说一句，在String方法包含的语句列表中，我们使用bytes.Buffer类型值作为结果值的缓冲区，这样可以避免因string类型值的拼接造成的内存空间上的浪费。

至此，我们完整地编写了一个具备常用功能的Set的实现类型。但是，在很多时候，我们需要提供更多的功能来降低客户端代码使用它的成本。

3. 高级功能

在集合代数中有对集合的基本性质和规律的描述，其中包含了对各种集合运算和集合关系的说明。集合的运算包括并集、交集、差集和对称差集。集合的关系包括等于（也就是相同）和真包含。我们在前面编写的Same方法已经实现了对集合相同性的判断。下面，我们关注其余的关系判断功能和运算。

首先，我们来实现集合真包含的判断功能。从名称上看，它与Contains方法在逻辑上有些类似，不过它会更复杂一些。为了不与Contains方法在名称上过于类似，我们需要为这个方法另起一个名字。根据集合代数中的描述，如果集合A真包含了集合B，那么就可以说集合A是集合B的一个超集。因此，我们给这个方法的名称确定为IsSuperset。对于会返回一个bool类型的结果值的方法来说，用以“Is”为开头的动宾短语作为它的名称是非常适合的。IsSuperset方法的声明如下：

  1. func (set *HashSet) IsSuperset(other *HashSet) bool {
  2.     if other == nil {
  3.         return false
  4.     }
  5.     oneLen := set.Len()
  6.     otherLen := other.Len()
  7.     if oneLen == 0 || oneLen == otherLen {
  8.         return false
  9.     }
  10.     if oneLen > 0 && otherLen == 0 {
  11.         return true
  12.     }
  13.     for _, v := range other.Elements() {
  14.         if !set.Contains(v) {
  15.             return false
  16.         }
  17.     }
  18.     return true
  19. }

只要我们理解了真包含的含义，实现IsSuperset方法并不难。因为我们已经把实现基本功能的方法都编写完成了，在这里只要对它们进行组合使用即可。

现在我们来看集合运算。我们先来了解一下这些集合运算的含义。

  • 并集运算是指把两个集合中的所有元素都合并起来并组成一个集合。

  • 交集运算是指找到两个集合中共有的元素并把它们组成一个集合。

  • 集合A对集合B进行差集运算的含义是找到只存在于集合A中但不存在于集合B中的元素并把它们组成一个集合。

  • 对称差集运算与差集运算类似但有所区别。对称差集运算是指找到只存在于集合A中但不存在于集合B中的元素，再找到只存在于集合B中但不存在于集合A中的元素，最后把它们合并起来并组成一个集合。

与IsSuperset方法相同，我们可以利用HashSet已有的方法来编写实现这些集合运算的方法。我们先为这些方法确定名称，实现并集、交集、差集、对称差集运算的方法的名称分别为Union、Intersect、Difference、SymmetricDifference。请读者模仿前面已经编写完成的方法的声明自行编写出它们的声明，并满足如下4点要求。

  • 它们都接受一个名为other且类型为*HashSet的参数值。

  • 在方法中不得修改接收者set的值和参数other的值。

  • 它们的结果的类型都应该为*HashSet。

  • 尽可能地利用已有的附属于*HashSet类型的方法。

另外，需要注意，由于参数值other和其中的字段m都可能为nil，所以我们应该考虑到每个实现高级功能的方法在这种情况下的不同处理方式。比如我们前面提到过的卫述语句。

在完成了这些方法的声明之后，读者应该首先去测试它们的功能和性能。关于怎样编写单元测试程序，请读者参看第5章。在我们使用单元测试程序对HashSet类型及其方法进行了全面的测试之后，就可以放心大胆地对它们进行修改和重构了（希望读者已经根据我们的要求编写了实现那些高级功能的方法）。

4. 进一步重构

我们在本节所实现的HashSet类型提供了一些必要的集合操作功能。但是，我们在不同应用场景下可能会需要使用功能更加丰富的集合类型。我们可以对HashSet类型进行扩展（注意，不是继承）以满足我们特定的要求。我们对HashSet类型的扩展往往可以通过将它嵌入到新类型的声明中来实现。比如，我们可以使一个嵌入了HashSet类型的新类型实现sort.Interface接口类型，以使它具有对元素排序的能力（参考3.2.6节）。又比如，我们可以创建一个元素类型固定的集合类型。这需要用到代码包reflect中声明的程序实体（请参看代码包reflect的文档和3.2.7节中的方案）。

当我们有了多个集合类型的时候，就应该在它们之上抽取出一个接口类型以标识它们共有的行为方式。我们可以把这个接口类型就取名为Set。依照HashSet类型的声明，我们可以这样来声明Set接口类型：

  1. type Set interface {
  2.     Add(e interface{}) bool
  3.     Remove(e interface{})
  4.     Clear()
  5.     Contains(e interface{}) bool
  6.     Len() int
  7.     Same(other Set) bool
  8.     Elements() []interface{}
  9.     String() string
  10. }

注意，Set中的Same方法的签名与附属于HashSet类型的Same方法有所不同。因为我们不能在接口类型的方法的签名中包含它的实现类型。这就需要我们对HashSet类型的Same方法稍作改动：

  1. func (set *HashSet) Same(other Set) bool {
  2.     // 省略若干条语句
  3. }

可以看到，我们只是修改了这个Same方法的签名。这样做的目的是让*HashSet类型成为Set接口类型的一个实现。

也许有些读者认为应该在Set接口类型的声明中加入实现高级功能的方法的声明，比如：

  1. IsSuperset(other Set) bool
  2. Union(other Set) Set
  3. Intersect(other Set) Set
  4. Difference(other Set) Set
  5. SymmetricDifference(other Set) Set

但是，这些代表集合操作的方法应该适用于所有实现了Set接口类型的数据类型（以下简称实现类型），不是吗？这些实现了高级功能的方法（以下简称高级方法）中的核心逻辑，应该通过对那些实现了基本功能的方法（以下简称基本方法）的组合使用来实现。每个实现类型的不同之处都应该体现在它们的基本方法的实现中。在高级方法中，我们应该屏蔽掉（或者说透明化）这些不同。因此，我们完全可以把这些高级方法抽离出来，并使之成为独立的函数，以面向所有的实现类型。并且，我们也不应该在每个实现类型中重复地实现这些高级方法。读者可以试着把之前声明的这些高级方法修改为独立的、面向所有集合类型的函数。我们在这里给出改造后的IsSuperset方法的声明：

  1. // 判断集合 one 是否是集合 other 的超集
  2. func IsSuperset(one Set, other Set) bool {
  3.     if one == nil || other == nil {
  4.         return false
  5.     }
  6.     oneLen := one.Len()
  7.     otherLen := other.Len()
  8.     if oneLen == 0 || oneLen == otherLen {
  9.         return false
  10.     }
  11.     if oneLen > 0 && otherLen == 0 {
  12.         return true
  13.     }
  14.     for _, v := range other.Elements() {
  15.         if !one.Contains(v) {
  16.             return false
  17.         }
  18.     }
  19.     return true
  20. }

我们在前面重点讲述的与集合相关的数据类型和函数的参考实现，都会被放在goc2p项目中的代码包basic/set的源码文件中。不过我还是建议读者在自己实现它们之后再去与参考实现进行比较。说不定你的实现会更好。