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:

1. Bucket array expansion

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.

2. Built-in bias lock

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!