一、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)化版本。現(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
}
以上就是Go語(yǔ)言之自定義集合Set的全部?jī)?nèi)容，希望對(duì)大家學(xué)習(xí)Go語(yǔ)言有所幫助。
您可能感興趣的文章:- Golang中的自定義函數(shù)詳解
- golang對(duì)自定義類型進(jìn)行排序的解決方法
- goLang引入自定義包的方法
