Home > Article > Backend Development > Implementation explanation of golang map
Golang is an emerging programming language, and its map is implemented based on hash tables. In this article, we will discuss how map is implemented in Golang. Specifically, we will introduce the concept of hash tables, the structure and performance optimization of Golang maps.
The concept of hash table
A hash table is a data structure that stores data in key-value pairs. It maps keys to an array index through a hash function, making access to data in the hash table more efficient.
The hash function calculates the value passed to it into a small fixed-length value that uniquely identifies the key (this is called a hash code). This hash code is used as the array index.
There are some problems with hash functions. One is hash collision, that is, different keys are mapped to the same array index, which needs to be solved by solving hash collision. Another type of problem is the inadequacy of the hash function, which may not accurately calculate the hash code of the value, resulting in uneven distribution of data in the hash table.
The structure of Golang map
In Golang, map is a structure, and its underlying data structure is a hash table. Specifically, map consists of the following three fields:
type hmap struct { count int flags uint32 B uint8 hash0 uint32 buckets unsafe.Pointer // 指向一个桶数组 oldbuckets unsafe.Pointer // 用于扩容时的桶数组 nevacuate uintptr // 当前将要被载入到oldbuckets的指针位置 extra *mapextra }
Among them, count represents the number of elements in the map; flags is used to record the status of the map, including whether to delete, iterate, etc.; B represents the bucket array The length is 2 raised to the Bth power; hash0 records the hash seed, which is used for the calculation of the hash function.
buckets is a pointer that points to an array of buckets. The format of the bucket array is as follows:
type bmap struct { tophash [bucketCnt]uint8 data [1]struct{ key, value interface{} } }
Among them, tophash is an array with a length of bucketCnt. Each element represents an element in bmap, and its value is an integer, used to locate the key-value pair in data. . data is an array of length 1 containing a key-value pair. The format of the key-value pair is as follows:
type iface struct { tab *itab data unsafe.Pointer } type itab struct { inter *interfacetype _type *_type link *itab bad int32 inhash int32 // 是否在哈希表中 funcbucket uintptr __hash uintptr // 哈希函数(方法) __eq uintptr // 判断是否相等的函数(方法) }
Among them, the data field is a pointer to the iface structure. The iface structure contains a pointer to the stored key-value pair and a pointer to the type information.
Performance optimization of Golang map
The performance optimization implemented by Golang map is mainly divided into the following two aspects:
When the number of elements in the map exceeds the capacity of the bucket array, the bucket array needs to be expanded. The way to expand is to add a new bucket array. The next time the map is accessed, all key-value pairs will be recalculated and then moved to the new bucket array one by one. This process is called rehash.
In the process of bucket array expansion, Golang uses a technology called randomized-hashing. This technology adjusts the hash seed so that key-value pairs can be more evenly distributed in the new bucket array during rehash, thereby reducing hash collisions.
Golang uses a locking mechanism called bias lock in map. Biased locking is an optimization technique. When the lock is only accessed by one go routine, it will use the thread ID of this goroutine to lock. This way, when this go routine needs to unlock or relock the lock, there is no need to switch threads because no other go routine will access the lock.
Summary
The underlying data structure of map in Golang is a hash table. Its bucket array uses randomized-hashing technology to rehash key-value pairs, and uses a biased locking mechanism for locking and Unlocked. These implementation details allow map in Golang to perform very well in some common data structure operations.
The above is the detailed content of Implementation explanation of golang map. For more information, please follow other related articles on the PHP Chinese website!