Map design

bucket （buckets）

Go Store key value pairs in a bucket list , Each bucket will hold 8 Key value pairs , When map When capacity is exhausted , The hash bucket will double its capacity . The following figure shows four barrels roughly ：

map Of buckets list

In the next article, we will introduce how the key value pairs in the bucket are stored . If map Capacity increase , The number of barrels will double to 8 individual 、16 Wait a minute .

When one key/value To deposit map among , Based on the key The hash value of is allocated to the bucket of .

hash

When key/value Assign to map when ,Go Will be based on key It's worth generating a hash value . We insert "foo=1" For example, key value pairs , Generated hash The value could be 15491954468309821754, Use this value for a bit operation , The mask is equal to the number of buckets minus 1. The number of barrels is shown in the figure below 4 Example , You can get the mask 3, Then perform bitwise and operation ：

value Distribution in barrels

Hash values are not only used to allocate bucket values , There are other operations . According to the height of the hash value 8 position , You can confirm that an array stored in a bucket value The location of . Here's the picture ：

In the bucket top hash table

Because there is this table in the bucket ,Go Can quickly access and compare key For the value value .

According to the procedure map Use ,Go A scalable mechanism is needed to store more key/value value .

Map Capacity expansion

If the bucket needs to store one key/value, Will be stored internally available 8 In the groove of a barrel . If no barrels are available , An overflow bucket will be created and linked to the current bucket , And link to the current bucket .

Overflow bucket

This overflow characteristic summarizes the internal structure of the barrel . However, increasing the overflow bucket will reduce map Performance of . To solve the performance problem ,Go New buckets will be allocated （ Twice the current number ） A connection will be established between the old barrel and the new barrel .

Go Use its load factor to know when to start distributing new barrels and the evacuation process .