回顾前景

在上一节中，咱们留了一个代码：

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

然后可以看看这个输出的结果，并留了一个为什么，不知道有木有朋友们思考到位了，咱们今天来合计合计这个问题。

map的结构分析

咱们初次接触GO的时候，已经被明确告知了，go语言中map是一个指针，必须要使用 make初始化之后才可以使用，咱们传递map的时候，传递的也是map的这个指针，并不会复制map内部的数据内容，那么这个map的结构到底是如何的呢，这一块，在go源码的runtimemap.go中可以窥探一二，对于这一块的源码分析，网上也有比较详尽的资料可以查看。

不过由于Go在编译期间做了不少事情，比如编译的时候根据map类型来生成实际的map结构，填充里面的数据等，这一块实际上都是在编译期间做的，源码中并没有完整的包含这些，只是一个可以抽象出所有数据的一个外壳，所以，基础上比较薄弱，没有相应的知识的朋友们可能看起来比较糊涂，看完了，可能也是迷迷糊糊的，比如说，之前说过很多次的，go的字符串类型实际上是一个结构体，那么map得实际类型到底是个啥呢。

下面就来对map做一个一一对应的分解，并且将对应的数据结构，以及编译之后对应的数据类型一一地通过代码的形式分解出来。

map的实际类型

map的格式是指针，这是第一要素，那么我们首先第一步，直接先获取一下，map的内容大小,这个可以使用unsafe.Sizeof来获取到

前面我们说过string实际上是一个结构体如下

type StringData struct{Data uintptr,DataLen int,}

所以，我们获取到string的数据长度是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的地址值，如果就是一个地址值，那么就应该是和uintptr的大小一致，然后咱们取得这个mp的实际地址值，如果没有初始化，那么这个地址肯定是空，也就是0，然后make之后，肯定就有一个地址值了，通过这一个代码，我们就可以直接确定，在go语言中，咱们写的map变量中存放的实际上就是map的地址指针。

在上面获取map的实际地址值上是有一个技巧的，就是是通过取地址的地址，然后推导出来的结果，从而拿到了map实际的地址值，因为go的编译器限定了，又不能直接像C，C++等之类的语言，直接做强制转换，所以，只有拿到地址之后，用地址来做强制转换，这个就是指针类的好处了，获取了内存结构之后，指针就不在乎数据形式了，你想他是什么都行，只是内存中的一块数据而已。

解构map解构hmap

结合runtime中的map.go，我们可以知道，实际上map的结构就是hmap,所以呢，实际上，咱们在go代码中写的map，就是*hmap的指针值。那么咱么来解构一下，上面也说了，go由于编译器的限制不能直接强制转换，所以，咱们只有先获取地址，然后通过地址来转，那么go代码中的map实际上就是 *hmap,所以第一步取地址&mp获取到的实际上就是地址的地址也就是 **hmap，所以，然后解指针一下就可以获取到实际的结构了,首先，咱们将go的runtime/map.go中的hmap相关的结构拷贝进来，然后改造改造试下

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 //这下面是动态结构，是编译期间根据KV类型动态生成的,这里测试使用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的个数为：", hmp.count)}

这里面改造的地方，只是在bmap结构中，将我们需要的类型补齐了，其他的没怎么变动

map的数据存储结构以及map的类型结构

map的本质实际上是一个哈希表，而对应的key不同，哈希函数肯定不同，同时，哈希表中存储的key,value的结构肯定也是动态的，但是runtime的map.go中只是给了一个通用的元素存储就结构bmap,而大家可以看到我上面的代码key是string,value也是string，所以在runtime/map.go的bmp的结构的基础上加上了keys [8]string和values [8]string以及overflow uintptr几个结构，这就说明了实际上这一块数据内容是在编译期间动态填充进去的，详细的内容，不细说了，网上有对应的说明，只标记一点，如果是别的类型，则这里对应的就是别的数据类型，同时针对每一个map结构，其都有一个mapType结构，记录了这个哈希表的类型结构

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}

这个结构中就记录了key类型，元素类型，以及哈希函数以及key大小，value大小，哈希桶大小等

查询方式

这一块，基本上就是是对 key 进行 hash 计算，计算后用 low bits 和高 8 位 hash 找到对应哈希桶的位置，然后再去桶中查找，这一块map.go中有，可以直接将相关代码搬出来，就行了，这里主要的代码要素是要找到这个key计算的哈希函数，而哈希函数在mapType中记录着，所以，最主要的就是找到map对应的mapType，给一个最简单的办法哈，就是用interface做一个中转，然后通过interface获取结构类型就可以搞定了，咱们可以写一个简单的查询某个key的值得代码如下

破题

通过上面这一系列的对应拆解，咱们再来看看最开始的那个问题是为啥子

首先，存入到map的时候，实际上会先计算出一个key的hash值

通过计算的哈希值，然后找到对应的哈希桶

将键值数据存入到哈希桶中去

而如果咱们将已经存入了哈希表中的某个字符串key的地址的数据值改了，而此时key并不知道他的值改了，所以此时这个键值的位置不会变动，依然是在原先那个哈希桶。那么如果这个时候使用原来的字符串key访问，此时hash计算出来的结果和原结果一致，所以能找到对应的哈希桶，但是找到了哈希桶之后，比对哈希桶中的元素的key的时候，无法匹配，所以此时就找不到了。那么如果使用改变后的字符串key去访问map，此时如果计算出来的哈希值然后找到的哈希桶和原始哈希桶相同，那么就能够找到这个新值，如果计算出来的哈希桶和原始哈希桶不同，那么就肯定找不到这个值了。于是破题得证

附加

有网友，说最好加上一个能定位到同一个哈希桶内部查找到的修改实现方式，所以，就将代码调整了一下，加上了一个哈希碰撞的调整

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的个数为：”, hmp.count)//通过interface获取mapType结构，然后获取到他的hash函数var mpInterface interface{}mpInterface = mpeface := *(*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 {//没有找到对应的桶,就从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(“通过自己实现的匹配模式,找到了key=”, str, “的值为:”, bucketPointer.values[i])break}}} else {//没有找到对应的桶,就从oldbuckets查找}fmt.Println(“碰撞到的匹配的key=” + str + “,value=” + mp[str])}

此时就行了。

郑重声明：本文内容及图片均整理自互联网，不代表本站立场，版权归原作者所有，如有侵权请联系管理员(admin#wlmqw.com)删除。