Go語(yǔ)言中如何自定義Set集合

這篇文章主要介紹“Go語(yǔ)言中如何自定義Set集合”，在日常操作中，相信很多人在Go語(yǔ)言中如何自定義Set集合問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Go語(yǔ)言中如何自定義Set集合”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

一、Go語(yǔ)言實(shí)戰(zhàn)——自定義集合Set

在Go語(yǔ)言中有作為Hash Table實(shí)現(xiàn)的字典（Map）類型，但標(biāo)準(zhǔn)數(shù)據(jù)類型中并沒(méi)有集合（Set）這種數(shù)據(jù)類型。比較 Set 和 Map 的主要特性，有類似特性如下：

    它們中的元素都是不可重復(fù)的。

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

    對(duì)它們中的元素進(jìn)行迭代的順序都是與元素插入順序無(wú)關(guān)的，同時(shí)也不保證任何有序性。

但是，它們之間也有一些區(qū)別，如下：

Set 的元素是一個(gè)單一的值，而 Map 的元素則是一個(gè)鍵值對(duì)。

Set 的元素不可重復(fù)指的是不能存在任意兩個(gè)單一值相等的情況。Map的元素不可重復(fù)指的是任意兩個(gè)鍵值對(duì)中的鍵的值不能相等。

從上面的特性可知，可以把集合類型（Set）作為字典類型（Map）的一個(gè)簡(jiǎn)化版本。也就是說(shuō)，可以用 Map 來(lái)編寫一個(gè) Set 類型的實(shí)現(xiàn)。實(shí)際上，在Java語(yǔ)言中，java.util.HashSet 類就是用 java.util.HashMap 類作為底層支持的。所以這里就從HashSet出發(fā)，逐步抽象出集合Set。

1. 定義HashSet

首先，在工作區(qū)的 src 目錄的代碼包 basic/set（可以自行定義，但后面要保持一致）中，創(chuàng)建一個(gè)名為 hash_set.go 的源碼文件。

根據(jù)代碼包 basic/set 可知，源碼文件 hash_set.go 的包聲明語(yǔ)句（關(guān)于這個(gè)一些規(guī)則可以看前面的系列博文）如下：

package set

上面提到可以將集合類型作為字典類型的一個(gè)簡(jiǎn)化版本?，F(xiàn)在我們的 HashSet 就以字典類型作為其底層的實(shí)現(xiàn)。HashSet 聲明如下：

type HashSet struct {
  m map[interface{}]bool
}

如上聲明 HashSet 類型中的唯一的字段的類型是 map[interface{}]bool。選擇這樣一個(gè)字典類型是因?yàn)橥ㄟ^(guò)將字典 m 的鍵類型設(shè)置為 interface{}，讓 HashSet 的元素可以是任何類型的，因?yàn)檫@里需要使用 m 的值中的鍵來(lái)存儲(chǔ) HashSet 類型的元素值。那使用 bool 類型作為 m 的值的元素類型的好處如下：

從值的存儲(chǔ)形式的角度看，bool 類型值只占用一個(gè)字節(jié)。

從值的表示形式的角度看，bool 類型的值只有兩個(gè)—true 和 false。并且，這兩個(gè)值度都是預(yù)定義常量。

把 bool 類型作為值類型更有利于判斷字典類型值中是否存在某個(gè)鍵。例如：如果在向 m 的值添加鍵值對(duì)的時(shí)候總是以 true 作為其中的元素的值，則索引表達(dá)式 m[“a”] 的結(jié)果值總能體現(xiàn)出在m的值中是否包含鍵為“a”的鍵值對(duì)。對(duì)于 map[interface{}]bool 類型的值來(lái)說(shuō)，如下：

if m["a"] {// 判斷是否m中包含鍵為“a”的鍵值對(duì)
  //省略其他語(yǔ)句
}

如上 HashSet 類型的基本結(jié)構(gòu)已確定了，現(xiàn)在考慮如何初始化 HashSet 類型值。由于字典類型的零值為 nil,而用 new 函數(shù)來(lái)創(chuàng)建一個(gè) HashSet 類型值，也就是 new(HashSet).m 的求值結(jié)果將會(huì)是一個(gè) nil (關(guān)于 new 函數(shù)可以查閱本人另一篇博文Go語(yǔ)言學(xué)習(xí)筆記5)。因此，這里需要編寫一個(gè)專門用于創(chuàng)建和初始化 HashSet 類型值的函數(shù)，該函數(shù)聲明如下：

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

如上可以看到，使用make函數(shù)對(duì)字段m進(jìn)行了初始化。同時(shí)注意觀察函數(shù) NewHashSet 的結(jié)果聲明的類型是 *HashSet 而不是 HashSet，目的是讓這個(gè)結(jié)果值的方法集合中包含調(diào)用接收者類型為 HashSet 或 *HashSet 的所有方法。這樣做的好處將在后面編寫 Set 接口類型的時(shí)候再予以說(shuō)明。

2.實(shí)現(xiàn)HashSet的基本功能

依據(jù)其他編程語(yǔ)言中的 HashSet 類型可知，它們大部分應(yīng)該提供的基本功能如下：

添加元素值。

刪除元素值。

清除所有元素值。

判斷是否包含某個(gè)元素值。

獲取元素值的數(shù)量。

判斷與其他HashSet類型值是否相同。

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

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

現(xiàn)在對(duì)這些功能一一實(shí)現(xiàn)，讀者可自行實(shí)現(xiàn)，以下僅供參考。

(1).添加元素值

//方法Add會(huì)返回一個(gè)bool類型的結(jié)果值，以表示添加元素值的操作是否成功。
//方法Add的聲明中的接收者類型是*HashSet。
func (set *HashSet) Add(e interface{}) bool {
  if !set.m[e] {//當(dāng)前的m的值中還未包含以e的值為鍵的鍵值對(duì)
    set.m[e] = true//將鍵為e(代表的值)、元素為true的鍵值對(duì)添加到m的值當(dāng)中
    return true //添加成功
  }
  return false //添加失敗
}

這里使用 *HashSet 而不是 HashSet，主要是從節(jié)約內(nèi)存空間的角度出發(fā)，分析如下：

當(dāng) Add 方法的接收者類型為 HashSet 的時(shí)候，對(duì)它的每一次調(diào)用都需要對(duì)當(dāng)前 HashSet 類型值進(jìn)行一次復(fù)制。雖然在 HashSet 類型中只有一個(gè)引用類型的字段，但是這也是一種開(kāi)銷。而且這里還沒(méi)有考慮 HashSet 類型中的字段可能會(huì)變得更多的情況。

當(dāng) Add 方法的接收者類型為 *HashSet 的時(shí)候，對(duì)它進(jìn)行調(diào)用時(shí)復(fù)制的當(dāng)前 *HashSet 的類型值只是一個(gè)指針值。在大多數(shù)情況下，一個(gè)指針值占用的內(nèi)存空間總會(huì)被它指向的那個(gè)其他類型的值所占用的內(nèi)存空間小。無(wú)論一個(gè)指針值指向的那個(gè)其他類型值所需的內(nèi)存空間有多么大，它所占用的內(nèi)存空間總是不變的。

(2).刪除元素值

//調(diào)用delete內(nèi)建函數(shù)刪除HashSet內(nèi)部支持的字典值
func (set *HashSet) Remove(e interface{}) {
  delete(set.m, e)//第一個(gè)參數(shù)為目標(biāo)字典類型，第二個(gè)參數(shù)為要?jiǎng)h除的那個(gè)鍵值對(duì)的鍵
}

(3).清除所有元素

//為HashSet中的字段m重新賦值
func (set *HashSet) Clear() {
  set.m = make(map[interface{}]bool)
}

如果接收者類型是 HashSet，該方法中的賦值語(yǔ)句的作用只是為當(dāng)前值的某個(gè)復(fù)制品中的字段m賦值而已，而當(dāng)前值中的字段 m 則不會(huì)被重新賦值。方法 Clear 中的這條賦值語(yǔ)句被執(zhí)行之后，當(dāng)前的 HashSet 類型值中的元素就相當(dāng)于被清空了。已經(jīng)與字段 m 解除綁定的那個(gè)舊的字典值由于不再與任何程序?qū)嶓w存在綁定關(guān)系而成為了無(wú)用的數(shù)據(jù)。它會(huì)在之后的某一時(shí)刻被Go語(yǔ)言的垃圾回收器發(fā)現(xiàn)并回收。

(4).判斷是否包含某個(gè)元素值。

//方法Contains用于判斷其值是否包含某個(gè)元素值。
//這里判斷結(jié)果得益于元素類型為bool的字段m
func (set *HashSet) Contains(e interface{}) bool {
  return set.m[e]
}

當(dāng)把一個(gè) interface{} 類型值作為鍵添加到一個(gè)字典值的時(shí)候，Go語(yǔ)言會(huì)先獲取這個(gè) interface{} 類型值的實(shí)際類型（即動(dòng)態(tài)類型），然后再使用與之對(duì)應(yīng)的 hash 函數(shù)對(duì)該值進(jìn)行 hash 運(yùn)算，也就是說(shuō)，interface{} 類型值總是能夠被正確地計(jì)算出 hash 值。但是字典類型的鍵不能是函數(shù)類型、字典類型或切片類型，否則會(huì)引發(fā)一個(gè)運(yùn)行時(shí)恐慌，并提示如下：
panic: runtime error: hash of unhashable type <某個(gè)函數(shù)類型、字典類型或切片類型的名稱>

(5).獲取元素值的數(shù)量。

//方法Len用于獲取HashSet元素值數(shù)量
func (set *HashSet) Len() int {
  return len(set.m)
}

(6).判斷與其他HashSet類型值是否相同。

//方法Same用來(lái)判斷兩個(gè)HashSet類型值是否相同
func (set *HashSet) Same(other *HashSet) bool {
  if other == nil {
    return false
  }
  if set.Len() != other.Len() {
    return false
  }
  for key := range set.m {
    if !other.Contains(key) {
      return false
    }
  }
  return true
}

兩個(gè) HashSet 類型值相同的必要條件是，它們包含的元素應(yīng)該是完全相同的。由于 HashSet 類型值中的元素的迭代順序總是不確定的，所以也就不用在意兩個(gè)值在這方面是否一致。如果要判斷兩個(gè) HashSet 類型值是否是同一個(gè)值，就需要利用指針運(yùn)算進(jìn)行內(nèi)存地址的比較。

(7).獲取所有元素值，即生成可迭代的快照。

所謂 快照，就是目標(biāo)值在某一個(gè)時(shí)刻的映像。對(duì)于一個(gè) HashSet 類型值來(lái)說(shuō)，它的快照中的元素迭代順序總是可以確定的，快照只反映了該 HashSet 類型值在某一個(gè)時(shí)刻的狀態(tài)。另外，還需要從元素可迭代且順序可確定的數(shù)據(jù)類型中選取一個(gè)作為快照的類型。這個(gè)類型必須是以單值作為元素的，所以字典類型最先別排除。又由于 HashSet 類型值中的元素?cái)?shù)量總是不固定的，所以無(wú)法用一個(gè)數(shù)組類型的值來(lái)表示它的快照。如上分析可知，Go語(yǔ)言中可以使用的快照的類型應(yīng)該是一個(gè)切片類型或者通道類型。

//方法Elements用于生成快照
func (set *HashSet) Elements() []interface{} {
  initialLen := len(set.m)//獲取HashSet中字段m的長(zhǎng)度，即m中包含元素的數(shù)量
  //初始化一個(gè)[]interface{}類型的變量snapshot來(lái)存儲(chǔ)m的值中的元素值
  snapshot := make([]interface{}, initialLen)
  actualLen := 0
  //按照既定順序?qū)⒌翟O(shè)置到快照值(變量snapshot的值)的指定元素位置上,這一過(guò)程并不會(huì)創(chuàng)建任何新值。
  for key := range set.m {
    if actualLen < initialLen {
      snapshot[actualLen] = key
    } else {//m的值中的元素?cái)?shù)量有所增加，使得實(shí)際迭代的次數(shù)大于先前初始化的快照值的長(zhǎng)度
      snapshot = append(snapshot, key)//使用append函數(shù)向快照值追加元素值。
    }
    actualLen++//實(shí)際迭代的次數(shù)
  }
  //對(duì)于已被初始化的[]interface{}類型的切片值來(lái)說(shuō)，未被顯示初始化的元素位置上的值均為nil。
  //m的值中的元素?cái)?shù)量有所減少，使得實(shí)際迭代的次數(shù)小于先前初始化的快照值的長(zhǎng)度。
  //這樣快照值的尾部存在若干個(gè)沒(méi)有任何意義的值為nil的元素，
  //可以通過(guò)snapshot = snapshot[:actualLen]將無(wú)用的元素值從快照值中去掉。
  if actualLen < initialLen {
    snapshot = snapshot[:actualLen]
  }
  return snapshot
}

注意：在 Elements 方法中針對(duì)并發(fā)訪問(wèn)和修改 m 的值的情況采取了一些措施。但是由于m的值本身并不是并發(fā)安全的，所以并不能保證 Elements 方法的執(zhí)行總會(huì)準(zhǔn)確無(wú)誤。要做到真正的并發(fā)安全，還需要一些輔助的手段，比如讀寫互斥量。

(8).獲取自身的字符串表示形式。

//這個(gè)String方法的簽名算是一個(gè)慣用法。 //代碼包fmt中的打印函數(shù)總會(huì)使用參數(shù)值附帶的具有如此簽名的String方法的結(jié)果值作為該參數(shù)值的字符串表示形式。
func (set *HashSet) String() string {
  var buf bytes.Buffer//作為結(jié)果值的緩沖區(qū)
  buf.WriteString("HashSet{")
  first := true
  for key := range set.m {
    if first {
      first = false
    } else {
      buf.WriteString(",")
    }
    buf.WriteString(fmt.Sprintf("%v", key))
  }
  //n := 1
  //for key := range set.m {
  // buf.WriteString(fmt.Sprintf("%v", key))
  // if n == len(set.m) {//最后一個(gè)元素的后面不添加逗號(hào)
  // break;
  // } else {
  // buf.WriteString(",")
  // }
  // n++;
  //}
  buf.WriteString("}")
  return buf.String() 
}

如上已經(jīng)完整地編寫了一個(gè)具備常用功能的Set的實(shí)現(xiàn)類型，后面將講解更多的高級(jí)功能來(lái)完善它。

3.高級(jí)功能

集合 Set 的真包含的判斷功能。根據(jù)集合代數(shù)中的描述，如果集合 A 真包含了集合 B，那么就可以說(shuō)集合 A 是集合 B 的一個(gè)超集。

// 判斷集合 set 是否是集合 other 的超集 
func (set *HashSet) IsSuperset(other *HashSet) bool {
  if other == nil {//如果other為nil，則other不是set的子集
    return false
  }
  setLen := set.Len()//獲取set的元素值數(shù)量
  otherLen := other.Len()//獲取other的元素值數(shù)量
  if setLen == 0 || setLen == otherLen {//set的元素值數(shù)量等于0或者等于other的元素?cái)?shù)量
    return false
  }
  if setLen > 0 && otherLen == 0 {//other為元素?cái)?shù)量為0，set元素?cái)?shù)量大于0，則set也是other的超集
    return true
  }
  for _, v := range other.Elements() {
    if !set.Contains(v) {//只要set中有一個(gè)包含other中的數(shù)據(jù)，就返回false
      return false
    }
  }
  return true
}

集合的運(yùn)算包括并集、交集、差集和對(duì)稱差集。

并集運(yùn)算是指把兩個(gè)集合中的所有元素都合并起來(lái)并組合成一個(gè)集合。

交集運(yùn)算是指找到兩個(gè)集合中共有的元素并把它們組成一個(gè)集合。

集合 A 對(duì)集合 B 進(jìn)行差集運(yùn)算的含義是找到只存在于集合 A 中但不存在于集合 B 中的元素并把它們組成一個(gè)集合。

對(duì)稱差集運(yùn)算與差集運(yùn)算類似但有所區(qū)別。對(duì)稱差集運(yùn)算是指找到只存在于集合 A 中但不存在于集合 B 中的元素，再找到只存在于集合 B 中但不存在于集合 A 中的元素，最后把它們合并起來(lái)并組成一個(gè)集合。

實(shí)現(xiàn)并集運(yùn)算

// 生成集合 set 和集合 other 的并集
func (set *HashSet) Union(other *HashSet) *HashSet {
  if set == nil || other == nil {// set和other都為nil，則它們的并集為nil
    return nil
  }
  unionedSet := NewHashSet()//新創(chuàng)建一個(gè)HashSet類型值，它的長(zhǎng)度為0，即元素?cái)?shù)量為0
  for _, v := range set.Elements() {//將set中的元素添加到unionedSet中
    unionedSet.Add(v)
  }
  if other.Len() == 0 {
    return unionedSet
  }
  for _, v := range other.Elements() {//將other中的元素添加到unionedSet中，如果遇到相同，則不添加（在Add方法邏輯中體現(xiàn)）
    unionedSet.Add(v)
  }
  return unionedSet
}

實(shí)現(xiàn)交集運(yùn)算

// 生成集合 set 和集合 other 的交集
func (set *HashSet) Intersect(other *HashSet) *HashSet {
  if set == nil || other == nil {// set和other都為nil，則它們的交集為nil
    return nil
  }
  intersectedSet := NewHashSet()//新創(chuàng)建一個(gè)HashSet類型值，它的長(zhǎng)度為0，即元素?cái)?shù)量為0
  if other.Len() == 0 {//other的元素?cái)?shù)量為0，直接返回intersectedSet
    return intersectedSet
  }
  if set.Len() < other.Len() {//set的元素?cái)?shù)量少于other的元素?cái)?shù)量
    for _, v := range set.Elements() {//遍歷set
      if other.Contains(v) {//只要將set和other共有的添加到intersectedSet
        intersectedSet.Add(v)
      }
    }
  } else {//set的元素?cái)?shù)量多于other的元素?cái)?shù)量
    for _, v := range other.Elements() {//遍歷other
      if set.Contains(v) {//只要將set和other共有的添加到intersectedSet
        intersectedSet.Add(v)
      }
    }
  }
  return intersectedSet
}

差集

// 生成集合 set 對(duì)集合 other 的差集
func (set *HashSet) Difference(other *HashSet) *HashSet {
  if set == nil || other == nil {// set和other都為nil，則它們的差集為nil
    return nil
  }
  differencedSet := NewHashSet()//新創(chuàng)建一個(gè)HashSet類型值，它的長(zhǎng)度為0，即元素?cái)?shù)量為0
  if other.Len() == 0 { // 如果other的元素?cái)?shù)量為0
    for _, v := range set.Elements() {//遍歷set，并將set中的元素v添加到differencedSet
      differencedSet.Add(v)
    }
    return differencedSet//直接返回differencedSet
  }
  for _, v := range set.Elements() {//other的元素?cái)?shù)量不為0，遍歷set
    if !other.Contains(v) {//如果other中不包含v，就將v添加到differencedSet中
      differencedSet.Add(v)
    }
  }
  return differencedSet
}

對(duì)稱差集

// 生成集合 one 和集合 other 的對(duì)稱差集
func (set *HashSet) SymmetricDifference(other *HashSet) *HashSet {
  if set == nil || other == nil {// set和other都為nil，則它們的對(duì)稱差集為nil
    return nil
  }
  diffA := set.Difference(other)//生成集合 set 對(duì)集合 other 的差集
  if other.Len() == 0 {//如果other的元素?cái)?shù)量等于0，那么other對(duì)集合set的差集為空，則直接返回diffA
    return diffA
  }
  diffB := other.Difference(set)//生成集合 other 對(duì)集合 set 的差集
  return diffA.Union(diffB)//返回集合 diffA 和集合 diffB 的并集
}

4.進(jìn)一步重構(gòu)
目前所實(shí)現(xiàn)的 HashSet 類型提供了一些必要的集合操作功能，但是不同應(yīng)用場(chǎng)景下可能會(huì)需要使用功能更加豐富的集合類型。當(dāng)有多個(gè)集合類型的時(shí)候，應(yīng)該在它們之上抽取出一個(gè)接口類型以標(biāo)識(shí)它們共有的行為方式。依據(jù) HashSet 類型的聲明，可以如下聲明 Set 接口類型：

type Set interface {
  Add(e interface{}) bool
  Remove(e interface{})
  Clear()
  Contains(e interface{}) bool
  Len() int
  Same(other Set) bool
  Elements() []interface{}
  String() string
}

注意： Set 中的 Same 方法的簽名與附屬于 HashSet類型的 Same 方法有所不同。這里不能再接口類型的方法的簽名中包含它的實(shí)現(xiàn)類型。因此這里的改動(dòng)如下：

func (set *HashSet) Same(other Set) bool {
  //省略若干語(yǔ)句
}

修改了 Same 方法的簽名，目的是讓 *HashSet 類型成為 Set 接口類型的一個(gè)實(shí)現(xiàn)類型。

高級(jí)功能的方法應(yīng)該適用于所有的實(shí)現(xiàn)類型，完全可以抽離出成為獨(dú)立的函數(shù)。并且，也不應(yīng)該在每個(gè)實(shí)現(xiàn)類型中重復(fù)地實(shí)現(xiàn)這些高級(jí)方法。如下為改造后的 IsSuperset 方法的聲明：

// 判斷集合 one 是否是集合 other 的超集
// 讀者應(yīng)重點(diǎn)關(guān)注IsSuperset與附屬于HashSet類型的IsSuperset方法的區(qū)別
func IsSuperset(one Set, other Set) bool {
  if one == nil || other == nil {
    return false
  }
  oneLen := one.Len()
  otherLen := other.Len()
  if oneLen == 0 || oneLen == otherLen {
    return false
  }
  if oneLen > 0 && otherLen == 0 {
    return true
  }
  for _, v := range other.Elements() {
    if !one.Contains(v) {
      return false
    }
  }
  return true
}

到此，關(guān)于“Go語(yǔ)言中如何自定義Set集合”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！