# Faster Go Maps With Swiss Tables  ## Metadata - Author: [[go.dev]] - Full Title: Faster Go Maps With Swiss Tables - Category: #articles - Published: 2025-02-26 - Document Tags: #go - Source: reader - Last Highlighted: 2025-03-06 10:21:13.786421+00:00 - URL: https://go.dev/blog/swisstable ## Summary Go 1.24 improves map performance with a brand new map implementation ## Highlights - The concept of a hash table was [first described](https://spectrum.ieee.org/hans-peter-luhn-and-the-birth-of-the-hashing-algorithm) by Hans Peter Luhn in 1953 in an internal IBM memo that suggested speeding up search by placing items into “buckets” and using a linked list for overflow when buckets already contain an item. Today we would call this a [hash table using chaining](https://en.wikipedia.org/wiki/Hash_table#Separate_chaining). ([View Highlight](https://read.readwise.io/read/01jnnfe4qbg0wwzf4xbe3c14s8)) - In 1954, Gene M. Amdahl, Elaine M. McGraw, and Arthur L. Samuel first used an “open addressing” scheme when programming the IBM 701. When a bucket already contains an item, the new item is placed in the next empty bucket. This idea was formalized and published in 1957 by W. Wesley Peterson in [“Addressing for Random-Access Storage”](https://ieeexplore.ieee.org/document/5392733). Today we would call this a [hash table using open addressing with linear probing](https://en.wikipedia.org/wiki/Hash_table#Open_addressing). ([View Highlight](https://read.readwise.io/read/01jnnff5vpt2236ba6zdtzc8ct)) - When a hash table reaches its maximum load factor, it needs to grow the backing array. Typically this means the next insertion doubles the size of the array, and copies all entries to the new array. Imagine inserting into a map with 1GB of entries. Most insertions are very fast, but the one insertion that needs to grow the map from 1GB to 2GB will need to copy 1GB of entries, which will take a long time. ([View Highlight](https://read.readwise.io/read/01jnnfgf17c2fzv4v844y9kew1)) - Go’s built-in map addresses this with another layer of indirection by splitting each map into multiple Swiss Tables. Rather than a single Swiss Table implementing the entire map, each map consists of one or more independent tables that cover a subset of the key space. An individual table stores a maximum of 1024 entries. A variable number of upper bits in the hash are used to select which table a key belongs to. This is a form of [*extendible hashing*](https://en.wikipedia.org/wiki/Extendible_hashing), where the number of bits used increases as needed to differentiate the total number of tables. ([View Highlight](https://read.readwise.io/read/01jnnfgqm1d9287m4vxwbpgx11)) - Many hash table designs, including Abseil’s Swiss Tables, forbid modifying the map during iteration. ([View Highlight](https://read.readwise.io/read/01jnnfh7qsfbvb8r1gd5yx1nvm)) - The Go language spec [explicitly allows](https://go.dev/ref/spec#For_statements:~:text=The%20iteration%20order,iterations%20is%200.) modifications during iteration, with the following semantics: • If an entry is deleted before it is reached, it will not be produced. • If an entry is updated before it is reached, the updated value will be produced. • If a new entry is added, it may or may not be produced. ([View Highlight](https://read.readwise.io/read/01jnnfhayz5rfaqef0m5z6wz11)) - This edge case is addressed by using the old table only to determine the iteration order. Before actually returning the entry, we consult the grown table to determine whether the entry still exists, and to retrieve the latest value. ([View Highlight](https://read.readwise.io/read/01jnnfjf0x5tjs6cr6n124r78n)) - There are more map improvements we want to investigate for future Go releases. For example, we may be able to [increase the locality of](https://go.dev/issue/70835) operations on maps that are not in the CPU cache. ([View Highlight](https://read.readwise.io/read/01jnnfhvewqw3mc50yj6gy3jfd))