Go map key類型分析

1 map的key類型

map中的key可以是任何的類型，只要它的值能比較是否相等，Go的語(yǔ)言規(guī)范已精確定義，Key的類型可以是：

• 布爾值
• 數(shù)字
• 字符串
• 指針
• 通道
• 接口類型
• 結(jié)構(gòu)體
• 只包含上述類型的數(shù)組

但不能是：

• slice
• map
• function

Key類型只要能支持和!=操作符，即可以做為Key，當(dāng)兩個(gè)值時(shí)，則認(rèn)為是同一個(gè)Key。

2 比較相等

我們先看一下樣例代碼：

**package** main

**import** "fmt"

**type** _key **struct** {
}

**type** point **struct** {
	x **int**
	y **int**
}

**type** pair **struct** {
	x **int**
	y **int**
}

**type** Sumer **interface** {
	Sum() **int**
}

**type** Suber **interface** {
	Sub() **int**
}

**func** (p *pair) Sum() **int** {
	**return** p.x + p.y
}

**func** (p *point) Sum() **int** {
	**return** p.x + p.y
}

**func** (p pair) Sub() **int** {
	**return** p.x - p.y
}

**func** (p point) Sub() **int** {
	**return** p.x - p.y
}

**func** main() {
	fmt.Println("_key{} == _key{}: ", _key{} == _key{}) // output: true

	fmt.Println("point{} == point{}: ", point{x: 1, y: 2} == point{x: 1, y: 2})     // output: true
	fmt.Println("&point{} == &point{}: ", &point{x: 1, y: 2} == &point{x: 1, y: 2}) // output: false

	fmt.Println("[2]point{} == [2]point{}: ", 
	  [2]point{point{x: 1, y: 2}, point{x: 2, y: 3}} == [2]point{point{x: 1, y: 2}, point{x: 2, y: 3}}) //output: true

	**var** a Sumer = &pair{x: 1, y: 2}
	**var** a1 Sumer = &pair{x: 1, y: 2}
	**var** b Sumer = &point{x: 1, y: 2}
	fmt.Println("Sumer.byptr == Sumer.byptr: ", a == b)        // output: false
	fmt.Println("Sumer.sametype == Sumer.sametype: ", a == a1) // output: false

	**var** c Suber = pair{x: 1, y: 2}
	**var** d Suber = point{x: 1, y: 2}
	**var** d1 point = point{x: 1, y: 2}
	fmt.Println("Suber.byvalue == Suber.byvalue: ", c == d)  // output: false
	fmt.Println("Suber.byvalue == point.byvalue: ", d == d1) // output: true

	ci1 := make(**chan** **int**, 1)
	ci2 := ci1
	ci3 := make(**chan** **int**, 1)
	fmt.Println("chan int == chan int: ", ci1 == ci2) // output: true
	fmt.Println("chan int == chan int: ", ci1 == ci3) // output: false
}

上面的例子讓我們較直觀地了解結(jié)構(gòu)體，數(shù)組，指針，chan在什么場(chǎng)景下是相等。我們?cè)賮?lái)看Go語(yǔ)言規(guī)范中是怎么說(shuō)的：

• Pointer values are comparable. Two pointer values are equal if they point to the same variable or if both have value nil. Pointers to distinct zero-size variables may or may not be equal.當(dāng)指針指向同一變量，或同為nil時(shí)指針相等，但指針指向不同的零值時(shí)可能不相等。
• Channel values are comparable. Two channel values are equal if they were created by the same call to make or if both have value nil.Channel當(dāng)指向同一個(gè)make創(chuàng)建的或同為nil時(shí)才相等
• Interface values are comparable. Two interface values are equal if they have identical dynamic types and equal dynamic values or if both have value nil.從上面的例子我們可以看出，當(dāng)接口有相同的動(dòng)態(tài)類型并且有相同的動(dòng)態(tài)值，或者值為都為nil時(shí)相等。要注意的是：參考理解Go Interface
• A value x of non-interface type X and a value t of interface type T are comparable when values of type X are comparable and X implements T. They are equal if t’s dynamic type is identical to X and t’s dynamic value is equal to x.如果一個(gè)是非接口類型X的變量x，也實(shí)現(xiàn)了接口T，與另一個(gè)接口T的變量t，只t的動(dòng)態(tài)類型也是類型X，并且他們的動(dòng)態(tài)值相同，則他們相等。
• Struct values are comparable if all their fields are comparable. Two struct values are equal if their corresponding non-blank fields are equal.結(jié)構(gòu)體當(dāng)所有字段的值相同，并且沒(méi)有 相應(yīng)的非空白字段時(shí)，則他們相等，
• Array values are comparable if values of the array element type are comparable. Two array values are equal if their corresponding elements are equal.兩個(gè)數(shù)組只要他們包括的元素，每個(gè)元素的值相同，則他們相等。

注意：Go語(yǔ)言里是無(wú)法重載操作符的，struct是遞歸操作每個(gè)成員變量，struct也可以稱為map的key，但如果struct的成員變量里有不能進(jìn)行==操作的，例如slice，那么就不能作為map的key。

3 類型判斷

判斷兩個(gè)變量是否相等，首先是要判斷變量的動(dòng)態(tài)類型是否相同，在runtime中，_type結(jié)構(gòu)是描述最為基礎(chǔ)的類型（runtime/type.go），而map, slice, array等內(nèi)置的復(fù)雜類型也都有對(duì)應(yīng)的類型描述（如maptype，slicetype，arraytype）。

type _type struct {
	size       uintptr
	ptrdata    uintptr 
	hash       uint32
	tflag      tflag
	align      uint8
	fieldalign uint8
	kind       uint8
	alg        *typeAlg
	gcdata    *byte
	str       nameOff
	ptrToThis typeOff
}
...
type chantype struct {
	typ  _type
	elem *_type
	dir  uintptr
}
...
type slicetype struct {
	typ  _type
	elem *_type
}
...

其中對(duì)于類型的值是否相等，需要使用到成員alg *typeAlg(runtime/alg.go)，它則持有此類型值的hash與equal的算法，它也是一個(gè)結(jié)構(gòu)體:

type typeAlg struct {
	// function for hashing objects of this type
	// (ptr to object, seed) -> hash
	hash func(unsafe.Pointer, uintptr) uintptr
	// function for comparing objects of this type
	// (ptr to object A, ptr to object B) -> ==?
	equal func(unsafe.Pointer, unsafe.Pointer) bool
}

runtime/alg.go中提供了各種基礎(chǔ)的hash func與 equal func，例如：

func strhash(a unsafe.Pointer, h uintptr) uintptr {
	x := (*stringStruct)(a)
	return memhash(x.str, h, uintptr(x.len))
}

func strequal(p, q unsafe.Pointer) bool {
	return *(*string)(p) == *(*string)(q)
}

有了這些基礎(chǔ)的hash func與 equal func，再?gòu)?fù)雜的結(jié)構(gòu)體也可以按字段遞歸計(jì)算hash與相等比較了。那我們?cè)賮?lái)看一下，當(dāng)訪問(wèn)map[key]時(shí)，其實(shí)現(xiàn)對(duì)應(yīng)在runtime/hashmap.go中的mapaccess1函數(shù):

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	...
	alg := t.key.alg
	hash := alg.hash(key, uintptr(h.hash0)) // 1
	m := uintptr(1)<<h.B - 1
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) // 2
	...
	top := uint8(hash >> (sys.PtrSize*8 - 8))
	if top < minTopHash {
		top += minTopHash
	}
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			...
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if alg.equal(key, k) { // 3
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				...
				return v
			}
		}
	...
	}
}

mapaccess1的代碼還是比較多的，簡(jiǎn)化邏輯如下（參考注釋上序列）：

1. 調(diào)用key類型的hash方法，計(jì)算出key的hash值
2. 根據(jù)hash值找到對(duì)應(yīng)的桶bucket
3. 在桶中找到key值相等的map的value。判斷相等需調(diào)用key類型的equal方法

到現(xiàn)在我們也就有了初步了解，map中的key訪問(wèn)時(shí)同時(shí)需要使用該類型的hash func與 equal func，只要key值相等，當(dāng)結(jié)構(gòu)體即使不是同一對(duì)象，也可從map中獲取相同的值，例如：

m := make(map[interface{}]interface{})
m[_key{}] = "value"
if v, ok := m[_key{}];ok {
	fmt.Println("%v", v) // output: value
}

判斷兩個(gè) map 是否相等

比較兩個(gè)map實(shí)例需要使用reflect包的DeepEqual()方法。如果相比較的兩個(gè)map滿足以下條件，方法返回true：

Map values are deeply equal when all of the following are true: they are both nil or both non-nil, they have the same length, and either they are the same map object or their corresponding keys (matched using Go equality) map to deeply equal values.

1.兩個(gè)map都為nil或者都不為nil，并且長(zhǎng)度要相等 they are both nil or both non-nil, they have the same length 2.相同的map對(duì)象或者所有key要對(duì)應(yīng)相同 either they are the same map object or their corresponding keys 3.map對(duì)應(yīng)的value也要深度相等 map to deeply equal values

Go 為什么不在語(yǔ)言層面支持 map 并發(fā)？

為什么原生不支持

憑什么 Go 官方還不支持，難不成太復(fù)雜了，性能太差了，到底是為什么？
官方答復(fù)原因如下（via @go faq）：

• 典型使用場(chǎng)景：map 的典型使用場(chǎng)景是不需要從多個(gè) goroutine 中進(jìn)行安全訪問(wèn)。
• 非典型場(chǎng)景（需要原子操作）：map 可能是一些更大的數(shù)據(jù)結(jié)構(gòu)或已經(jīng)同步的計(jì)算的一部分。
• 性能場(chǎng)景考慮：若是只是為少數(shù)程序增加安全性，導(dǎo)致 map 所有的操作都要處理 mutex，將會(huì)降低大多數(shù)程序的性能。

核心來(lái)講就是：Go 團(tuán)隊(duì)在經(jīng)過(guò)了長(zhǎng)時(shí)間的討論后，認(rèn)為原生 map 更應(yīng)適配典型使用場(chǎng)景。
如果為了小部分情況，將會(huì)導(dǎo)致大部分程序付出性能代價(jià)，決定了不支持原生的并發(fā) map 讀寫。且在 Go1.6 起，增加了檢測(cè)機(jī)制，并發(fā)的話會(huì)導(dǎo)致異常。

為什么要崩潰

前面有提到一點(diǎn)，在 Go1.6 起會(huì)進(jìn)行原生 map 的并發(fā)檢測(cè)，這是一些人的 “噩夢(mèng)”。
在此有人吐槽到：“明明給我拋個(gè)錯(cuò)就好了，憑什么要讓我的 Go 進(jìn)程直接崩潰掉，分分鐘給我背個(gè) P0”。

場(chǎng)景枚舉

這里我們假設(shè)一下，如果并發(fā)讀寫 map 是以下兩種場(chǎng)景：

1. 產(chǎn)生 panic：程序 panic -> 默認(rèn)走進(jìn) recover -> 沒(méi)有對(duì)并發(fā) map 進(jìn)行處理 -> map 存在臟數(shù)據(jù) -> 程序使用臟數(shù)據(jù) -> 產(chǎn)生**未知((影響。
2. 產(chǎn)生 crash：程序 crash -> 直接崩潰 -> 保全數(shù)據(jù)（數(shù)據(jù)正常）-> 產(chǎn)生**明確((風(fēng)險(xiǎn)。

你會(huì)選擇哪一種方案呢？Go 官方在兩者的風(fēng)險(xiǎn)衡量中選擇了第二種。
無(wú)論是編程，還是人生。如何在隨機(jī)性中掌握確定性的部分，也是一門極大的哲學(xué)了。

let it crash

Go 官方團(tuán)隊(duì)選擇的方式是業(yè)內(nèi)經(jīng)典的 “l(fā)et it crash” 行為，很多編程語(yǔ)言中，都會(huì)將其奉行為設(shè)計(jì)哲學(xué)。
let it crash 是指工程師不必過(guò)分擔(dān)心未知的錯(cuò)誤，而去進(jìn)行面面俱到的防御性編碼。
這塊理念最經(jīng)典的就是 erlang 了。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-790957.html

到了這里，關(guān)于go 語(yǔ)言中 map 的相關(guān)知識(shí)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！