回顧前景

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

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) }}

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

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

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

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

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

map的實際類型

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

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

type StringData struct{Data uintptr,DataLen int,}

所以，我們獲取到string的數(shù)據(jù)長度是16，那么咱們來試試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是不是就是保存的就是一個map的地址值，如果就是一個地址值，那么就應(yīng)該是和uintptr的大小一致，然后咱們?nèi)〉眠@個mp的實際地址值，如果沒有初始化，那么這個地址肯定是空，也就是0，然后make之后，肯定就有一個地址值了，通過這一個代碼，我們就可以直接確定，在go語言中，咱們寫的map變量中存放的實際上就是map的地址指針。

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

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

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

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 //這下面是動態(tài)結(jié)構(gòu)，是編譯期間根據(jù)KV類型動態(tài)生成的,這里測試使用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的個數(shù)為：", hmp.count)}

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

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

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

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

查詢方式

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

破題

通過上面這一系列的對應(yīng)拆解，咱們再來看看最開始的那個問題是為啥子

首先，存入到map的時候，實際上會先計算出一個key的hash值

通過計算的哈希值，然后找到對應(yīng)的哈希桶

將鍵值數(shù)據(jù)存入到哈希桶中去

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

附加

有網(wǎng)友，說最好加上一個能定位到同一個哈希桶內(nèi)部查找到的修改實現(xiàn)方式，所以，就將代碼調(diào)整了一下，加上了一個哈希碰撞的調(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的個數(shù)為：”, hmp.count)//通過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 {//沒有找到對應(yīng)的桶,就從oldbuckets查找}//下面來搞一個可以找到的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(“碰撞到一個匹配到同一個哈希桶的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(“通過自己實現(xiàn)的匹配模式,找到了key=”, str, “的值為:”, bucketPointer.values[i])break}}} else {//沒有找到對應(yīng)的桶,就從oldbuckets查找}fmt.Println(“碰撞到的匹配的key=” + str + “,value=” + mp[str])}

此時就行了。

鄭重聲明：本文內(nèi)容及圖片均整理自互聯(lián)網(wǎng)，不代表本站立場，版權(quán)歸原作者所有，如有侵權(quán)請聯(lián)系管理員(admin#wlmqw.com)刪除。