一、Go語言實戰(zhàn)——自定義集合Set
在Go語言中有作為Hash Table實現(xiàn)的字典（Map）類型，但標(biāo)準(zhǔn)數(shù)據(jù)類型中并沒有集合（Set）這種數(shù)據(jù)類型。比較 Set 和 Map 的主要特性，有類似特性如下：
它們中的元素都是不可重復(fù)的。
它們都只能用迭代的方式取出其中的所有元素。
對它們中的元素進行迭代的順序都是與元素插入順序無關(guān)的，同時也不保證任何有序性。
但是，它們之間也有一些區(qū)別，如下：
Set 的元素是一個單一的值，而 Map 的元素則是一個鍵值對。
Set 的元素不可重復(fù)指的是不能存在任意兩個單一值相等的情況。Map的元素不可重復(fù)指的是任意兩個鍵值對中的鍵的值不能相等。
從上面的特性可知，可以把集合類型（Set）作為字典類型（Map）的一個簡化版本。也就是說，可以用 Map 來編寫一個 Set 類型的實現(xiàn)。實際上，在Java語言中，java.util.HashSet 類就是用 java.util.HashMap 類作為底層支持的。所以這里就從HashSet出發(fā)，逐步抽象出集合Set。
1. 定義HashSet
首先，在工作區(qū)的 src 目錄的代碼包 basic/set（可以自行定義，但后面要保持一致）中，創(chuàng)建一個名為 hash_set.go 的源碼文件。
根據(jù)代碼包 basic/set 可知，源碼文件 hash_set.go 的包聲明語句（關(guān)于這個一些規(guī)則可以看前面的系列博文）如下：
package set
上面提到可以將集合類型作為字典類型的一個簡化版本。現(xiàn)在我們的 HashSet 就以字典類型作為其底層的實現(xiàn)。HashSet 聲明如下：
type HashSet struct {
m map[interface{}]bool
}
如上聲明 HashSet 類型中的唯一的字段的類型是 map[interface{}]bool。選擇這樣一個字典類型是因為通過將字典 m 的鍵類型設(shè)置為 interface{}，讓 HashSet 的元素可以是任何類型的，因為這里需要使用 m 的值中的鍵來存儲 HashSet 類型的元素值。那使用 bool 類型作為 m 的值的元素類型的好處如下：
從值的存儲形式的角度看，bool 類型值只占用一個字節(jié)。
從值的表示形式的角度看，bool 類型的值只有兩個—true 和 false。并且，這兩個值度都是預(yù)定義常量。
把 bool 類型作為值類型更有利于判斷字典類型值中是否存在某個鍵。例如：如果在向 m 的值添加鍵值對的時候總是以 true 作為其中的元素的值，則索引表達式 m[“a”] 的結(jié)果值總能體現(xiàn)出在m的值中是否包含鍵為“a”的鍵值對。對于 map[interface{}]bool 類型的值來說，如下：
if m["a"] {// 判斷是否m中包含鍵為“a”的鍵值對
//省略其他語句
}
如上 HashSet 類型的基本結(jié)構(gòu)已確定了，現(xiàn)在考慮如何初始化 HashSet 類型值。由于字典類型的零值為 nil,而用 new 函數(shù)來創(chuàng)建一個 HashSet 類型值，也就是 new(HashSet).m 的求值結(jié)果將會是一個 nil (關(guān)于 new 函數(shù)可以查閱本人另一篇博文Go語言學(xué)習(xí)筆記5)。因此，這里需要編寫一個專門用于創(chuàng)建和初始化 HashSet 類型值的函數(shù)，該函數(shù)聲明如下：
func NewHashSet() *HashSet {
return HashSet{m: make(map[interface{}]bool)}
}
如上可以看到，使用make函數(shù)對字段m進行了初始化。同時注意觀察函數(shù) NewHashSet 的結(jié)果聲明的類型是 *HashSet 而不是 HashSet，目的是讓這個結(jié)果值的方法集合中包含調(diào)用接收者類型為 HashSet 或 *HashSet 的所有方法。這樣做的好處將在后面編寫 Set 接口類型的時候再予以說明。
2.實現(xiàn)HashSet的基本功能
依據(jù)其他編程語言中的 HashSet 類型可知，它們大部分應(yīng)該提供的基本功能如下：
添加元素值。
刪除元素值。
清除所有元素值。
判斷是否包含某個元素值。
獲取元素值的數(shù)量。
判斷與其他HashSet類型值是否相同。
獲取所有元素值，即生成可迭代的快照。
獲取自身的字符串表示形式。
現(xiàn)在對這些功能一一實現(xiàn)，讀者可自行實現(xiàn)，以下僅供參考。
(1).添加元素值
//方法Add會返回一個bool類型的結(jié)果值，以表示添加元素值的操作是否成功。
//方法Add的聲明中的接收者類型是*HashSet。
func (set *HashSet) Add(e interface{}) bool {
if !set.m[e] {//當(dāng)前的m的值中還未包含以e的值為鍵的鍵值對
set.m[e] = true//將鍵為e(代表的值)、元素為true的鍵值對添加到m的值當(dāng)中
return true //添加成功
}
return false //添加失敗
}
這里使用 *HashSet 而不是 HashSet，主要是從節(jié)約內(nèi)存空間的角度出發(fā)，分析如下：
當(dāng) Add 方法的接收者類型為 HashSet 的時候，對它的每一次調(diào)用都需要對當(dāng)前 HashSet 類型值進行一次復(fù)制。雖然在 HashSet 類型中只有一個引用類型的字段，但是這也是一種開銷。而且這里還沒有考慮 HashSet 類型中的字段可能會變得更多的情況。
當(dāng) Add 方法的接收者類型為 *HashSet 的時候，對它進行調(diào)用時復(fù)制的當(dāng)前 *HashSet 的類型值只是一個指針值。在大多數(shù)情況下，一個指針值占用的內(nèi)存空間總會被它指向的那個其他類型的值所占用的內(nèi)存空間小。無論一個指針值指向的那個其他類型值所需的內(nèi)存空間有多么大，它所占用的內(nèi)存空間總是不變的。
(2).刪除元素值
//調(diào)用delete內(nèi)建函數(shù)刪除HashSet內(nèi)部支持的字典值
func (set *HashSet) Remove(e interface{}) {
delete(set.m, e)//第一個參數(shù)為目標(biāo)字典類型，第二個參數(shù)為要刪除的那個鍵值對的鍵
}
(3).清除所有元素
//為HashSet中的字段m重新賦值
func (set *HashSet) Clear() {
set.m = make(map[interface{}]bool)
}
如果接收者類型是 HashSet，該方法中的賦值語句的作用只是為當(dāng)前值的某個復(fù)制品中的字段m賦值而已，而當(dāng)前值中的字段 m 則不會被重新賦值。方法 Clear 中的這條賦值語句被執(zhí)行之后，當(dāng)前的 HashSet 類型值中的元素就相當(dāng)于被清空了。已經(jīng)與字段 m 解除綁定的那個舊的字典值由于不再與任何程序?qū)嶓w存在綁定關(guān)系而成為了無用的數(shù)據(jù)。它會在之后的某一時刻被Go語言的垃圾回收器發(fā)現(xiàn)并回收。
(4).判斷是否包含某個元素值。
//方法Contains用于判斷其值是否包含某個元素值。
//這里判斷結(jié)果得益于元素類型為bool的字段m
func (set *HashSet) Contains(e interface{}) bool {
return set.m[e]
}
當(dāng)把一個 interface{} 類型值作為鍵添加到一個字典值的時候，Go語言會先獲取這個 interface{} 類型值的實際類型（即動態(tài)類型），然后再使用與之對應(yīng)的 hash 函數(shù)對該值進行 hash 運算，也就是說，interface{} 類型值總是能夠被正確地計算出 hash 值。但是字典類型的鍵不能是函數(shù)類型、字典類型或切片類型，否則會引發(fā)一個運行時恐慌，并提示如下：
panic: runtime error: hash of unhashable type 某個函數(shù)類型、字典類型或切片類型的名稱>
(5).獲取元素值的數(shù)量。
//方法Len用于獲取HashSet元素值數(shù)量
func (set *HashSet) Len() int {
return len(set.m)
}
(6).判斷與其他HashSet類型值是否相同。
//方法Same用來判斷兩個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
}
兩個 HashSet 類型值相同的必要條件是，它們包含的元素應(yīng)該是完全相同的。由于 HashSet 類型值中的元素的迭代順序總是不確定的，所以也就不用在意兩個值在這方面是否一致。如果要判斷兩個 HashSet 類型值是否是同一個值，就需要利用指針運算進行內(nèi)存地址的比較。
(7).獲取所有元素值，即生成可迭代的快照。
所謂 快照，就是目標(biāo)值在某一個時刻的映像。對于一個 HashSet 類型值來說，它的快照中的元素迭代順序總是可以確定的，快照只反映了該 HashSet 類型值在某一個時刻的狀態(tài)。另外，還需要從元素可迭代且順序可確定的數(shù)據(jù)類型中選取一個作為快照的類型。這個類型必須是以單值作為元素的，所以字典類型最先別排除。又由于 HashSet 類型值中的元素數(shù)量總是不固定的，所以無法用一個數(shù)組類型的值來表示它的快照。如上分析可知，Go語言中可以使用的快照的類型應(yīng)該是一個切片類型或者通道類型。
//方法Elements用于生成快照
func (set *HashSet) Elements() []interface{} {
initialLen := len(set.m)//獲取HashSet中字段m的長度，即m中包含元素的數(shù)量
//初始化一個[]interface{}類型的變量snapshot來存儲m的值中的元素值
snapshot := make([]interface{}, initialLen)
actualLen := 0
//按照既定順序?qū)⒌翟O(shè)置到快照值(變量snapshot的值)的指定元素位置上,這一過程并不會創(chuàng)建任何新值。
for key := range set.m {
if actualLen initialLen {
snapshot[actualLen] = key
} else {//m的值中的元素數(shù)量有所增加，使得實際迭代的次數(shù)大于先前初始化的快照值的長度
snapshot = append(snapshot, key)//使用append函數(shù)向快照值追加元素值。
}
actualLen++//實際迭代的次數(shù)
}
//對于已被初始化的[]interface{}類型的切片值來說，未被顯示初始化的元素位置上的值均為nil。
//m的值中的元素數(shù)量有所減少，使得實際迭代的次數(shù)小于先前初始化的快照值的長度。
//這樣快照值的尾部存在若干個沒有任何意義的值為nil的元素，
//可以通過snapshot = snapshot[:actualLen]將無用的元素值從快照值中去掉。
if actualLen initialLen {
snapshot = snapshot[:actualLen]
}
return snapshot
}
注意：在 Elements 方法中針對并發(fā)訪問和修改 m 的值的情況采取了一些措施。但是由于m的值本身并不是并發(fā)安全的，所以并不能保證 Elements 方法的執(zhí)行總會準(zhǔn)確無誤。要做到真正的并發(fā)安全，還需要一些輔助的手段，比如讀寫互斥量。
(8).獲取自身的字符串表示形式。
//這個String方法的簽名算是一個慣用法。 //代碼包fmt中的打印函數(shù)總會使用參數(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) {//最后一個元素的后面不添加逗號
// break;
// } else {
// buf.WriteString(",")
// }
// n++;
//}
buf.WriteString("}")
return buf.String()
}
如上已經(jīng)完整地編寫了一個具備常用功能的Set的實現(xiàn)類型，后面將講解更多的高級功能來完善它。
3.高級功能
集合 Set 的真包含的判斷功能。根據(jù)集合代數(shù)中的描述，如果集合 A 真包含了集合 B，那么就可以說集合 A 是集合 B 的一個超集。
// 判斷集合 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的元素數(shù)量
return false
}
if setLen > 0 otherLen == 0 {//other為元素數(shù)量為0，set元素數(shù)量大于0，則set也是other的超集
return true
}
for _, v := range other.Elements() {
if !set.Contains(v) {//只要set中有一個包含other中的數(shù)據(jù)，就返回false
return false
}
}
return true
}
集合的運算包括并集、交集、差集和對稱差集。
并集運算是指把兩個集合中的所有元素都合并起來并組合成一個集合。
交集運算是指找到兩個集合中共有的元素并把它們組成一個集合。
集合 A 對集合 B 進行差集運算的含義是找到只存在于集合 A 中但不存在于集合 B 中的元素并把它們組成一個集合。
對稱差集運算與差集運算類似但有所區(qū)別。對稱差集運算是指找到只存在于集合 A 中但不存在于集合 B 中的元素，再找到只存在于集合 B 中但不存在于集合 A 中的元素，最后把它們合并起來并組成一個集合。
實現(xià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)建一個HashSet類型值，它的長度為0，即元素數(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
}
實現(xià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)建一個HashSet類型值，它的長度為0，即元素數(shù)量為0
if other.Len() == 0 {//other的元素數(shù)量為0，直接返回intersectedSet
return intersectedSet
}
if set.Len() other.Len() {//set的元素數(shù)量少于other的元素數(shù)量
for _, v := range set.Elements() {//遍歷set
if other.Contains(v) {//只要將set和other共有的添加到intersectedSet
intersectedSet.Add(v)
}
}
} else {//set的元素數(shù)量多于other的元素數(shù)量
for _, v := range other.Elements() {//遍歷other
if set.Contains(v) {//只要將set和other共有的添加到intersectedSet
intersectedSet.Add(v)
}
}
}
return intersectedSet
}
差集
// 生成集合 set 對集合 other 的差集
func (set *HashSet) Difference(other *HashSet) *HashSet {
if set == nil || other == nil {// set和other都為nil，則它們的差集為nil
return nil
}
differencedSet := NewHashSet()//新創(chuàng)建一個HashSet類型值，它的長度為0，即元素數(shù)量為0
if other.Len() == 0 { // 如果other的元素數(shù)量為0
for _, v := range set.Elements() {//遍歷set，并將set中的元素v添加到differencedSet
differencedSet.Add(v)
}
return differencedSet//直接返回differencedSet
}
for _, v := range set.Elements() {//other的元素數(shù)量不為0，遍歷set
if !other.Contains(v) {//如果other中不包含v，就將v添加到differencedSet中
differencedSet.Add(v)
}
}
return differencedSet
}
對稱差集
// 生成集合 one 和集合 other 的對稱差集
func (set *HashSet) SymmetricDifference(other *HashSet) *HashSet {
if set == nil || other == nil {// set和other都為nil，則它們的對稱差集為nil
return nil
}
diffA := set.Difference(other)//生成集合 set 對集合 other 的差集
if other.Len() == 0 {//如果other的元素數(shù)量等于0，那么other對集合set的差集為空，則直接返回diffA
return diffA
}
diffB := other.Difference(set)//生成集合 other 對集合 set 的差集
return diffA.Union(diffB)//返回集合 diffA 和集合 diffB 的并集
}
4.進一步重構(gòu)
目前所實現(xiàn)的 HashSet 類型提供了一些必要的集合操作功能，但是不同應(yīng)用場景下可能會需要使用功能更加豐富的集合類型。當(dāng)有多個集合類型的時候，應(yīng)該在它們之上抽取出一個接口類型以標(biāo)識它們共有的行為方式。依據(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 方法有所不同。這里不能再接口類型的方法的簽名中包含它的實現(xiàn)類型。因此這里的改動如下：
func (set *HashSet) Same(other Set) bool {
//省略若干語句
}
修改了 Same 方法的簽名，目的是讓 *HashSet 類型成為 Set 接口類型的一個實現(xiàn)類型。
高級功能的方法應(yīng)該適用于所有的實現(xiàn)類型，完全可以抽離出成為獨立的函數(shù)。并且，也不應(yīng)該在每個實現(xiàn)類型中重復(fù)地實現(xiàn)這些高級方法。如下為改造后的 IsSuperset 方法的聲明：
// 判斷集合 one 是否是集合 other 的超集
// 讀者應(yīng)重點關(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語言之自定義集合Set的全部內(nèi)容，希望對大家學(xué)習(xí)Go語言有所幫助。
您可能感興趣的文章:- Golang中的自定義函數(shù)詳解
- golang對自定義類型進行排序的解決方法
- goLang引入自定義包的方法
