回顧前景

在上一節(jié)中，咱們留了一個(gè)代碼：

func main() { buffer := []byte(“test”) stringData := reflect.StringHeader{ Data: uintptr(unsafe.Pointer(&buffer[0])), Len: len(buffer), } str := *(*string)(unsafe.Pointer(&stringData)) mmp := make(map[string]int, 32) mmp[str] = 3 mmp[“abcd”] = 4 fmt.Println(mmp[str]) buffer[0] = ‘a’ buffer[1] = ‘b’ buffer[2] = ‘c’ buffer[3] = ‘d’ fmt.Println(mmp[str]) fmt.Println(mmp[“test”]) fmt.Println(mmp[“abcd”]) for k, v := range mmp { fmt.Println(k, v) }}

然后可以看看這個(gè)輸出的結(jié)果，并留了一個(gè)為什么，不知道有木有朋友們思考到位了，咱們今天來(lái)合計(jì)合計(jì)這個(gè)問(wèn)題。

map的結(jié)構(gòu)分析

咱們初次接觸GO的時(shí)候，已經(jīng)被明確告知了，go語(yǔ)言中map是一個(gè)指針，必須要使用 make初始化之后才可以使用，咱們傳遞map的時(shí)候， 傳遞的也是map的這個(gè)指針，并不會(huì)復(fù)制map內(nèi)部的數(shù)據(jù)內(nèi)容，那么這個(gè)map的結(jié)構(gòu)到底是如何的呢，這一塊，在go源碼的runtimemap.go中可以窺探一二，對(duì)于這一塊的源碼分析，網(wǎng)上也有比較詳盡的資料可以查看。

不過(guò)由于Go在編譯期間做了不少事情，比如編譯的時(shí)候根據(jù)map類型來(lái)生成實(shí)際的map結(jié)構(gòu)，填充里面的數(shù)據(jù)等，這一塊實(shí)際上都是在編譯期間做的，源碼中并沒(méi)有完整的包含這些，只是一個(gè)可以抽象出所有數(shù)據(jù)的一個(gè)外殼，所以，基礎(chǔ)上比較薄弱，沒(méi)有相應(yīng)的知識(shí)的朋友們可能看起來(lái)比較糊涂，看完了，可能也是迷迷糊糊的，比如說(shuō)，之前說(shuō)過(guò)很多次的，go的字符串類型實(shí)際上是一個(gè)結(jié)構(gòu)體，那么map得實(shí)際類型到底是個(gè)啥呢。

下面就來(lái)對(duì)map做一個(gè)一一對(duì)應(yīng)的分解，并且將對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以及編譯之后對(duì)應(yīng)的數(shù)據(jù)類型一一地通過(guò)代碼的形式分解出來(lái)。

map的實(shí)際類型

map的格式是指針，這是第一要素，那么我們首先第一步，直接先獲取一下，map的內(nèi)容大小,這個(gè)可以使用unsafe.Sizeof來(lái)獲取到

前面我們說(shuō)過(guò)string實(shí)際上是一個(gè)結(jié)構(gòu)體如下

type StringData struct{Data uintptr,DataLen int,}

所以，我們獲取到string的數(shù)據(jù)長(zhǎng)度是16，那么咱們來(lái)試試map的

func main() { var mp map[string]int if unsafe.Sizeof(mp) == unsafe.Sizeof(uintptr(0)) { pmp := unsafe.Pointer(&mp) fmt.Println(“mp指向的map地址：”, *(*int)(pmp)) mp = make(map[string]int) fmt.Println(“mp初始化之后指向的map地址：”, *(*int)(pmp)) } else { fmt.Println(unsafe.Sizeof(mp)) }}

我們先判定，mp是不是就是保存的就是一個(gè)map的地址值，如果就是一個(gè)地址值，那么就應(yīng)該是和uintptr的大小一致，然后咱們?nèi)〉眠@個(gè)mp的實(shí)際地址值，如果沒(méi)有初始化，那么這個(gè)地址肯定是空，也就是0，然后make之后，肯定就有一個(gè)地址值了，通過(guò)這一個(gè)代碼，我們就可以直接確定，在go語(yǔ)言中，咱們寫的map變量中存放的實(shí)際上就是map的地址指針。

在上面獲取map的實(shí)際地址值上是有一個(gè)技巧的，就是是通過(guò)取地址的地址，然后推導(dǎo)出來(lái)的結(jié)果，從而拿到了map實(shí)際的地址值，因?yàn)間o的編譯器限定了，又不能直接像C，C++等之類的語(yǔ)言，直接做強(qiáng)制轉(zhuǎn)換，所以，只有拿到地址之后，用地址來(lái)做強(qiáng)制轉(zhuǎn)換，這個(gè)就是指針類的好處了，獲取了內(nèi)存結(jié)構(gòu)之后，指針就不在乎數(shù)據(jù)形式了，你想他是什么都行，只是內(nèi)存中的一塊數(shù)據(jù)而已。

解構(gòu)map解構(gòu)hmap

結(jié)合runtime中的map.go，我們可以知道，實(shí)際上map的結(jié)構(gòu)就是hmap,所以呢，實(shí)際上，咱們?cè)趃o代碼中寫的map，就是*hmap的指針值。那么咱么來(lái)解構(gòu)一下，上面也說(shuō)了，go由于編譯器的限制不能直接強(qiáng)制轉(zhuǎn)換，所以，咱們只有先獲取地址，然后通過(guò)地址來(lái)轉(zhuǎn)，那么go代碼中的map實(shí)際上就是 *hmap,所以第一步取地址&mp獲取到的實(shí)際上就是地址的地址也就是 **hmap，所以，然后解指針一下就可以獲取到實(shí)際的結(jié)構(gòu)了,首先，咱們將go的runtime/map.go中的hmap相關(guān)的結(jié)構(gòu)拷貝進(jìn)來(lái)，然后改造改造試下

type mapextra struct {// If both key and elem do not contain pointers and are inline, then we mark bucket// type as containing no pointers. This avoids scanning such maps.// However, bmap.overflow is a pointer. In order to keep overflow buckets// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.// overflow and oldoverflow are only used if key and elem do not contain pointers.// overflow contains overflow buckets for hmap.buckets.// oldoverflow contains overflow buckets for hmap.oldbuckets.// The indirection allows to store a pointer to the slice in hiter.overflow *[]*bmapoldoverflow *[]*bmap// nextOverflow holds a pointer to a free overflow bucket.nextOverflow *bmap}const ( // Maximum number of key/elem pairs a bucket can hold. bucketCntBits = 3 bucketCnt = 1 hash hasher func(unsafe.Pointer, uintptr) uintptr keysize uint8 // size of key slot valuesize uint8 // size of value slot bucketsize uint16 // size of bucket flags uint32}type emptyInterface struct { typ *rtype word unsafe.Pointer}// PtrSize is the size of a pointer in bytes – unsafe.Sizeof(uintptr(0)) but as an ideal constant.// It is also the size of the machine’s native word size (that is, 4 on 32-bit systems, 8 on 64-bit).const PtrSize = 4 63)// bucketShift returns 1<<b, optimized for code generation.func bucketShift(b uint8) uintptr { // Masking the shift amount allows overflow checks to be elided. return uintptr(1) << (b & (PtrSize*8 – 1))}// bucketMask returns 1<<b – 1, optimized for code generation.func bucketMask(b uint8) uintptr { return bucketShift(b) – 1}// A bucket for a Go map.type bmap struct { // tophash generally contains the top byte of the hash value // for each key in this bucket. If tophash[0] < minTopHash, // tophash[0] is a bucket evacuation state instead. tophash [bucketCnt]uint8 //這下面是動(dòng)態(tài)結(jié)構(gòu)，是編譯期間根據(jù)KV類型動(dòng)態(tài)生成的,這里測(cè)試使用string類型 keys [8]string values [8]string overflow uintptr}type hmap struct { // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go. // Make sure this stays in sync with the compiler's definition. count int // # live cells == size of map. Must be first (used by len() builtin) flags uint8 B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details hash0 uint32 // hash seed buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) extra *mapextra // optional fields}func main() {mp := make(map[string]string, 32)mp["tt"] = "tt"mp["tt1"] = "551"fmt.Println(unsafe.Sizeof(mp))var hmp *hmaphmp = *(**hmap)(unsafe.Pointer(&mp))fmt.Println("map的個(gè)數(shù)為：", hmp.count)}

這里面改造的地方，只是在bmap結(jié)構(gòu)中，將我們需要的類型補(bǔ)齊了，其他的沒(méi)怎么變動(dòng)

map的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)以及map的類型結(jié)構(gòu)

map的本質(zhì)實(shí)際上是一個(gè)哈希表，而對(duì)應(yīng)的key不同，哈希函數(shù)肯定不同，同時(shí)，哈希表中存儲(chǔ)的key,value的結(jié)構(gòu)肯定也是動(dòng)態(tài)的，但是runtime的map.go中只是給了一個(gè)通用的元素存儲(chǔ)就結(jié)構(gòu)bmap,而大家可以看到我上面的代碼key是string,value也是string，所以在runtime/map.go的bmp的結(jié)構(gòu)的基礎(chǔ)上加上了keys [8]string和values [8]string以及overflow uintptr幾個(gè)結(jié)構(gòu)，這就說(shuō)明了實(shí)際上這一塊數(shù)據(jù)內(nèi)容是在編譯期間動(dòng)態(tài)填充進(jìn)去的，詳細(xì)的內(nèi)容，不細(xì)說(shuō)了，網(wǎng)上有對(duì)應(yīng)的說(shuō)明，只標(biāo)記一點(diǎn)，如果是別的類型，則這里對(duì)應(yīng)的就是別的數(shù)據(jù)類型，同時(shí)針對(duì)每一個(gè)map結(jié)構(gòu)，其都有一個(gè)mapType結(jié)構(gòu)，記錄了這個(gè)哈希表的類型結(jié)構(gòu)

type mapType struct {rtypekey *rtype // map key typeelem *rtype // map element (value) typebucket *rtype // internal bucket structure// function for hashing keys (ptr to key, seed) -> hashhasher func(unsafe.Pointer, uintptr) uintptrkeysize uint8 // size of key slotvaluesize uint8 // size of value slotbucketsize uint16 // size of bucketflags uint32}

這個(gè)結(jié)構(gòu)中就記錄了key類型，元素類型，以及哈希函數(shù)以及key大小，value大小，哈希桶大小等

查詢方式

這一塊，基本上就是是對(duì) key 進(jìn)行 hash 計(jì)算，計(jì)算后用 low bits 和高 8 位 hash 找到對(duì)應(yīng)哈希桶的位置，然后再去桶中查找，這一塊map.go中有，可以直接將相關(guān)代碼搬出來(lái)，就行了，這里主要的代碼要素是要找到這個(gè)key計(jì)算的哈希函數(shù)，而哈希函數(shù)在mapType中記錄著，所以，最主要的就是找到map對(duì)應(yīng)的mapType，給一個(gè)最簡(jiǎn)單的辦法哈，就是用interface做一個(gè)中轉(zhuǎn)，然后通過(guò)interface獲取結(jié)構(gòu)類型就可以搞定了，咱們可以寫一個(gè)簡(jiǎn)單的查詢某個(gè)key的值得代碼如下

func main() { mp := make(map[string]string, 32) mp[“tt”] = “tt” mp[“tt1”] = “551” fmt.Println(unsafe.Sizeof(mp)) var hmp *hmap hmp = *(**hmap)(unsafe.Pointer(&mp)) fmt.Println(“map的個(gè)數(shù)為：”, hmp.count) //通過(guò)interface獲取mapType結(jié)構(gòu)，然后獲取到他的hash函數(shù) var mpInterface interface{} mpInterface = mp eface := *(*emptyInterface)(unsafe.Pointer(&mpInterface)) mpType := (*mapType)(unsafe.Pointer(eface.typ)) fmt.Println(“桶大小：”, mpType.bucketsize) key := “tt” keyHash := mpType.hasher(unsafe.Pointer(&key), uintptr(hmp.hash0)) m := bucketMask(hmp.B) bucketPointer := (*bmap)(unsafe.Pointer(uintptr(hmp.buckets) + (keyHash&m)*uintptr(mpType.bucketsize))) if bucketPointer != nil { //找到了桶了，直接從桶中查找 for i := range bucketPointer.keys { if bucketPointer.keys[i] == key { fmt.Println(“找到了key=”, key, “的值為:”, bucketPointer.values[i]) break } } } else { //沒(méi)有找到對(duì)應(yīng)的桶,就從oldbuckets查找 }}

破題

通過(guò)上面這一系列的對(duì)應(yīng)拆解，咱們?cè)賮?lái)看看最開(kāi)始的那個(gè)問(wèn)題是為啥子

而如果咱們將已經(jīng)存入了哈希表中的某個(gè)字符串key的地址的數(shù)據(jù)值改了，而此時(shí)key并不知道他的值改了，所以此時(shí)這個(gè)鍵值的位置不會(huì)變動(dòng)，依然是在原先那個(gè)哈希桶。那么如果這個(gè)時(shí)候使用原來(lái)的字符串key訪問(wèn)，此時(shí)hash計(jì)算出來(lái)的結(jié)果和原結(jié)果一致，所以能找到對(duì)應(yīng)的哈希桶，但是找到了哈希桶之后，比對(duì)哈希桶中的元素的key的時(shí)候，無(wú)法匹配，所以此時(shí)就找不到了。那么如果使用改變后的字符串key去訪問(wèn)map，此時(shí)如果計(jì)算出來(lái)的哈希值然后找到的哈希桶和原始哈希桶相同，那么就能夠找到這個(gè)新值，如果計(jì)算出來(lái)的哈希桶和原始哈希桶不同，那么就肯定找不到這個(gè)值了。于是破題得證

附加

有網(wǎng)友，說(shuō)最好加上一個(gè)能定位到同一個(gè)哈希桶內(nèi)部查找到的修改實(shí)現(xiàn)方式，所以，就將代碼調(diào)整了一下，加上了一個(gè)哈希碰撞的調(diào)整

func main() {mp := make(map[string]string, 32)mp[“tt”] = “tt”mp[“tt1”] = “551”fmt.Println(unsafe.Sizeof(mp))var hmp *hmaphmp = *(**hmap)(unsafe.Pointer(&mp))fmt.Println(“map的個(gè)數(shù)為：”, hmp.count)//通過(guò)interface獲取mapType結(jié)構(gòu)，然后獲取到他的hash函數(shù)var mpInterface interface{}mpInterface = mpeface := *(*emptyInterface)(unsafe.Pointer(&mpInterface))mpType := (*mapType)(unsafe.Pointer(eface.typ))fmt.Println(“桶大?。?#8221;, mpType.bucketsize)key := “tt”keyHash := mpType.hasher(unsafe.Pointer(&key), uintptr(hmp.hash0))m := bucketMask(hmp.B)bucketPointer := (*bmap)(unsafe.Pointer(uintptr(hmp.buckets) + (keyHash&m)*uintptr(mpType.bucketsize)))if bucketPointer != nil {//找到了桶了，直接從桶中查找for i := range bucketPointer.keys {if bucketPointer.keys[i] == key {fmt.Println(“找到了key=”, key, “的值為:”, bucketPointer.values[i])break}}} else {//沒(méi)有找到對(duì)應(yīng)的桶,就從oldbuckets查找}//下面來(lái)搞一個(gè)可以找到的buffer := []byte(“test”)stringData := reflect.StringHeader{Data: uintptr(unsafe.Pointer(&buffer[0])),Len: len(buffer),}str := *(*string)(unsafe.Pointer(&stringData))mp[str] = strfmt.Println(“原始key=” + str + “,value=” + mp[str])chars := []byte(“abcdefghijklmnobjqrstuvwxyz”)keyHash = mpType.hasher(unsafe.Pointer(&str), uintptr(hmp.hash0))bucketIndex := keyHash & mtop := tophash(keyHash)for {buffer[0] = chars[rand.Intn(len(chars))]buffer[1] = chars[rand.Intn(len(chars))]buffer[2] = chars[rand.Intn(len(chars))]buffer[3] = chars[rand.Intn(len(chars))]newHash := mpType.hasher(unsafe.Pointer(&str), uintptr(hmp.hash0))if newHash&m == bucketIndex && tophash(newHash) == top {fmt.Println(“碰撞到一個(gè)匹配到同一個(gè)哈希桶的key：”, str)break}}keyHash = mpType.hasher(unsafe.Pointer(&str), uintptr(hmp.hash0))bucketPointer = (*bmap)(unsafe.Pointer(uintptr(hmp.buckets) + (keyHash&m)*uintptr(mpType.bucketsize)))if bucketPointer != nil {//找到了桶了，直接從桶中查找for i := range bucketPointer.keys {if bucketPointer.keys[i] == str {fmt.Println(“通過(guò)自己實(shí)現(xiàn)的匹配模式,找到了key=”, str, “的值為:”, bucketPointer.values[i])break}}} else {//沒(méi)有找到對(duì)應(yīng)的桶,就從oldbuckets查找}fmt.Println(“碰撞到的匹配的key=” + str + “,value=” + mp[str])}

此時(shí)就行了。