Introduction

With the release of Go 1.24, the language takes a significant leap forward in performance optimization—this time, targeting one of its most fundamental data structures: the map. Inspired by Google’s high-performance Swiss Table (popularized in C++’s Abseil library), the Go team has re-engineered the internals of its map implementation to deliver faster lookups, reduced memory overhead, and better cache utilization. This change marks a pivotal shift in how Go handles hash tables, addressing long-standing inefficiencies while embracing modern hash table design principles. Let’s dive into how this transformation works and why it matters.

Part 1: The Old Map (A Quick Refresher)

Before Go 1.24, maps worked like this:

  • Buckets: Your keys were stored in buckets (groups of 8 entries).
  • Overflow Chains: If a bucket filled up, new entries went into overflow buckets, linked like a chain.
  • Tophash: Each entry had a tiny tophash (8 bits of the key’s hash) to skip non-matching keys quickly.

It worked, but it had some rough edges:

  • Slow Lookups: Scanning overflow chains meant jumping around in memory (hello, cache misses!).
  • Memory Bloat: Overflow buckets ate up extra space.
  • Resizing Woes: Growing the map meant rehashing everything. Ouch.

👉 Want to dive deeper into the old design? Check out this great explainer.

Part 2: Swiss Table Deep Dive—How It Handles Collisions Like a Pro

Let’s break down the Swiss Table’s secret sauce step-by-step, using a concrete example. Spoiler: It’s all about smart metadata and cache-friendly groups.

Step 1: Hash Splitting (H1 vs. H2)

Imagine you insert the key price into a Go map. The hash function generates a 64-bit value, say:
H = 0x5F4A3B2C1D (simplified for clarity).

The Swiss Table splits this hash into two parts:

  • H2 (7 bits): The first 7 bits of the hash. Think of this as a "mini fingerprint" of the key.
  • H1 (57 bits): The remaining bits. This determines which group the key belongs to.

Example:

  • H2 = First 7 bits of 0x5F4A3B2C1D → 0x5F (binary: 01011111).
  • H1 = The rest → Used to calculate the group index.

Step 2: Metadata—The Magic Cheat Sheet

Every entry in the map has a 1-byte metadata field. This byte stores:

  • The 7-bit H2 value.
  • A 1-bit status flag:
    • 0: Empty.
    • 1: Occupied.
    • 0x80 (binary 10000000): Tombstone (deleted).

Example:
When you insert price, Go stores 0x5F in the metadata (since its H2 is 0x5F) and marks the status as 1 (occupied). The full metadata byte becomes 0x5F | 0x01 = 0x5F1 (simplified).

Step 3: Group Hunting with H1

The map is divided into groups of 16 entries. To find where "price" belongs:

Use H1 to calculate the group index:

group_index = H1 % number_of_groups

Check the metadata of all 16 entries in that group.

Example:
If H1 points to Group 3, Go scans the 16 metadata bytes in Group 3.

Step 4: Handling Collisions (No Linked Lists!)

If Group 3 is full, here’s what happens:

  • Linear Probing: Go checks the next group (Group 4, then Group 5, etc.) until it finds an empty slot.
  • Tombstones: If a slot is marked as deleted (tombstone), it’s treated as empty for insertion but preserved for lookups.

Why This Rocks:

  • No more chasing linked lists—everything stays in contiguous memory.
  • CPU caches love this (fewer cache misses!).

Example Walkthrough:

Insert price

  • Hash: price → H = 0x5F4A3B2C1D.
  • Split:
    • H2 = 0x5F → stored in metadata.
    • H1 → calculates group index (e.g., Group 3).
  • Check Group 3:
    • If Slot 5 in Group 3 is empty → insert "price" there.
    • If Slot 5 is occupied, check Slot 6, then Slot 7, etc.
  • Collision? If Group 3 is full, move to Group 4.

Lookup price

  • Compute H2 = 0x5F.
  • Go to the group calculated by H1.
  • Scan the group’s metadata for 0x5F.
    • Match found: Compare the actual key (to handle hash collisions).
    • No match: Skip to the next group.

This skips 99% of non-matching keys without even looking at the keys!

Why This Beats the Old Map

Old Map Swiss Table Map
Used linked lists for collisions Uses linear probing (no pointers!)
Scanned keys one-by-one Metadata filters out mismatches instantly
Overflow buckets wasted memory Tombstones reuse space efficiently

Final Takeaway

The Swiss Table’s genius lies in:

  • Metadata: A tiny cheat sheet to skip useless work.
  • Groups: Cache-friendly memory layout.
  • Linear Probing: Simpler, faster collision handling.

Go 1.24’s new map isn’t just faster—it’s smarter. And you get all this without changing a single line of your code! 🎉

👉 For benchmarks and nitty-gritty details, check out this post.

Still have questions? Drop them in the comments! 👇

Author Of article : Anh Tu Nguyen Read full article