你是否曾经好奇，为什么某些哈希表能在高负载下依然保持飞快速度，而另一些却随着数据增多而急剧变慢？有一天，我偶然接触到了 SwissTable——这种设计让我眼前一亮，随即为自己曾经写过的每一个简单的线性探测哈希表感到后悔。

这篇文章记录了我如何尝试将那种“为什么它能这么快？”的感觉带入 Java 世界。它既是一次技术深潜，也是一份工程日记，同时还是一个关于性能优化工作的警示故事。我将带你了解 SwissTable 的核心思想，展示它如何在 Rust 和 Go 等语言中成为标准，并详细分享我在 Java 中实现类似结构的实践过程、挑战与收获。

一、初识 SwissTable：一种令人耳目一新的设计

SwissTable 源自 Google 的工作，最初作为一种新的 C++ 哈希表方法被提出，后来被集成到 Abseil 库中。从根本上说，它仍然在做哈希表的常规工作：计算 hash(key)，选择一个起始槽位，然后探测直到找到你的键或一个空槽。

但巧妙之处在于，SwissTable 将 元数据（微小的“控制字节”）与实际键值对的存储分离开来，并利用这些控制字节在大多数情况下避免昂贵的键比较。与其立即访问一堆可能不在缓存中、且通常是指针密集型结构的键，它首先扫描一个紧凑的控制字节数组。这个数组密度高、对缓存友好，并且可以批量进行快速比较。如果你觉得这有点像一个小型的布隆过滤器，那么你的方向是对的：控制字节充当了一个廉价的“可能”关卡，在我们为真正的键比较付出代价之前进行筛选。

为了使探测变得廉价，SwissTable 有效地将哈希值分成两部分：h1 和 h2。你可以把 h1 看作是选择从哪里开始探测（先查看哪个组）的部分，而 h2 是存储在控制字节中的一个微小指纹，用于快速排除或纳入槽位。它不是一个完整的哈希值——只是足够多的比特位，以便在触及真实键之前过滤候选者。

因此，在查找时，你计算哈希，推导出 (h1, h2)，跳到 h1 对应的组，并在查看任何键之前，先将 h2 与该组中的所有控制字节进行比较。这意味着大多数未命中（以及许多命中）在元数据给出“这里有一个可能的候选者”信号之前，完全避免了触及键内存。

由于探测保持廉价，SwissTable 可以容忍更高的负载因子——在像 Abseil 的 flat_hash_map 这样的实现中高达约 87.5%（7/8）——而不会导致性能急剧下降，这直接提高了内存效率。最终效果是产生了一种同时更快（更少的缓存未命中、更少的键比较）和更紧凑（更高的负载因子、更少的像溢出桶这样的辅助结构）的设计。

二、从概念到标准：SwissTable 的多语言之旅

当你发现一个设计从酷炫的库技巧变成标准库的一部分时，你就知道它属于划时代的设计。

从 Rust 1.36.0 开始，std::collections::HashMap 切换到了基于 SwissTable 的 hashbrown 实现。它被描述为使用二次探测和 SIMD 查找，这基本上在精神和技术上都属于 SwissTable 的领域。这是我的“好吧，这不再是小众技术了”的时刻。

随后 Go 也加入了派对：Go 1.24 版本发布了一个基于 SwissTable 设计的新内置 map 实现，直接来自 Go 团队的博客文章。在他们的微基准测试中，map 操作的报告速度比 Go 1.23 快了 60%，在完整的应用程序基准测试中，他们看到了大约 1.5% 的几何平均 CPU 时间改进。如果你想要一个非常实用的“这在真实系统中很重要”的故事，Datadog 撰写了关于 Go 1.24 基于 SwissTable 的 map 以及新布局和增长策略如何在大规模下转化为显著内存改进的文章。

至此，SwissTable 不再感觉像是一个“聪明的 C++ 技巧”，而开始感觉像是现代基线。我无法摆脱这个想法：Rust 做了，Go 发布了……那为什么 Java 不行呢？凭借现代 CPU、强大的 JIT 以及终于可用的 Vector API，这感觉不再像技术上的不可能，而更像是一个我必须去挠的痒处。

就这样，我掉进了兔子洞。

三、当 SwissTable 的秘诀遇上 Java Vector API

SwissTable 速度的一个重要来源在于宽比较：一次性检查许多控制字节，而不是逐字节循环并不断分支。这正是 SIMD 擅长的任务：加载一个小块，与广播值比较，获取匹配的位掩码，然后才分支进入“慢路径”的键比较。换句话说，SwissTable 不仅仅是“做得好的开放寻址”——它是“为适应现代 CPU 而塑造的开放寻址”。

历史上，在 Java 中可移植地做到这一点很尴尬：你要么信任自动向量化，使用 Unsafe，编写 JNI，或者接受标量循环。但 Vector API 一直处于孵化阶段，专门为了让 Java 能够表达可靠地编译为支持 CPU 上良好 SIMD 指令的向量计算。

在 Java 25 中，Vector API 仍在孵化中，位于 jdk.incubator.vector 包中。对我来说重要的不是“它是否是最终版？”——而是“它是否足够好用，能够清晰地表达 SwissTable 的控制字节扫描？”因为如果我能在纯 Java 中写出“比较 16 个字节，生成掩码，对设置的位进行操作”，那么 SwissTable 的其余部分就变成了主要需要仔细设计数据布局和调整大小逻辑的工作。一旦你将控制字节扫描视为最热路径，你就会开始设计其他所有东西，以使该扫描变得廉价且可预测。

所以，是的：Vector API 是我尝试一些通常会被认为是“对 Java 来说太底层了”的事情所需的通行证。

四、动手实现：Java 的便利与挑战

我从 SwissTable 的核心分离开始：一个紧凑的控制数组加上独立的键/值存储。控制字节是主角——如果它们能保持在缓存中温热且扫描保持分支轻量，即使在微优化之前，表也会感觉很快。

我使用了熟悉的 h1/h2 分割思想：h1 选择初始组，而 h2 是存储在控制字节中的小指纹，用于过滤候选者。查找变成了一个两阶段管道：(1) 向量扫描控制字节以寻找 h2 匹配，(2) 对于每个匹配，比较实际键以确认。插入重用了相同的扫描，但一旦我们知道键不存在，就多了一个“查找第一个空槽”的路径。

Java 开始“推回”的地方在于布局的现实性。

在 C++ 中，你可以紧密地打包键/值；而在 Java 中，对象引用意味着“键数组”仍然是一个指针数组，触及键仍然可能导致一连串的缓存未命中。因此，设计目标变成了：尽可能晚地触及键，并且当你必须触及时，尽可能少地触及——这又是 SwissTable 的世界观。

删除需要墓碑（一个“已删除但非空”的标记），这样探测链不会断裂，但墓碑也会累积，如果从不清理，可能会悄悄降低性能。

调整大小本身就是一个小项目：进行完整的重新哈希计算是昂贵的，但巧妙的增长策略（如 Go 使用的表分割/可扩展哈希）显示了如果你愿意让设计复杂化，可以做到什么程度。

我还必须将 Vector API 视为优化工具，而不是魔法棒。向量代码对加载字节的方式、处理尾部的方式以及 JIT 能否保持循环结构稳定很敏感。我最终将控制字节扫描写成了一个非常明确的“加载 → 比较 → 掩码 → 迭代匹配项”循环。

在这个阶段，原型已经可以工作，但它还不是“SwissTable 级快”——它是“有希望的，现在真正的工作开始了”。

五、SwissMap 实现中真正重要的部分

以下是经过通常的“这感觉聪明但不够快”重构后幸存下来的部分。

1. 控制字节与布局

对于非原始键，真正的成本很少是“几次额外的字节读取”——而是指针追逐。即使一次 equals() 调用也可能遍历冷的对象并付出缓存未命中的延迟。因此，SwissMap 将控制数组视为第一道防线：扫描一个紧凑的、对缓存友好的字节数组，将搜索范围缩小到少数几个可能的槽位，然后才触及任何键/值。

这在 Java 中更重要，因为“键/值”通常意味着引用数组。在 64 位 JVM 上，压缩指针（通常根据对齐/JVM 标志启用至约 32GB）将引用打包为 32 位，使得引用数组更密集。当压缩指针关闭时，引用会扩展为 64 位，相同数量的键触及可能跨越更多的缓存行。

无论哪种方式，控制数组都完成了大部分工作：大多数未命中在元数据阶段就被排除了。压缩指针只是让不可避免的键触及在发生时更便宜。

2. 负载因子

在经典的开放寻址中，提高负载因子通常意味着平均探测链长度迅速增加——更多的分支、更多的随机内存触及，以及未命中成本的急剧上升。这就是为什么许多通用哈希映射选择保守的默认值。例如，Java 的 HashMap 默认负载因子为 0.75，以防止表填满时未命中成本膨胀。

SwissTable 颠覆了成本模型：探测主要由首先扫描控制字节主导，这些控制字节密集、对缓存友好，并且批量比较廉价。这意味着“多探测一个组”通常只是多一次控制向量加载 + 比较，而不是一堆键 equals() 调用。使用 SwissTable 风格的探测，表可以在不坠入悬崖的情况下运行得更密集。Abseil 的 SwissTable 系列映射以目标约为 7/8（0.875）的最大负载因子而闻名；即使表很拥挤，大多数探测仍然是“仅仅是元数据处理”。

这正是我也想在 Java 中实现的权衡：更高的负载因子 → 更少的槽位 → 更小的键/值数组 → 每次操作触及的缓存行更少，只要控制扫描保持为快速路径。

3. 哨兵填充

SIMD 需要固定宽度的加载：每次 16 或 32 个控制字节。烦人的部分是尾部——控制数组末尾附近的最后一个组。在本机代码中，你可能会“过度读取”几个字节，并依赖相邻内存是无害的。在 Java 中你没有这种奢侈：越界访问会直接导致错误。

如果没有填充，探测循环就需要处理尾部：额外的边界检查、掩码加载或数组结束分支——这正是在最热路径上你不想要的那种簿记工作。在数组末尾添加一个小的哨兵填充区域，可以让每次探测都发出相同的向量加载，保持循环的可预测性和 JIT 友好性。

4. H1/H2 分割

将哈希分割为 h1（选择起始组）和 h2（存储在控制字节中的小指纹）。h1 驱动探测序列（通常通过二的幂次方掩码），而 h2 是一个廉价的第一阶段过滤器：通过 SIMD 将 h2 与整个组的控制字节进行比较，只对匹配的通道触及键。

SwissMap 使用 7 位作为 h2，将控制字节的剩余值留给特殊状态，如 EMPTY 和 DELETED。这就是巧妙之处：一个字节同时回答两个问题：

  • “这个槽位是满/空/已删除吗？”
  • “这个槽位值得进行键比较吗？”

大多数查找在控制层面就拒绝了不匹配项。如果一个被探测的组包含一个 EMPTY，那就是一个确定的停止信号：探测链永远不会越过那个点继续，因此该键不可能存在“更后面”。

5. 重用已加载的控制向量

ByteVector 加载并非免费——它是对控制字节的一次真正的 SIMD 宽度内存加载。在我的测试机上，仅此一次加载每个探测组就约需 ~6 纳秒。在一个 get() 操作可能只需几十纳秒的哈希表中，这是一笔可观的成本。

因此，SwissMap 努力在每个组只加载一次控制向量并重用它：

  • 使用相同的加载向量生成 h2 相等掩码（候选通道）
  • 再次用于 EMPTY/DELETED 掩码（停止/继续决策）

没有额外的遍历，没有“就再加载一次”，没有重复工作。

6. 墓碑与删除管理

删除是开放寻址中正确性带来的痛点：如果你将一个移除的槽位标记为 EMPTY，你可能会破坏探测链。后来插入到该链中的键将变得“不可见”，因为查找会在第一个空槽处停止。

墓碑通过将槽位标记为 DELETED（“已删除但非空”）来解决这个问题，因此查找会继续探测过去。

在 put 操作中，墓碑不仅仅是正确性技巧——它们也是可重用的空间。常见模式是：

  • 在探测过程中，记住你看到的第一个 DELETED 槽位
  • 继续探测，直到你找到键（更新）或遇到 EMPTY（确定的未命中）
  • 如果未找到键，则插入到记住的墓碑中，而不是后面的空槽

这有助于防止探测链随时间变长，减少调整大小的压力，并防止大量删除/放入循环的工作负载慢慢毒化性能。

7. 触发同容量重哈希

墓碑保持了正确性，但它们稀释了最强的早期退出信号：EMPTY。一个有很多 DELETED 的表的未命中和插入操作往往会探测得更远——更多的控制扫描、更多的向量加载，以及更多触及冷键的机会。

因此，SwissMap 跟踪墓碑，并在它们超过阈值（作为容量的一个分数或相对于活动条目）时触发同容量重哈希。这会重建控制数组，将 DELETED 变回 EMPTY，并恢复短的探测链——基本上是在不改变逻辑内容的情况下进行压缩。

8. 无需冗余检查的调整大小重哈希

调整大小会强制进行重哈希，因为 h1 依赖于容量。显而易见的方法是“迭代旧条目并调用 put 到新表中”，但这会支付你不需要的工作：重复检查、额外分支和不必要的键相等性调用。

更快的路径将调整大小视为纯粹的移动：

  • 分配新的控制/键/值数组
  • 重置计数器
  • 扫描旧表一次，对于每个 FULL 槽位：

    • 为新容量重新计算 (h1, h2)
    • 使用相同的控制字节探测循环找到的第一个可用槽位插入
    • 不检查“这个键是否已经存在？”（不可能：你正在移动唯一的键）

这使得调整大小成为一个可预测的内存线性遍历，而不是一系列分支繁多的完整 put() 操作。

9. 无需额外缓冲区的迭代器

迭代是另一个“简单”变得异常昂贵的地方。你可以线性扫描并产出 FULL 槽位，但许多设计希望有一个稳定的访问模式，而不需要分配单独的密集列表。一些重新插入/重哈希交互甚至可能意外地变成二次复杂度（参见 Rust 迭代文章）。

SwissMap 通过使用模块化步进排列进行迭代来避免额外的缓冲区：选择一个 start 和一个奇数 step（对于二的幂次方容量，任何奇数步长都是互质的），然后通过重复 idx = (idx + step) & mask 访问索引。这恰好访问每个槽位一次，将访问分散在整个表中，并将迭代保持为与其他地方使用的相同控制字节状态机的紧密循环。

以下是一个删减版的查找方法，展示了探测循环如何围绕控制字节组织：

protected int findIndex(Object key) {
    if (size == 0) return -1;
    int h = hash(key);
    int h1 = h1(h);
    byte h2 = h2(h);
    int nGroups = numGroups();
    int visitedGroups = 0;
    int mask = nGroups - 1;
    int g = h1 & mask; // 优化的取模操作（与 h1 % nGroups 相同）
    for (;;) {
        int base = g * DEFAULT_GROUP_SIZE;
        ByteVector v = loadCtrlVector(base);
        long eqMask = v.eq(h2).toLong();
        while (eqMask != 0) {
            int bit = Long.numberOfTrailingZeros(eqMask);
            int idx = base + bit;
            if (Objects.equals(keys[idx], key)) { // 找到了
                return idx;
            }
            eqMask &= eqMask - 1; // 清除最低有效位
        }
        long emptyMask = v.eq(EMPTY).toLong(); // 重用已加载的向量
        if (emptyMask != 0) { // 在被探测组中任何空槽位都是 SwissTable 风格探测中的确定未命中
            return -1;
        }
        if (++visitedGroups >= nGroups) { // 防止当表充满墓碑时无限探测
            return -1;
        }
        g = (g + 1) & mask;
    }
}

六、性能基准测试

我不想只挑选在合成案例中看起来好看的数据。
因此，我使用了一个简单、可重复的 JMH 设置，对高负载探测和指针密集型键进行了压力测试——这正是 SwissTable 风格设计旨在处理的情况。

所有基准测试均在 Windows 11 (x64) 上运行，使用 Eclipse Temurin JDK 21.0.9，硬件为 AMD Ryzen 5 5600 (6C/12T)。

作为对比，我将其与 HashMap、fastutil 的 Object2ObjectOpenHashMap 和 Eclipse Collections 的 UnifiedMap 进行了比较。

主要结果

在高负载因子下，SwissMap 相对于其他开放寻址表保持了有竞争力的吞吐量，并且接近 JDK HashMap 的性能。在一些基准测试中，它甚至以较大优势领先。

put hit 操作性能 put miss 操作性能
CPU: put hit CPU: put miss
get hit 操作性能 get miss 操作性能
CPU: get hit CPU: get miss

在内存方面，平坦的布局（无桶/溢出节点）加上 0.875（7/8）的最大负载因子，转化为在小负载场景下明显更小的保留堆——根据本项目的测量，比 HashMap 少了 50% 以上。

Memory Footprint

注意事项

这些数字是发布前的；Vector API 仍在孵化中，并且该表是针对高负载、引用键工作负载进行调整的。对于原始类型特化映射或低负载因子配置，预期结果会有所不同。

七、快速提示：关于 SWAR 变体

你可能会在基准测试部分注意到一个 SWAR 风格的 SwissTable 变体突然出现。该版本是后续一轮调整的一部分：相同的 SwissTable 控制字节工作流，但使用 SWAR 实现以减少开销并避免依赖处于孵化阶段的 Vector API。

如果你对 SWAR 不熟悉，可以把它看作“寄存器内的 SIMD”：我们不使用向量通道，而是将多个控制字节打包到一个 64 位字中，并使用纯标量指令进行相同类型的逐字节比较。最终结果是类似的快速路径思想，只是以一种更便携（且对 JDK 版本更友好）的方式表达。

我不想把这篇文章变成三篇，所以我将完整的“如何/为什么”（包括 SWAR）留待下一篇分享——敬请期待。

八、常见问题解答 (FAQ)

1. SwissTable 和传统 Java HashMap 主要区别是什么？
传统 HashMap 使用链地址法（数组+链表/红黑树），而 SwissTable（及其 Java 实现 SwissMap）使用开放寻址法，并将元数据（控制字节）与数据存储分离。核心区别在于查找路径：SwissMap 首先在密集的控制字节数组中进行快速的 SIMD 扫描，只有匹配的候选者才需要访问实际的键对象，这大幅减少了缓存未命中和昂贵的 equals() 调用。

2. 为什么负载因子可以设到 0.875 那么高？
因为性能瓶颈转移了。在传统开放寻址中，高负载因子导致长探测链，意味着大量键比较和分支。SwissTable 的探测成本主要由 SIMD 扫描控制字节承担，这非常快。因此，即使表很满，大多数探测操作也只是在操作一小块热缓存中的元数据，性能下降曲线更平缓。

3. Vector API 是必须的吗？
对于实现 SIMD 加速的控制字节扫描，使用 Vector API 是目前 Java 中最清晰、最面向未来的方式。但如文中提及，也可以使用 SWAR（寄存器内 SIMD）技术实现类似加速，无需依赖孵化中的 API，牺牲一些灵活性但获得更好的兼容性。

4. 墓碑（Tombstone）会不会导致性能下降？
会，如果积累过多。墓碑虽然保持了正确性，但会延长探测链（因为查找遇到 DELETED 不会停止）。因此 SwissMap 需要监控墓碑数量，并在超过阈值时触发“同容量重哈希”来清理它们，这本质上是内部压缩操作。

5. 这个实现适合生产环境吗？
文中介绍的实现是实验性的（项目 HashSmith）。它用于探索设计思想和进行基准测试。虽然借鉴了成熟设计，但将其投入生产需要对边缘情况、并发支持、序列化等进行更全面的考量。不过，其核心思路（分离元数据、SIMD 扫描、高负载因子）对于优化高性能 Java 应用中的哈希表使用具有直接的启发意义。

6. 键对象有什么特殊要求吗？
与任何哈希表一样，键必须正确实现 hashCode() 和 equals() 方法。由于 SwissMap 重度依赖哈希值来生成 h1 和 h2，一个分布均匀的 hashCode() 对性能至关重要。

九、关键收获与总结

通过这次将 SwissTable 思想引入 Java 的实践，我们可以清晰地看到现代高性能哈希表设计的几个关键趋势：

  1. 计算换访问，元数据先行：通过增加少量的计算（如分割哈希、SIMD 比较）来大幅减少对主数据的随机内存访问，尤其是对缓存不友好的指针追逐。这是提升性能的核心。
  2. 为缓存和向量化设计：数据布局（控制字节与数据分离、密集排列）直接为 CPU 缓存层次结构和 SIMD 指令优化，将最热路径转化为线性、可预测的内存访问模式。
  3. 重新审视权衡：通过改变成本模型（让探测变廉价），可以突破传统的限制（如负载因子），从而在内存效率和运行时性能上获得双重收益。
  4. 语言特性的利用与挑战：Java 的 Vector API 为表达此类算法打开了大门，但语言本身的特性（如对象头、引用数组）也带来了独特的挑战，需要因地制宜的优化策略（如利用压缩指针）。

这项实践也提醒我们，性能优化工作往往是一个深入细节、反复衡量和测试的过程。一个在概念上优雅的设计，在具体实现中需要应对各种平台和语言环境的现实约束。

十、资源与下一步

如果你对代码、基准测试细节或自己动手实验感兴趣，可以参考这个公开实验项目：HashSmith。它包含了 SwissMap 以及 SwissSet 变体，附带 JMH 基准测试和文档。

如果你想深入了解 SwissTable 的原始设计，我强烈推荐观看 Google 工程师 Matt Kulukundis 等人的 CppCon 演讲：CppCon talk on SwissTable。讲解清晰、实用，充满了让设计豁然开朗的细节。

希望这篇深入探讨的文章能为你理解哈希表性能优化和现代 Java 性能编程提供有价值的视角。无论是为了在特定场景下构建更高效的数据结构，还是为了更深入地理解你所使用的工具内部原理，这类探索都大有裨益。