这个算法由google开源，最早在2017年的c 大会上分享过。
文章概览
效果
hash表的实现，实在是太经典太没什么新意了，但是这个数据结构又是用得太多太基础的组件了，如果有人能够把hashtable做的更快，实在也没理由拒绝。Google实现的这个hash表的性能，请看下图：
(图片引用了Zhihu 流左沙文章内图片)
各种情况下，swisstable比std::unordered_set至少快两倍！！！
低负载情况 | 高负载情况 | |
|---|---|---|
找到的情况 | 快2倍以上 | 快6倍 |
找不到的情况 | 快2.5倍 | 快6倍 |
对比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的大致结构可以表述如下：
代码语言：javascript复制 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
