1. Why write such an article?

  • Why write recently naked resignation at home, have time ha ha ha ha. Then also consolidate their knowledge of this piece
  • Why change your mind not to write basic operations (add, delete, change, check, expand), but to write from the perspective of the problem?
    • 1. Because I read a book recently, it is more difficult to remember things that people are not interested in. And the common basic operation source code analysis is actually a bit boring, so instead start with map common problems to analyze
    • 2, many people have written about the basic operation (recommend fried fish blog), I don’t think my level can write better than them (I am vegetable chicken =-=)
  • Note: The following source code is based on Go1.16 Darwin /arm64. Golang Map runtime/map.go,

2. Faqs about MAP

2.1 Why is map Unordered? What if I want an ordered map?

2.1.1 First of all, what is the underlying structure of map

2.1.2 Can logical inference be traversed in order?

  • Logically, if I just follow the diagram above, I just need to go through buckets’ list and overflow pointer to do so

2.1.3 Why is the actual traversal not in order?

  • First point: random numbers are inserted into the function of the native traversal map, resulting in disorder, as shown below
// Code location: runtime/map.go
func mapiterinit(t *maptype, h *hmap, it *hiter) {
	// Omit some code
    
    // 1, this will get a random number, implement below
	r := uintptr(fastrand())
	if h.B > 31-bucketCntBits {
		r += uintptr(fastrand()) << 31
	}
    // 2, which determines the starting point of a bucket traversal based on a random number
	it.startBucket = r & bucketMask(h.B)
	it.offset = uint8(r >> h.B & (bucketCnt - 1))

	// iterator state
	it.bucket = it.startBucket

	// Remember we have an iterator.
	// Can run concurrently with another mapiterinit().
	ifold := h.flags; old&(iterator|oldIterator) ! = iterator|oldIterator { atomic.Or8(&h.flags, iterator|oldIterator) } mapiternext(it) }// Code location: runtime/stubs.go
func fastrand(a) uint32 {
	mp := getg().m
	s1, s0 := mp.fastrand[0], mp.fastrand[1]
	s1 ^= s1 << 17
	s1 = s1 ^ s0 ^ s1>>7 ^ s0>>16
	mp.fastrand[0], mp.fastrand[1] = s0, s1
	return s0 + s1
}

Copy the code
  • Second point: why add random numbers when you can logically order them?
    • 1, because it only looks like order can be done from the first picture, but in the actual traversing map, the effect of expansion needs to be considered
    • 2. Assume that in the case of capacity expansion, the situation of twice traversal occurs
      • The first time through, the elements in the first bucket come first
      • The map was expanded, causing elements from the first bucket to be allocated to subsequent buckets
      • The second time I iterate, I’m going to get a different answer than the first time
    • 3, so if Golang does not include random numbers, then it is possible that developers unfamiliar with this principle will assume that the map is ordered without experiencing scaling. They rely on this feature and cause bugs. So Golang avoids this problem by simply adding random numbers

2.1.4 What if I want an ordered Map?

  • 1, implement an ordered map by yourself, this is a bit complicated =-=, need some things, not to talk about
  • 2. Sort the unordered map
    • The first method: sort for keys. You can take out keys and make a list, sort for the list, and then go back to the original map for values
    • The second method: sort by key or value, which can be implemented through the interface that implements sorting

2.2 Why Does Panic occur when I Read and write A Map Concurrently? How to solve it?

2.2.1 Why Does Panic Occur in Concurrent READ and write Operations?

  • Because there are restrictions in the code, the code is as follows
// File location: Runtime /map.go
// 1, data is read to check if it is being written
ifh.flags&hashWriting ! =0 {
    throw("concurrent map read and map write")}// 2, the assignment also checks if it is being written
ifh.flags&hashWriting ! =0 {
    throw("concurrent map writes")}Copy the code
  • Why does the code have restrictions that don’t allow simultaneous reads and writes?
    • If more than one Groutine operates on the same memory address, the data in that memory can be corrupted
    • Personal Understanding:
      • 1, let’s say A block of memory is 10, and then thread A changes it, changes it 1-5,
      • 2, then CPU time is up, thread B changes again 1-5, then THREAD A changes again 6-10
      • 3, thread C comes and reads this variable, what does it read

2.2.2 How to Solve the Concurrent Read and Write Problem?

  • 1. Use sync.Mutex to lock
  • 2. Replace map with sync.map
  • Sync. RWMutex can be used if there are too many reads and too few writes

2.2.3 Why does Golang not support map concurrency natively?

  • Reason: If the native support map concurrency, the need to lock, and if the map performance will be degraded, but there are many scenarios where the map will not be multithreaded read and write simultaneously
  • extension: Are there performance optimizations if you want to use locks to support concurrency?
    • See Java’s ConcurrentHashmap for a segmented lock implementation. You can divide the database into different tables to improve read and write performance
    • Golang’s own implementation of Sync.map is also implemented through data redundancy

3. Map is not common but also worth thinking about some points

3.1 What Value can be used as the Map Key? Why is that? Is float ok?

  • Keys can be of many typesBool, number, String, pointer, channel, and interface types, structs, and Arrays
    • The reason: As mentioned earlier, map keys may be of any type that is comparable. The language spec defines this precisely, but in short, comparable types are boolean, numeric, string, pointer, channel, and interface types, and structs or arrays that contain only those types. Notably absent from the list are slices, maps, and functions; these types cannot be compared using ==, and may not be used as map keys.
    • Above link: blog.golang.org/maps
  • Can float be used as a map key?
    • Yes, but with caution. Because float64 is converted to unit64 as the map key, errors may occur

3.3 Can the Map Key Fetch an Address?

  • No, the code is as follows
func TestMain1(t *testing.T) {
	testMap := make(map[int]bool)
	testMap[1] = true
	testMap[2] = true
	fmt.Println(&testMap[1]) // This will not compile
}
Copy the code
  • The memory address of the key may change due to capacity expansion

4. Problem: Map nested structure problem

4.1 Question 1: What is the problem with the following code?

type Student struct {
	name string
}

func main(a) {
	m := map[string]Student{"people": {"zhoujielun"}}
	m["people"].name = "wuyanzu"
}
Copy the code

4.2 Question 2: What is the problem with the following code?

type Param map[string]interface{}

type Show struct {
	Param
}

func main(a) {
	s := new(Show)
	s.Param = *new(Param)
	s.Param["RMB"] = 10000
}
Copy the code

4.3 Reference answer: base64 decode

UTE6ICAg5Zug5Li6dmFsdWXmmK/pnZ7mjIfpkojnsbvlnovvvIzmiYDku6Xkv67mlLnnmoTor53lj6rog73lhajlsYDkv67mlLnvvIzkuI3og73lsYDpg6jk v67mlLkKUTLvvJrmsqHmnInpnIDopoHlr7nnu5PmnoTpopjkuK3nmoRtYXDnlKhtYWtl5p2l5Yid5aeL5YyW77yM6ICM5LiN5pivbmV3Copy the code

Reference 5.

  • Developpaper.com/deep-decryp…
  • blog.golang.org/maps
  • Golang. Design/go – question…