Recently I sorted out my knowledge system and found that a lot of knowledge took a lot of time and energy to learn. It was easy to understand when I looked back and grasped the key points. Output is the best way to learn, so I want to write this series to sort out various knowledge points and share them with you.

The basic concepts of go are as follows:

  • Basic usage, convenient for everyone to quickly master;
  • The underlying implementation structure, so that we quickly get to the implementation principle;
  • Common problems, in order to better landing application;
  • Reference articles, because it is to grasp the main points, so the content will not be too detailed, but I will give a better reference article I have seen in this part, in order to continue in-depth research.

Use the Map

Map is a structure that exists in every language, some are called map, some are called dictionary, the standard translation is map, also known as associative array or dictionary or hash table, the core function is to store a key-value pair, where the key is not allowed to repeat.

Declaration and initialization

In the Go language, maps can be initialized with the make keyword.

m = make(map[string]string)
m["a"] = "b"
Copy the code

The make keyword can only be used to initialize slice, map, or channel with nil values, but the nil value is typed.

var m map[string]string
if m == nil {
    fmt.Printf("m is nil --> %#v \n ", m) //map[string]string(nil)
}
Copy the code

Maps can also be declared and initialized at the same time

var m = map[string]string{
	"a": "go",
	"b": "gogo",
}
Copy the code

Add and delete

Add, delete, change and check more intuitive, directly paste the code. It should be noted that each traversal of the map in Go is random, that is, the results obtained by traversing the same map twice may be different.

M1 := map[int]string{1: "go", 2: "zen"} m1[1] = "zen" m1[3] = "gogo" fmt.Println(m1) m2 := make(map[int]string, 3) m2[0] = "aaa" m2[1] = "BBB" FMT.Println(m2[0], m2[1]) FMT.Println(m2[0], m2[1]) m3 := map[int]string{1: "go", 2: "Zen "} for k, v := range m3 {FMT.Printf("%d:%s\n", k, v)} for k := range m3 {FMT.Printf("%d:%s\n", k, v) M3} [k]) / / get the value, ok: = m3 [1] FMT. Println (" value ", value, ", "ok, ok) / / delete the m4: = map (int) string {1:" go ", 2: "zen"} delete(m4, 1) for k, v := range m4 { fmt.Printf("%d:%s\n", k, v) }Copy the code

The underlying implementation

Different languages have different ways to implement map. In general, there are two underlying implementation structures, one is hash table and the other is search tree. If using hash table implementation, also need to solve the problem of hash collision, the solution method is open address method and chain address method. Map in Go language is implemented based on hash table and uses chain address method to solve hash collision problem. The structure is defined in the go/ SRC /runtime/map.go file of the source code as follows:

// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/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
}
Copy the code

The main attributes include buckets at the bottom, count to mark the current number, B to mark the capacity, flags to handle read/write conflicts, hash0 to hash functions, noverflow, oldbuckets, nevacuate, etc. Buckets points to a 2^B array that actually stores data, which might be nil if there are no elements, and whose underlying structure is bucket, which points to BMAP.

type bmap struct {
    tophash [bucketCnt]uint8
}
Copy the code

Tophash is a high 8-bit hash. In addition to the normal 8-bit hash value, topHash stores the status values of some features when idle or migrated. Therefore, the minimum value of a valid Tophash (the calculated one) should be 4, and any value less than 4 is the defined status value. Since different types of key-value pairs can be stored in hash tables, and the Go language does not support generics, the amount of memory occupied by key-value pairs can only be inferred at compile time, so a new structure is dynamically created at compile time:

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}
Copy the code

Here we finally see where keys and values are stored. You can see that each bucket holds up to eight elements, and there is also a pointer to the next one, which is where the chain-address method was used to resolve hash conflicts.

The overall structure is shown in the figure below. The source of the picture is map for In-depth Decryption of the Go language. For more information about map access and expansion, you can also check this article, which has a detailed introduction.

Other problems with maps in Go

Is map a value type or a reference type

The reference types, interface, Map, Channel, slice, and func, are all reference types, which means that if you pass a map as an argument to a function, the changes in the function take effect synchronously.

Is map thread safe

No, to be thread-safe you need to use sync.map or define your own map+mutex structure.

Which types can be used as keys in a map

All comparable types can be used as keys. In short, all types except func, map, and slice can be used as map keys. For details, please refer to the “==” comparison rule in Go language

Refer to the article

A Tour Of Go

Deep decryption of Go language map

Cao Chunhui’s article on map is strongly recommended

Go language design and implementation