Swisstable：C++中比std::unordered_map更快的hash表

这个算法由google开源，最早在2017年的c++大会上分享过。

文章概览

效果

hash表的实现，实在是太经典太没什么新意了，但是这个数据结构又是用得太多太基础的组件了，如果有人能够把hashtable做的更快，实在也没理由拒绝。Google实现的这个hash表的性能，请看下图：

(图片引用了Zhihu 流左沙文章内图片)

各种情况下，swisstable比std::unordered_set至少快两倍！！！

对比std::unordered_map

hash表通常号称O(1)的时间复杂度，但是在hash冲突存在的情况下，往往达不到O(1)的时间复杂度。

众所周知(我最喜欢问的面试题)，解决hash冲突有以下经典的三种方式：

• 开放地址法
• 相邻地址法
• 多散列函数法

重点在于，std::unordered_map使用开放地址法来解决hash冲突。

链表最大的问题就在于——在当代的CPU架构下，内存比SSD快100倍，而cpu cache又比内存快100倍，链表对于CPU cache并不友好。因此，cache友好的结构能够提升性能。

关键设计

Swiss table的关键设计就是——通过相邻地址法来解决hash冲突。一个平坦的内存结构，能够提高cpu cache命中率。

因此，具体的设计细节，都是针对相邻地址法解决hash冲突的具体办法。

大致结构

swiss hash的大致结构可以表述如下：

 struct Item{
     uint64_t hashcode;  //57bit
     void* key;
     void* value;
 };
 ​
 #define MAX_ITEMS 1024  /*hash的长度以2的幂对齐*/
 ​
 struct SwissTable{
     Item items[MAX_ITEMS];
     uint8_t meta_table[MAX_ITEMS];  //元数据表，用于解决hash冲突
 };
 ​

hashcode

通过在key上执行hash函数，得到一个64位的hash值。

把hash值分为高7位和低57位：

• 低57位用于定位桶中slot的位置
• 高7位用于在control byte中解决hash冲突

control byte

hash桶中每个slot对应一个1一个byte的控制字节。

Control byte的高1位用于表示状态，低7位用于存储hashcode的高7位。

状态位分为：

• 未使用：0xFF表示（全为1）
• 已删除：0x80表示（最高位为1，其余位为0）
• 在使用：0x00~0x7F之间的值（最高位为1）

group概念

以128bit对齐的连续8字节的control byte称为一个group。

解决hash冲突通常在slot对应的control byte所在的group内解决。

以128bit对齐的原因是，group内的搜索，可以用四条SIMD指令来解决。

展望

• 搜索了一下，目前还没有golang版本的swiss table，后续准备实现一个
• Flat hashtable不仅仅只是CPU CACHE友好，这样的结构配合原子操作，相信很容易做出一个并发版本的hash table。后续也准备在这里做一些尝试。
• 算法的优化进入深水区了：
  • 与当下的CPU架构结合起来，很多经典算法能够老树开新花
  • 假设当前使用的是苹果的M1芯片，那么经典算法可能在异构计算的体系里产生更多令人惊异的提升。

参考文章

• 浅谈哈希算法
• 视频：CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”
• google 的 swisstable hashmap 筆記
• Swisstable, a Quick and Dirty Description
• rust hashmap实现
• The Swiss Army Knife of Hashmaps
  • （翻译和解读）Zhihu 流左沙：新式哈希表 - Swiss Tables

google开源的abseil库

• Swiss Tables Design Notes
• c++语言实现，文档：Swiss Tables and absl::Hash
• 把c++版本包装成c版本：(github)Accessing Abseil Swiss Tables from C
• (github)Abseil - C++ Common Libraries

源码

• C语言实现的版本：Swissmap
• rust语言的实现：hashbrown
• 用代码生成的方法来提供swisstable: github, google, cwisstable.h