https://laisky.notion.site/SwissMap-A-smaller-faster-Golang-Hash-Table-DoltHub-Blog-2fd1a48ab8a24e13ab9614409252ab9c?pvs=4
学习了一下 SwissTable，号称更快更轻的下一代 hash table。
一开始被 DoltHub 的这张 benchmark 图唬住了，内存接近于 array，吞吐居然还比 built-in map 快，太神奇了。仔细研究了一下源码后发现果然是幻觉，benchmark 的代码作弊了，因为频繁 rehash，把内存占用压缩到了极致，而 bench 中忽略了最耗时的
hashmap 的结构大同小异，底层都是一个固定长度的 array，key 通过哈希函数定位到 array 的地址，然后取得值。Go built-in map 使用的是开地址法（open-hashing），即不同的 key 可能会被映射到同一个 array 地址，然后这些不同的 item 通过一组以链表串联的 bucket 来存储，每个 bucket 存放 8 个 item。
而 swisstable 使用闭散列法（closed-hashing），即每个 key 都会有一个唯一的地址，不会有冲突。拿 Find 来解释 swissTable 的原理：
1. 计算 key 的 hash 值，前 56-bits 称为 H1、后 8-bits 称为 H2
2. 通过 H1 计算得到 array 的 index，array 的每一个 item 为 128-bits 长，由 16 个 8-bits H2 组成
3. 使用 SIMD 指令，并行比较 16 个 8-bits 地址，可以得知 key 是否存在于当前桶
a. 如果 key 存在，完成查找
b. 如果 key 不存在，且这 16 个地址都非空，说明 key 可能溢出到了下一个桶，index+1，继续循环（probing）
c. 如果 key 不存在，且这 16 个地址中存在空，说明 key 不存在
总的来说，swissTable 最大的亮点就是利用了 SIMD 的并行计算能力，实际上它和 open-hashing 类似也有 buckets，只是每个 bucket 的容量是固定的 16 个（取决于 SIMD 指令的宽度），而且不像拉链法那样可以串联，这样可以用 SIMD 一次性比对完 bucket 内的全部 keys，提高了性能，而且还能充分利用缓存的局部性。
至于说它省内存，我倾向于认为只是因为它的 load factor 略高一些所带来的些微优势，而没有本质区别，要注意不要被一些第三方的虚假宣传骗了。 #algorithm
学习了一下 SwissTable，号称更快更轻的下一代 hash table。
一开始被 DoltHub 的这张 benchmark 图唬住了，内存接近于 array，吞吐居然还比 built-in map 快，太神奇了。仔细研究了一下源码后发现果然是幻觉，benchmark 的代码作弊了，因为频繁 rehash，把内存占用压缩到了极致，而 bench 中忽略了最耗时的
Put 操作，然后只呈现了 Get 的性能😓。hashmap 的结构大同小异，底层都是一个固定长度的 array，key 通过哈希函数定位到 array 的地址，然后取得值。Go built-in map 使用的是开地址法（open-hashing），即不同的 key 可能会被映射到同一个 array 地址，然后这些不同的 item 通过一组以链表串联的 bucket 来存储，每个 bucket 存放 8 个 item。
而 swisstable 使用闭散列法（closed-hashing），即每个 key 都会有一个唯一的地址，不会有冲突。拿 Find 来解释 swissTable 的原理：
1. 计算 key 的 hash 值，前 56-bits 称为 H1、后 8-bits 称为 H2
2. 通过 H1 计算得到 array 的 index，array 的每一个 item 为 128-bits 长，由 16 个 8-bits H2 组成
3. 使用 SIMD 指令，并行比较 16 个 8-bits 地址，可以得知 key 是否存在于当前桶
a. 如果 key 存在，完成查找
b. 如果 key 不存在，且这 16 个地址都非空，说明 key 可能溢出到了下一个桶，index+1，继续循环（probing）
c. 如果 key 不存在，且这 16 个地址中存在空，说明 key 不存在
总的来说，swissTable 最大的亮点就是利用了 SIMD 的并行计算能力，实际上它和 open-hashing 类似也有 buckets，只是每个 bucket 的容量是固定的 16 个（取决于 SIMD 指令的宽度），而且不像拉链法那样可以串联，这样可以用 SIMD 一次性比对完 bucket 内的全部 keys，提高了性能，而且还能充分利用缓存的局部性。
至于说它省内存，我倾向于认为只是因为它的 load factor 略高一些所带来的些微优势，而没有本质区别，要注意不要被一些第三方的虚假宣传骗了。 #algorithm