這篇文章主要介紹“Go語(yǔ)言中如何自定義Set集合”,在日常操作中,相信很多人在Go語(yǔ)言中如何自定義Set集合問題上存在疑惑,小編查閱了各式資料,整理出簡(jiǎn)單好用的操作方法,希望對(duì)大家解答”Go語(yǔ)言中如何自定義Set集合”的疑惑有所幫助!接下來(lái),請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧!
成都創(chuàng)新互聯(lián)是專業(yè)的興業(yè)網(wǎng)站建設(shè)公司,興業(yè)接單;提供成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、成都外貿(mào)網(wǎng)站建設(shè)公司,網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行興業(yè)網(wǎng)站開發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!一、Go語(yǔ)言實(shí)戰(zhàn)——自定義集合Set
在Go語(yǔ)言中有作為Hash Table實(shí)現(xiàn)的字典(Map)類型,但標(biāo)準(zhǔn)數(shù)據(jù)類型中并沒有集合(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)化版本。也就是說,可以用 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)橥ㄟ^將字典 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)說,如下:
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í)候再予以說明。
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è)引用類型的字段,但是這也是一種開銷。而且這里還沒有考慮 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)算,也就是說,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)說,它的快照中的元素迭代順序總是可以確定的,快照只反映了該 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的值)的指定元素位置上,這一過程并不會(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)說,未被顯示初始化的元素位置上的值均為nil。 //m的值中的元素?cái)?shù)量有所減少,使得實(shí)際迭代的次數(shù)小于先前初始化的快照值的長(zhǎng)度。 //這樣快照值的尾部存在若干個(gè)沒有任何意義的值為nil的元素, //可以通過snapshot = snapshot[:actualLen]將無(wú)用的元素值從快照值中去掉。 if actualLen < initialLen { snapshot = snapshot[:actualLen] } return snapshot }
注意:在 Elements方法中針對(duì)并發(fā)訪問和修改 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,那么就可以說集合 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)注創(chuàng)新互聯(lián)網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章!
當(dāng)前文章:Go語(yǔ)言中如何自定義Set集合-創(chuàng)新互聯(lián)
本文鏈接:http://redsoil1982.com.cn/article38/hpjpp.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供ChatGPT、網(wǎng)站內(nèi)鏈、虛擬主機(jī)、面包屑導(dǎo)航、網(wǎng)站收錄、靜態(tài)網(wǎng)站
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容