，因此一些在线性探测法中遇到的问题在这里也跑不掉。所以插入、更新和删除都得基于上一节介绍的查找。
所以对于插入和更新，算法的大致步骤是这样的：
- 利用查找的过程尝试找到目标key，如果存在那就直接进行更新
- 不存在的时候会选择合适的有空位的group，当前group没有位置的时候就会顺延到下一个group，这步和线性探测一样
- 然后选择有空位的group里最左侧的一个空位（控制信息显示为删除或者空的slot），写入控制信息，然后把key和value插入对应的slot（这里的左侧只是个形象的说法，实际上根据实现的不同略有出入，但group是一次比较一整组的，所以相对顺序通常没有那么重要）
- 如果没找到合适的空位，先尝试把标记为delete的slot按算法将符合条件的标记为空，依然没有合适的空位则会尝试扩容，然后再插入
查找是否有合适的空位和将标记为删除的slot更新为empty这两个操作都是借助SIMD指令和位运算批量完成的。
删除的操作需要考虑一些边界条件，并为减少内存使用量做了一些优化：
- 根据给的key找到对应的control byte和slot
- 将slot里存的数据释放掉，slot本身保留
- 将control byte从哈希特征值改成表示数据被删除的标记值
- 这步是优化，会判断control byte前后的数据，符合条件的情况下可以不标记为被删除，直接标记为empty。
当然了，设置control byte的值用的是位运算，而检查是否符合直接标记为空的操作也借助了SIMD。
从这三个操作来看，SwissTable快的原因还在于：所有可以利用SIMD进行批量操作的地方都进行了对应的优化。
所以SwissTable为什么这么快？
看完SwissTable的实现，我觉得可以总结为下面几点：
- 对hashtable的操作从slot转移到了control bytes上，控制信息更小更容易被填入CPU的高速缓存，因此比直接在slot上操作更快，即使需要多付出一次从control bytes得到索引后再去引用slot的代价
- 记录哈希特征值，减少了无意义的key等值比较，这是线性探测法性能下降的主要元凶
- 对slot的查找和操作是通过control bytes批量进行的，单位时间内吞吐量有显著提升
- 标志位的值和整个数据结构的内存布局都为SIMD进行了优化，可以充分发挥性能优势
- 对slot也有优化，比如对太大的数据会压缩存储以提高缓存命中率，不过这只是锦上添花
还有一些abseil特有的优化，比如根据table的大小选择更合适的扩容策略来平衡性能和内存效率。这些不是swisstable算法的一部分，就不列进去了。
在解决了空间局部性问题的基础上，swisstable还利用了现代CPU的特性批量操作元素，所以性能会有飞跃般的提升。
如果CPU没有对应的SIMD指令怎么办
swisstable需要的主要是sse2的指令，这些指令最早在2000年由Intel发布，目前X86平台上常见的处理器都支持，20年前发布的处理器还在运行的已经非常稀有了。
在ARM平台上比较特殊，虽然有NEON这样的SIMD指令集存在，但缺少一部分SSE2的功能，虽然可以靠位运算修补，但整体要比X86上多花几条指令。以及NEON的普及程度较SSE2稍差，新的芯片上应该都支持，但稍微老一些的设备和部分嵌入式设备/单板计算机就够呛了。
最麻烦的是一些不支持算法要求的SIMD指令的平台。当然也不是没办法，实际上swisstable算法中描述的批量操作可以靠位运算实现，其中查找的操作还可以一次批量处理8条数据。但吞吐量直接腰斩，一次查找需要的指令数也大幅超过了能使用SIMD的平台，粗略看了下至少得多用三倍的指令，这会带来一些性能衰退。
不过缓存友好和批量操作带来的好处还是可以体验到一部分的，所以即使CPU不支持需要的SIMD指令，你依旧能从swisstable中获益。
SwissTable还有什么需要注意的地方
对于使用者来说只有一个需要注意的地方：如果你要自定义key的哈希函数，一定得提供一个质量最上乘的。因为现在哈希函数计算出来的值除了要让数据尽量均匀分布之外，还得尽量保证每一个bit的概率均等性，也就是尽量接近前面说的“完美哈希函数”，否则哈希特征值会出现很多重复值，这样即使有再多的批量操作，还是会被大量等值比较拖慢速度。不过这也有上限，最低也差不多在1/128，因为我们就用了七位哈希值。如果我们用了个质量堪忧的哈希函数，这个重复率就可能变成1/20，SIMD带来的性能优势可能就荡然无存了。
对于想实现swisstable的人来说，注意点会稍微多一些。
第一点是注意内存对齐，SSE2要求操作的内存地址是对齐过的，如果不是它会自己转换，这个转换非常耗时。所以abseil的实现上不仅分配的时候处理对齐，还用填充数据保证了这一点。
第二点的slot的个数，选择了不合适的slot数量会导致H1定位冲突的增加，因此像abseil选择了2**N-1作为slot的数量，扩容也是按照N∈{1, 2, 3, 4, ...}这样的方式扩容的。
第三点，用作存放控制信息的数据类型大小最好是8bit，多了浪费少了不能充分表示信息并加大了冲突概率，而且这8bit必须是全部可以使用的；如果用的是c/c++，那么char不能用，因为char是否带符号是平台和编译器定义的，没有可移植性，不用unsigned char是因为标准只规定了它的最小大小，没规定上限，所以不如intN_t这样的类型来的保险。可以学abseil用int8_t。
总结
整篇文章其实还忽略了一个影响hashtable算法性能的点：哈希函数的算法。因为我们开篇就假设了我们有“完美哈希函数”，所以没有对这点进行过多讨论。现实是哈希函数的性能也很重要，但讨论怎么优化它的性能超出了本文的讨论范围。比较常见的优化方向其实和swisstable在实现查找时用的办法差不多：依赖SIMD增加数据吞吐量或者利用硬件指令（AES、SHA系列）来加速计算。详细的就不做展开了。
如果要说swisstable有什么缺点，那应该只有高度依赖哈希函数的品质这一点了，依赖SIMD其实不是什么大问题，现代CPU都支持，新兴的平台比如RISC-V和LoongArch都有活跃的社区和维护者，随着时间推进提供对等的支持不是太远的事，但哈希函数的品质是很难控制的，何况哈希函数可以使用一些用户自己实现的。使用者想避免这类问题，最好的办法就是用现成的被证明品质良好的哈希算法，比如murmur3或者用库里提供的，而不是自己去写。
swisstable正在逐渐被业界接纳，例如rust就已经把它内置进标准库了；golang最后是否会接受swisstable还是未知数，不过swisstable本身最早就是谷歌设计和实现的，带来的提升也是实打实的，我想官方最终接纳的可能性还是比较大的。
参考资料
首次提出swisstable的cppcon演讲：https://www.youtube.com/watch?v=ncHmEUmJZf4
两年后针对swisstable算法的一些改进：https://www.youtube.com/watch?v=JZE3_0qvrMg
swisstable