Home >Backend Development >Golang >What are the expansion methods of go language?
Go language expansion methods include: 1. Slice expansion. When using append to add elements to Slice, if the Slice space is insufficient, Slice expansion will be triggered; 2. Map expansion. There are two conditions that trigger Map expansion: 1. When the load factor is greater than 6.5, that is, the average number of key-value pairs stored in each bucket reaches 6.5; 2. When the number of overflows is greater than 2^15, that is, when the number of overflows exceeds 32768.
The operating environment of this tutorial: Windows 7 system, GO version 1.18, Dell G3 computer.
When using append to append elements to Slice, if the Slice space is insufficient, Slice will be triggered Expansion
Expansion is actually to reallocate a larger memory, copy the original Slice data into the new Slice, then return to the new Slice, and then append the data to it after expansion .
The selection of expansion capacity follows the following rules:
// 1.17及以前的版本中 // old指切片的旧容量, cap指期望的新容量 func growslice(old, cap int) int { newcap := old doublecap := newcap + newcap // 如果期望容量大于旧容量的2倍,则直接使用期望容量作为最终容量 if cap > doublecap { newcap = cap } else { // 如果旧容量小于1024,则直接翻倍 if old < 1024 { newcap = doublecap } else { // 每次增长大约1.25倍 for 0 < newcap && newcap < cap { newcap += newcap / 4 } if newcap <= 0 { newcap = cap } } } // 这里忽略了对齐操作 return newcap }
The selection of new expansion capacity follows the following rules: (has a smoother expansion coefficient)
// 只关心扩容规则的简化版growslice func growslice(old, cap int) int { newcap := old doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { const threshold = 256 // 不同点1 if old < threshold { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += (newcap + 3*threshold) / 4 // 不同点2 } if newcap <= 0 { newcap = cap } } } return newcap }
There are two conditions for triggering expansion:
Load factor> 6.5, that is, the average number of key-value pairs stored in each bucket reaches 6.5. IncrementExpansion
Equal amountExpansion/rearrangement
will trigger a relocation every time the map is accessed, and each time 2 key-value pairs will be relocated. After all key-value pairs in oldbuckets have been relocated, delete oldbuckets.
The following figure shows a map containing a fully loaded bucket (for the convenience of description, the value area of the bucket is omitted in the figure): Current map There are 7 key-value pairs stored and only 1 bucket. At this time the load factor is 7 > 6.5. When data is inserted again, thecapacity expansion operation will be triggered. After capacity expansion, the new insertion key will be written into the new bucket. Note that because the load factor is triggered, the overflow bucket is not created.
When the 8th key-value pair is inserted,capacity expansion will be triggered. The schematic diagram after expansion is as follows:
Subsequent access operations to the map will trigger migration, and the key-value pairs in the oldbuckets will be gradually relocated. The diagram after the migration is completed is as follows: # During the data migration process, the key-value pairs in the original bucket will exist in front of the new bucket, and the newly inserted keys The value pair will exist at the end of the new bucket.Expansion is not actually an expansion of capacity, the number of buckets No change, redo the relocation action similar to IncrementExpansion, and rearrange the loose key-value pairs to make the bucket usage higher and ensure faster access. In extreme scenarios, such as constant additions and deletions, and key-value pairs are concentrated in a small number of buckets, this will cause the number of overflow buckets to increase, but the load factor is not high, making it impossible to perform incremental migration. , as shown in the figure below:
expansion is performed, that is, the number of buckets remains unchanged, and the number of overflow buckets will be reduced after reorganization, which saves space and improves access efficiency.
【Related recommendations:Go video tutorial, Programming teaching】
The above is the detailed content of What are the expansion methods of go language?. For more information, please follow other related articles on the PHP Chinese website!