A Deep Dive into Slice and Map Expansion in Go

In the study of Go language, the expansion strategy of arrays and Maps is a common and classic topic. This article aims to summarize and explain the expansion strategies of arrays and Maps.

Array Expansion

In Go, dynamic arrays are called slices. A slice provides a flexible and dynamically sized array solution. When using the append function to add elements to a slice, Go decides whether to expand the capacity based on the current capacity of the slice.

The strategy for slice expansion in Go is as follows:

1. First, if the newly requested capacity is greater than twice the old capacity, the final capacity will be the newly requested capacity;
2. Otherwise, if the length of the old slice is less than 1024, the final capacity will be twice the old capacity;
3. Otherwise, if the length of the old slice is greater than or equal to 1024, the final capacity will increase iteratively by one-quarter of the old capacity until it reaches or exceeds the newly requested capacity;
4. If the calculation of the final capacity overflows, then the final capacity will be the newly requested capacity.

Hash Table Expansion

In Go, Map is a commonly used data structure for storing key-value pairs. Its expansion mechanism is crucial for understanding Map’s performance and memory usage.

There are two types of expansion in Go Maps:

• Doubling Expansion: When the number of key-value pairs exceeds 6.5 times the current bucket array capacity, it means the buckets are about to be full. At this point, expansion will be triggered, and the number of buckets will double. The purpose is to reduce hash collisions and improve query efficiency;
• Same-Size Expansion: When there are too many overflow buckets (e.g., frequent insertions and deletions cause data to be scattered) but the total number of key-value pairs is small, the number of buckets remains unchanged. Instead, data will be rearranged, redundant overflow buckets will be merged, and the distribution of data becomes more compact, thereby improving query performance.

Underlying Structure of Map

The underlying implementation of Map in Go is a hashmap. The Go source code is as follows:

// runtime/map.go
// A header for a Go map.
type hmap struct {
 count     int // number of key-value pairs currently in the hash table
 flags     uint8
 B         uint8  // number of buckets currently held by the hash table. Since the number of buckets always expands by a factor of 2, this field stores the exponent, i.e. len(buckets) == 2^B
 noverflow uint16 // approximate number of overflow buckets
 hash0     uint32 // hash seed

 buckets    unsafe.Pointer // array storing 2^B buckets
 oldbuckets unsafe.Pointer // used to save the previous buckets during expansion, size is half of buckets
 nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

 extra *mapextra // optional fields
}

// mapextra mainly maintains overflow buckets when some buckets in hmap have overflowed
// but have not yet reached the threshold for expansion
type mapextra struct {
 overflow    *[]*bmap
 oldoverflow *[]*bmap

 // nextOverflow holds a pointer to a free overflow bucket.
 nextOverflow *bmap
}

Some key field explanations are as follows:

• count: indicates the number of key-value pairs in the hash table;
• B: this is the exponent with base 2, used to determine the number of buckets. For example, when B = 1, the number of buckets is 2^1 = 2; when B = 2, the number of buckets is 2^2 = 4, and so on;
• hash0: a factor used in calculating the hash value of a key;
• buckets: a pointer to the bucket array, each bucket is used to store key-value pairs;
• overflow: when a bucket cannot hold more elements and a key hashes into this bucket, the element will be placed in an overflow bucket, and the original bucket’s overflow field points to the overflow bucket (chaining method).

Expansion Mechanism: Doubling Expansion

Trigger Condition:

When the load of a Map exceeds a certain threshold, doubling expansion will be triggered. The load is calculated as the number of elements (count) divided by the number of buckets (2^B). If this ratio is greater than or equal to 6.5, the load is considered exceeded.

For example, when B = 2, there are 2^2 = 4 buckets. If the element count count is 26 (26 / 4 = 6.5), doubling expansion will be triggered.

Relevant logic in the source code is as follows:

// assume h is a pointer to the map structure
if !h.flags&hashWriting && h.count > int(float64(1<<h.B)*loadFactor) {
    // trigger doubling expansion logic
}

Expansion Process:

During doubling expansion, the value of B increases by 1, thus doubling the number of buckets. For example, if originally B = 2 with 4 buckets, after expansion B = 3 with 2^3 = 8 buckets.

When migrating data, elements in the original buckets are redistributed into the new buckets. Specifically, the new bucket position is recalculated based on the hash value of the key.

Suppose the hash value of a key is hash. The original number of buckets was 2^B1, and after expansion, it becomes 2^B2. Then the data will migrate from the original bucket (hash % 2^B1) to the new bucket (hash % 2^B2).

For example:

• If the hash value is 10 and B = 2 (4 buckets), then 10 % 4 = 2, so the data is stored in the bucket at index 2;
• After expansion with B = 3 (8 buckets), 10 % 8 = 2, the data is still in the bucket at index 2. However, now the bucket distribution is sparser, reducing the probability of hash collisions.

Expansion Mechanism: Same-Size Expansion

Trigger Condition:

When a large number of keys are deleted, causing too many overflow buckets, same-size expansion may be triggered. Here, overflow buckets refer to the situation where a bucket is full with 8 elements, and new elements are stored in overflow buckets. Overflow buckets do not count towards the total number of buckets.

When the number of overflow buckets is greater than or equal to 2^B, same-size expansion may be triggered. However, if overflow buckets are excessive due to hash collisions and the load is exceeded, doubling expansion will be triggered first.

Relevant logic in the source code is as follows:

// assume h is a pointer to the map structure, noverflow is the number of overflow buckets
if noverflow >= uint16(1)<<(h.B) {
    if h.B < 15 {
        // may trigger same-size or doubling expansion logic
    }
}

Expansion Process:

Same-size expansion mainly organizes the buckets to remove empty spaces. A new bucket array is created, and the old bucket array is traversed to reinsert non-empty key-value pairs into the new array while freeing the original overflow buckets.

Since the hash factor, B value, and hash algorithm remain unchanged, the positions of key-value pairs in the new buckets are calculated in the same way as before. Only the empty storage spaces are removed, making the key-value pairs more compact and improving the efficiency of subsequent operations.

---

We are Leapcell, your top choice for hosting Go projects.

Leapcell is the Next-Gen Serverless Platform for Web Hosting, Async Tasks, and Redis:

Multi-Language Support

• Develop with Node.js, Python, Go, or Rust.

Deploy unlimited projects for free

• pay only for usage — no requests, no charges.

Unbeatable Cost Efficiency

• Pay-as-you-go with no idle charges.
• Example: $25 supports 6.94M requests at a 60ms average response time.

Streamlined Developer Experience

• Intuitive UI for effortless setup.
• Fully automated CI/CD pipelines and GitOps integration.
• Real-time metrics and logging for actionable insights.

Effortless Scalability and High Performance

• Auto-scaling to handle high concurrency with ease.
• Zero operational overhead — just focus on building.

Explore more in the Documentation!

Follow us on X: @LeapcellHQ