Golang - Data Structures - Map Internals and Performance

Introduction

For senior engineers, a surface-level understanding of maps isn’t enough. Interviews will often probe your knowledge of the underlying implementation to assess your ability to reason about performance and concurrency.

How a Go Map Works: The Hash Table

A Go map is implemented as a hash table. When you add a key-value pair, the following happens:

1. Hashing: The key is passed through a hashing function, which produces a single number (a hash). This hash is deterministic: the same key will always produce the same hash.
2. Bucket Selection: The hash is used to determine which “bucket” the key-value pair should be placed in. A bucket is a small, fixed-size array (currently holds up to 8 key-value pairs).
3. Storage: The key and value are stored in the selected bucket.

This process allows for very fast lookups. To find a key, Go just needs to hash it, find the correct bucket, and then do a quick search within that small bucket.

      "my_key"
         |
         v
+-----------------+
| Hashing Function|
+-----------------+
         |
         v
      Hash: 8971243
         |
         v (modulo number of buckets)
+-------------------------------------------------+
| Buckets Array                                   |
| +---------+ +---------+ +---------+ +---------+ |
| | Bucket 0| | Bucket 1| | ...     | | Bucket N| |
| +---------+ +---------+ +---------+ +---------+ |
|               ^
|               | (Place K-V pair here)
+-------------------------------------------------+

Handling Collisions

What if two different keys hash to the same bucket? This is called a collision. Go handles this by:

1. Storing multiple key-value pairs in the same bucket (up to 8).
2. If a bucket becomes full, Go creates an overflow bucket and links it to the original bucket, forming a linked list of buckets.

Excessive collisions and long overflow chains can degrade a map’s performance from O(1) to O(n) in the worst case.

Map Growth and Performance

To keep operations fast, a map must grow when it gets too full.

• Load Factor: A map’s load factor is the average number of items per bucket. Go considers a map “too full” when its load factor reaches 6.5.
• Growing: When the load factor is exceeded, Go doubles the number of buckets. It then gradually re-distributes the old key-value pairs into the new, larger set of buckets. This process is called incremental rehashing. It’s done progressively so that no single map operation takes too long.

Key Performance Characteristics:

• Time Complexity: On average, add, lookup, and delete operations are constant time, O(1).
• Memory: Maps start small and grow, but they never shrink. If you delete all elements from a map, the memory for the buckets remains allocated. To reclaim this memory, you must create a new map and copy over the desired data.

Interview Question: “What happens to the memory if you delete all the keys from a large map?” Answer: “The memory is not reclaimed. The map will still hold onto the allocated bucket structures. To free the memory, you would need to let the old map be garbage collected and create a new one.”

Pre-allocation with make

Just like with slices, if you know the approximate number of elements you will store in a map, you should pre-allocate it.

m := make(map[string]int, hint)

Providing a size hint to make allocates enough initial buckets to hold that many items without needing to grow immediately. This can provide a significant performance boost by avoiding the overhead of rehashing during the initial population of the map.

// BAD: Will likely cause several rehashes as it grows.
m1 := make(map[int]int)
for i := 0; i < 10000; i++ {
    m1[i] = i
}

// GOOD: Allocates enough memory for 10,000 elements upfront.
m2 := make(map[int]int, 10000)
for i := 0; i < 10000; i++ {
    m2[i] = i
}

This is a simple but powerful optimization.

0222 - Data Structures - Concurrency with Maps