Introduction to Map
Map data structure is provided in Go language to store key-value pair data. The data type of map ismap[K]V, where K is the type of the key and V is the type of the value. The key type of map must support==Operator, used to compare whether two keys are equal. Go provides 4 built-in map operations:len、delete、comparison、assign。
Map definition
map_var := make(map[K]V) // Create an empty map with make function, where K and V are the key and value types respectivelymap_var[key] = value // Add a key-value pair to the mapvalue := map_var[key] // Get the value of the specified keydelete(map_var, key) // frommapDelete the specified key and its corresponding value
Map Iteration
Go provides two methods to iterate through all key-value pairs in the map, respectivelyrangeMethods andLen()method.
// Loop through all key-value pairs in the map using rangefor key, value := range map_var {
// TODO ...
}
// Calculate the number of elements in the mapif len(map_var) > 0 {
// TODO ...
}Map thread safety
In Go, map isNon-thread-safe, may cause the program to report an error during multi-threaded concurrent access. When the map is accessed by multiple coroutines at the same time, we need to use theto ensure the atomicity and concurrency security of operations.
import "sync"
type SafeMap struct {
mu
m map[string]int
}
func (sm *SafeMap) Get(key string) int {
()
defer ()
return [key]
}
func (sm *SafeMap) Set(key string, value int) {
()
defer ()
[key] = value
}
func (sm *SafeMap) Delete(key string) {
()
defer ()
delete(, key)
}map underlying principle
Go language map is a kind of designHash tabledata structure. It uses a hash function to map keys to different storage spaces, thus enabling efficient search and insert operations.
Hash function
The hash function maps a string to an integer, which is called a hash value. Different strings may have the same hash value, but the same string must have the same hash value. The hash function needs to meet two points:
The calculation result of the hash function must be a non-negative integer, because negative numbers cannot be represented in the array.
Try not to be equal to the hash values of two different strings, so as to avoid conflicts during searches.
In Go language, the hash function of a string uses the FNV-1 hash algorithm, and the algorithm code is as follows:
const (
offset64 = 14695981039346656037
prime64 = 1099511628211
)
func stringHash(s string) uint64 {
h := uint64(offset64)
for i := 0; i < len(s); i++ {
h ^= uint64(s[i])
h *= prime64
}
return h
}Hash conflict
In a hash table, multiple strings with the same hash value may be stored in the same location. This phenomenon is calledHash conflict. Hash conflict processing strategies include open addressing, rehash method and chain address method.
Open addressing method: Search for new nulls one by one by one by one until a null location is found to store the current key-value pair
Rehash method: For conflicting keys, use another different hash function to calculate the address
Link address method: For conflicting keys, store them in a linked list
Go language usageLink address methodHandle hash conflicts. For each storage unit, a map structure is also maintained[]keyValueType of linked list.
type hmap struct {
count int // Number of key-value pairs in the mapflags uint8 // Control some properties of the hash tableB uint8 // Used to calculate the initial size of the hash addressnoverflow uint16 // Number of overflow buckets on the linked list}Growing
In Go, dynamic arrays automatically allocate more space to maps. The Growing process involves recopying the original array into a larger array where elements of the original array need to recalculate their position in the new array, while elements of the new array need to fill their key-value pairs to the corresponding position. The process of Growing is relatively complicated and can be made from functionshashGrow()To control it.
// hashGrow() doubles the size of the map's array and handles hash conflicts.func hashGrow(h *hmap) {
// ...
buf := make([]keyValue, newCap)
//...
for i := uintptr(0); i < cap; i++ {
// ...
evacuate(h, &[i], &buf)
// ...
}
// ...
}
// evacuate() remap key-value pairs in a bucket into a new arrayfunc evacuate(h *hmap, oldbuck *bucket, newbuck *[]keyValue) {
// ...
}Map expansion
Double expansion
The hash table in Go language will automatically expand when the map's array capacity reaches a certain level. The basis for expansion is the ratio between the number of currently stored elements and the length of the array:
When the number of stored elements of a map is less than half of the length of the map array, the number of elements does not reach the maximum efficiency of the hash table and there is no need to expand the capacity;
When the number of elements stored in the map is greater than or equal to half of the length of the map array, the search efficiency of the hash table has reached the maximum value, so it needs to be expanded.
Go's map will prefer the array size to twice the original array size to ensure that the map has enough space to store new elements in the stored procedure. When the number of elements reaches 85%, Go will expand the array again. At this time, the length of the array is doubled to ensure that the ratio of the array length and the number of elements is always maintained at around 0.75 to balance efficiency and space occupation.
Growing process
When the number of elements in the map exceeds 85%, the Go language will trigger the map expansion process. During the expansion process, the map will copy the original elements into the new array and set the initial size of the new array to 2 times the original array. For elements that have hash conflicts, the hash address needs to be recalculated in the new array.
Avoid overflow
When the number of elements in the array exceeds0x7fffffffWhen (2^31-1, that is, the maximum value of type int), overflow will occur, and the size of the array will not reach twice the original array. So when the map is initially created, Go will initialize a smaller array for it and set the B value of the map so that it can expand again when the number of elements exceeds the limit. When the number of elements in the map exceeds the threshold, it will double again until the array size is smaller than0x7fffffffuntil.
Code Analysis
Included in Go language source codesrc/container/in the file. inmapThe definition of structure and the implementation of Growing are bothruntimeIn the package, insrc/runtime/in the file.
appendix
Why is the capacity of the hash table set to a power of n of 2? Why not other numbers?
How is maps in Go language thread-safe? What is the principle?
What is the data structure of map? How to find, add and delete key-value pairs?
How to implement the Growing process?
Why is the capacity expansion condition of map 85%, not 100%?
How to create map in go language?
Why do hash conflict processing strategies have open addressing, rehash method and chain address method?
If there is a conflict, how are key-value pairs stored in an array?
Why does a large temporary array be created during the Growing process instead of directly expanding the space on the original array?
How to implement map iteration?
Summarize
In this section, we learned about map data types, usage methods and map data security issues in Go language.
This is the end of this article about the introduction of Golang Map and the underlying principles. For more detailed explanations of Golang Map, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!