Go: Map Design by Example — Part I

Illustration created for “A Journey With Go”, made from the original Go Gopher, created by Renee French.

ℹ️ This article is the first of a series of three articles. Each article will cover a different part of the map. I suggest you read them in order.

The built-in type map provided by Go implements a hash table. In this article, we will explore the implementation of the different parts of this hash table: the buckets (structure that stores the key/value pairs), the hashing (index of those pairs), and the load factor (metric that defines the capacity of the map should grow).

Buckets

Go stores the key/value pairs in a list of buckets where each bucket will hold 8 pairs, and when the map is running out of capacity, the number of hash buckets doubles. Here is a diagram of the rough representation of a map with 4 buckets:

We will see in the next article how the key/value pairs in the bucket are stored. If the map grows again, the number of buckets will double to 8, then 16, and so on.

When a pair comes into the map, it will be dispatched to a bucket according to the hash calculated from the key.

Hashing

When a key/value pair is assigned to the map, Go will generate a hash based on this key.

Let’s take an example with the insertion of key/value pair "foo" = 1. The hash generated could be…