Swiss Table的实现原理

/// Non-generic part of `RawTable` which allows functions to be instantiated only once regardless
/// of how many different key-value types are used.
struct RawTableInner<A> {
    // Mask to get an index from a hash value. The value is one less than the
    // number of buckets in the table.
    bucket_mask: usize,
    // [Padding], T1, T2, ..., Tlast, C1, C2, ...
    //                                ^ points here
    ctrl: NonNull<u8>,
    // Number of elements that can be inserted before we need to grow the table
    growth_left: usize,
    // Number of elements in the table, only really used by len()
    items: usize,
    alloc: A,
}

核心的数据结构就是上面的RawTableInner，其中bucket_mask，其值等于buckets数量减1，buckets的数量总是2的冥，所以这里用bucket减去1作为其mask。ctrl指向是Swiss Table的控制区域的地址。growth_left是剩余可以插入的元素。items则是Table中已经使用的元素。ctrl指向的控制区域和bucket的区域是连续的。用ctrl区域的地址减去bucket的大小即可得到bucket区域的开始地址。控制区域则是按照16个字节为一组，正好是128bit，主要是方便SIMD指令进行运算。每个字节对应到一个bucket，这个字节中的内容是0xff则表示空，否则表示bucket已经存值了。

插入过程:

插入元素的时候，首先通过SipHasher计算Key的hash值，然后和bucket_mask进行相与，得到要插入的位置，然后取出这个Hash值的前7位放到ctrl区域的第0个字节。

Untitled

SIMD查找过程:

对Key进去Hash，然后和bucket_mask进行相与，得到对应的bucket number，假设这里得到了139，对139进行取余，得到1，也就是说从控制区域+128处通过SIMD指令加载128位，然后和Hash的头7bit进行匹配。

Untitled

Bucket扩容:

当bucket满的时候，哈希表会按照2的幂进行扩容，会导致分配新的堆内存，老的堆内存会重新拷贝到新的内存区域，在拷贝的过程中会涉及到哈希的重分配。

Untitled

删除一个值:

删除一个值和查找的过程基本一致，查找到对应的ctrl区域后，直接将对应区域设置为0xff即可。可以看到实际上并未清除内存。等到这个bucket被再次使用的时候，才会真正清除内存。

Untitled

Untitled