Golang在1.24版本中引入了基于Swiss Tables的新map实现。
在新的实现中，一个map由多个group组成，而每个group包含8个slot以存储键值对，且还包含一个control word作为元数据。control word一共占8个字节，其中的每个字节都对应group中的1个slot。Golang在这个基础上，将一个map继续分为多个table，即一个map其实包含了多个Swiss Table。
map -> table -> group -> slot基本数据结构
接下来自底而上看看新map数据结构的实现：
group
一个slot其实就是一个键值对，这里没什么可以深挖的，所以我们从group开始。每个group都可以理解成一张固定大小的哈希表，slot在其中连续分布：
| Slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| Key | 56 | 32 | 21 |
而control word和slot也一一对应：
| Slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| h2 | 23 | 89 | 50 |
表中的h2是每个slot的键的低7位，注意每个slot在control word里都有1个字节，也就是8位bit与之对应。高位的1个bit用于标记slot状态：空（10000000）、已删除（11111110）、正在使用（0*******）。
table
在原始的Swiss Table设计（C++）里，一张table就实现了整个哈希表，这样设计有两点缺陷：
表格的增长受到限制，会一次性影响所有数据（要把数据从一个底层数组迁移到另一个更大的新数组里去）；
查找未命中时的搜寻序列会很大，所有的
group都得查一遍。
为此，Golang采用可扩展哈希的形式令每个map可包含一个或多个table，每个table最多可以容纳1024个键值对，即128个group。如此一来，每个table的增长，不会影响到其它table的数据，且在最坏的情况下，也只是在插入新数据时，把一个满溢的table增长为两个容量为1024的table，只需要拷贝已有的1024个键值对。
这里所谓可扩展哈希，即根据map中表格数量，采用不同位数的bit来做选择。例如，如果只有两张table，则使用1个bit，4张则使用2个。
哈希过程
我们以插入一个新的键值对为例，看看如何将数据定位到一个特定的slot里去。
首先，我们会通过一个哈希函数，得到一个64-bit的哈希码，其中：
前57 bit称为
h1；后7 bit称为
h2。
假设我们的map包含4个table，那么这里的前2个bit其实决定了存放这个新键值对的table。我们假设前两位是10，代表定位到第2个table。
紧接着，我们要确定新的数据落在哪个group里，这就要使用前57个bit，也即h1了。Golang内部会基于h1计算目标group的位置。如果group已满，则使用Quadratic probing 来查找下一个group。相比于线性查找，这种做法的好处时能尽可能的将数据分散到不同的group里。既能避免数据集中，又能减少后续查询时间。而如果采用线性查找，就只能一个个往下查找group了。
假设我们找到了一个候选的group，就需要根据h2来查看目标slot。因为我们是要插入数据，涉及更新已有数据和插入新数据两种情况，不需要查看高1位（见group里对slot状态的描述）。
我们需要扫描对比control word和h2以确定候选slot，这个过程中，可能会找到多个匹配的slot。当搜索到一个空slot时，搜索会立刻终止，毕竟后续的匹配slot也必然为空。为此，之前被删除的键值对，在control word中会标定为“已删除”（见前文），而不是“空”，以免做键值对搜索时误判。如果没有空slot，则在第一个被删除的slot里插入这个键值对。
相比于之前的实现，新实现的优点在于，字节级别的control word和h2的匹配比较，在硬件层面是可以支持并行的，即一个group的八个slot可以并行计算匹配结果。
增长过程
一个极小的map（数据不大于8个）是无所谓table的概念的，仅仅包含一个group，且slot不会被标记为“已删除”，搜索时只会简单遍历8个slot。
当map的尺寸增长时，就会出现table。如果一个table的实际数据量超过了负载阈值，它就会像slice一样将自身底层数组切换为原容量两倍的新数组（见之前的一篇blog）。如果它计算得到的新容量已经超过了1024，则table会被拆分为两个新的table。
在后者的情况下，map中存放table位置的底层数据结构也会扩大两倍，而不论table的实际个数。如，原本有两个table（map中的数组大小为2），现在其中有一个需要分成两个新table，即现在一共有三个table，此时map中的数组却会扩大为4，多余的容量用于指向未分裂的table。
旧map的一个缺点是不支持并发（见另一篇blog），毕竟修改时可能扩容，而搜索顺序也是随机的，导致某些键值对在扩容过程中可能不会被遍历到。在基于Swiss Table的实现中，执行搜索的迭代器会记录当前正在搜索的table的引用地址，如果该table扩容，这样能保证已有的数据是可以被检索到的，但仍不保证新数据的搜索。如果我们此时修改或删除某些数据，也同样会出现问题，毕竟我们实际上是对旧的table做操作，脏数据有可能已经完成了迁移。总结起来看，新的map最好也不要并发访问。