当前位置：网站首页>New solutions to go points (II) map solution

New solutions to go points (II) map solution

2022-07-20 15:20:00 【51CTO】

Review Prospects

In the last section , We left a code ：

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

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

Then you can see the result of this output , And left a why , I don't know if youmu and friends have thought in place , Let's sum up this problem today .

map Structural analysis of

Our first contact GO When , Has been clearly informed ,go In language map It's a pointer , You have to use make After initialization, you can use , Let's pass map When , It's also about map This pointer to , Does not copy map Internal data content , So this map What is the structure of , This piece of , stay go Source code runtime\map.go You can peek into one or two , For this piece of source code analysis , There are also more detailed information available online .

–

But due to the Go A lot of things were done during compilation , For example, when compiling, it is based on map Type to generate the actual map structure , Fill in the data inside , This piece is actually done during compilation , The source code does not completely contain these , It's just a shell that can abstract all the data , therefore , The foundation is relatively weak , Friends without corresponding knowledge may look confused , It's over , May also be confused , for instance , I have said many times before ,go The string type of is actually a structure , that map What is the actual type .

–

Here's the right map Make a one-to-one decomposition , And the corresponding data structure , And the corresponding data types after compilation are decomposed one by one in the form of code .

map Actual type

map The format of is pointer , This is the first element , Then let's take the first step , Get it directly first ,map Content size of , This can be used unsafe.Sizeof To get to the .
We said earlier string It is actually a structure as follows

therefore , We get string What is the data length of 16, Then let's try map Of

func main() {
    var mp map[string]int
    if unsafe.Sizeof(mp) == unsafe.Sizeof(uintptr(0)) {
        pmp := unsafe.Pointer(&mp)
        fmt.Println("mp Point to the map Address ：", *(*int)(pmp))
        mp = make(map[string]int)
        fmt.Println("mp After initialization, point to map Address ：", *(*int)(pmp))
    } else {
        fmt.Println(unsafe.Sizeof(mp))
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

Let's decide first ,mp Whether it is saved is a map Address value of , If it is an address value , Then it should be and uintptr Of the same size , Then we get this mp The actual address value of , If it's not initialized , Then this address must be empty , That is to say 0, then make after , There must be an address value , Through this code , We can directly determine , stay go In language , We wrote map What is stored in variables is actually map The address pointer of .

–

Get... On it map There is a trick in the actual address value of , It is by taking the address of the address , Then the result is deduced , So I got map Actual address value , because go The compiler of defines , It can't be like C,C++ And so on , Direct conversion , therefore , Only after getting the address , Use the address to cast , This is the advantage of pointer class , After obtaining the memory structure , The pointer doesn't care about the data form , Whatever you want him to be , It's just a piece of data in memory .

deconstruction map deconstruction hmap

combination runtime Medium map.go, We can know , actually map The structure of is hmap, So , actually , We are go It's written in the code map, Namely *hmap The pointer value of . Let's deconstruct it , It says so ,go Due to the limitation of the compiler, it cannot be directly cast , therefore , We have to get the address first , Then transfer through the address , that go In code map It's actually *hmap, So the first step is to get the address &mp What you get is actually the address of the address, that is **hmap, therefore , Then you can get the actual structure by solving the pointer , First , We will go Of runtime/map.go Medium hmap Copy in the relevant structure , Then transform and try

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    *[]*bmap
oldoverflow *[]*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 << bucketCntBits
)

type tflag uint8
type nameOff int32 // offset to a name
type typeOff int32 // offset to an *rtype

type rtype struct {
    size       uintptr
    ptrdata    uintptr // number of bytes in the type that can contain pointers
    hash       uint32  // hash of type; avoids computation in hash tables
    tflag      tflag   // extra type information flags
    align      uint8   // alignment of variable with this type
    fieldAlign uint8   // alignment of struct field with this type
    kind       uint8   // enumeration for C
    // function for comparing objects of this type
    // (ptr to object A, ptr to object B) -> ==?
    equal     func(unsafe.Pointer, unsafe.Pointer) bool
    gcdata    *byte   // garbage collection data
    str       nameOff // string form
    ptrToThis typeOff // type for pointer to this type, may be zero
}

type mapType struct {
    rtype
    key    *rtype // map key type
    elem   *rtype // map element (value) type
    bucket *rtype // internal bucket structure
    // function for hashing keys (ptr to key, seed) -> 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 << (^uintptr(0) >> 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
    // Here is the dynamic structure , It is based on KV Type dynamically generated , Test here string type 
    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 *hmap
	hmp = *(**hmap)(unsafe.Pointer(&mp))
	fmt.Println("map The number of ：", hmp.count)
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.

The transformation place inside , It's just bmap In structure , We have completed the types we need , The others haven't changed much

map Data storage structure and map The type structure of

map The essence of is actually a hash table , And the corresponding key Different , Hash functions are definitely different , meanwhile , Stored in the hash table key,value The structure of is certainly dynamic , however runtime Of map.go It just gives a general element storage structure bmap, And you can see the code above key yes string,value It's also string, So in runtime/map.go Of bmp On the basis of the structure of keys [8]string and values [8]string as well as overflow uintptr Several structures , This shows that in fact, this piece of data content is dynamically filled in during compilation , Detailed content , Don't elaborate. , There are corresponding instructions on the Internet , Just mark a little , If it's another type , Then the corresponding data types here are other data types , At the same time, for each map structure , They all have one mapType structure , Record the type structure of this hash table

type mapType struct {
	rtype
	key    *rtype // map key type
	elem   *rtype // map element (value) type
	bucket *rtype // internal bucket structure
	// function for hashing keys (ptr to key, seed) -> 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
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

This structure records key type , Element type , And hash functions and key size ,value size , Hash bucket size, etc

A query

This piece of , Basically, it's right key Conduct hash Calculation , Use after calculation low bits And high 8 position hash Find the location of the corresponding hash bucket , Then look in the bucket , This piece of map.go There is , You can directly move out the relevant code , That's it , The main code element here is to find this key Computed hash function , And the hash function is mapType It's recorded in , therefore , The most important thing is to find map Corresponding mapType, Give me the simplest way , Just use interface Make a transit , And then through interface You can get the structure type , We can write a simple query about a key The value code of is as follows

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 The number of ：", hmp.count)
    // adopt interface obtain mapType structure , Then get his hash function 
    var mpInterface interface{}
    mpInterface = mp
    eface := *(*emptyInterface)(unsafe.Pointer(&mpInterface))
    mpType := (*mapType)(unsafe.Pointer(eface.typ))
    fmt.Println(" Barrel size ：", 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 {
        // I found the bucket , Search directly from the bucket 
        for i := range bucketPointer.keys {
            if bucketPointer.keys[i] == key {
                fmt.Println(" eureka key=", key, " The value of is :", bucketPointer.values[i])
                break
            }
        }
    } else {
        // The corresponding bucket is not found , From oldbuckets lookup 
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.

Break the question

Through the corresponding disassembly of the above series , Let's take a look at the first question is why

First , Deposit to map When , In fact, I will calculate a key Of hash value
By calculating the hash value , Then find the corresponding hash bucket
Store the key value data into the hash bucket

And if we put a string that has been stored in the hash table key The data value of the address of has been changed , And then key I don't know that his value has changed , So the position of this key will not change at this time , It is still in the original hash bucket . Then if the original string is used at this time key visit , here hash The calculated result is consistent with the original result , So we can find the corresponding hash bucket , But after finding the hash bucket , Compare the elements in the hash bucket key When , Can't match , So I can't find it at this time . Then if you use the changed string key To visit map, At this time, if the calculated hash value is then found, the hash bucket is the same as the original hash bucket , Then we can find this new value , If the calculated hash bucket is different from the original hash bucket , Then you can't find this value . So I got the proof

Add a hash collision , Attach the code located in the same hash bucket

In order to further clarify the above explanation , Here we add a modification implementation method that can be located in the same hash bucket , therefore , Adjust the code , Plus a hash collision adjustment , In this code, different strings are collided into the same hash , Then search and locate .

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 The number of ：", hmp.count)
	// adopt interface obtain mapType structure , Then get his hash function 
	var mpInterface interface{}
	mpInterface = mp
	eface := *(*emptyInterface)(unsafe.Pointer(&mpInterface))
	mpType := (*mapType)(unsafe.Pointer(eface.typ))
	fmt.Println(" Barrel size ：", 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 {
		// I found the bucket , Search directly from the bucket 
		for i := range bucketPointer.keys {
			if bucketPointer.keys[i] == key {
				fmt.Println(" eureka key=", key, " The value of is :", bucketPointer.values[i])
				break
			}
		}
	} else {
		// The corresponding bucket is not found , From oldbuckets lookup 

	}
	// Let's find one that can be found 
	buffer := []byte("test")
	stringData := reflect.StringHeader{
		Data: uintptr(unsafe.Pointer(&buffer[0])),
		Len:  len(buffer),
	}
	str := *(*string)(unsafe.Pointer(&stringData))

	mp[str] = str
	fmt.Println(" original key=" + str + ",value=" + mp[str])

	chars := []byte("abcdefghijklmnobjqrstuvwxyz")
	keyHash = mpType.hasher(unsafe.Pointer(&str), uintptr(hmp.hash0))
	bucketIndex := keyHash & m
	top := 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(" Collide with a matching to the same hash bucket 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 {
		// I found the bucket , Search directly from the bucket 
		for i := range bucketPointer.keys {
			if bucketPointer.keys[i] == str {
				fmt.Println(" Through their own implementation of the matching pattern , eureka key=", str, " The value of is :", bucketPointer.values[i])
				break
			}
		}
	} else {
		// The corresponding bucket is not found , From oldbuckets lookup 

	}
	fmt.Println(" Hit the matching key=" + str + ",value=" + mp[str])
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.