[Rust 每日一库] hashbrown

hashbrown 库是 Rust 转写的 Google SwissTable，算法细节可以看 CppCon talk。它也是 1.36 之后版本的 Rust 标准库 HashTable 实现。

Layout

大体架构上，它实现了一个 RawTable<T>。不同于 CppCon 中提到的一个 ctrl 一个 bucket 两个向量，它的实现只用了一个 ctrl 指针。

源码中有以下说明：

                       `self.table.ctrl.cast()` returns pointer that
                       points here (to the end of `T0`)
                         ∨
[Pad], T_n, ..., T1, T0, |CT0, CT1, ..., CT_n|, CTa_0, CTa_1, ..., CTa_m
                          \________  ________/
                                   \/
      `n = buckets - 1`, i.e. `RawTable::buckets() - 1`

where: T0...T_n  - our stored data;
       CT0...CT_n - control bytes or metadata for `data`.
       CTa_0...CTa_m - additional control bytes, where `m = Group::WIDTH - 1` (so that the search
                       with loading `Group` bytes from the heap works properly, even if the result
                       of `h1(hash) & self.bucket_mask` is equal to `self.bucket_mask`). See also
                       `RawTableInner::set_ctrl` function.

P.S. `h1(hash) & self.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.

本质上是 Grouped Vector，让人眼前一亮！这种做法感觉对缓存非常友好。

Allocator

随着 no_std Rust 的日益发展和 Rust Allocator api 还没有 stablize 的矛盾，allocator-api2 诞生了。它类似于 proc-macro2，在 stable Rust 下会实现自己的 Allocator api 镜像，在 unstable Rust 下会用 Rust 的 Allocator api。

不过大部分情况都不需要一个数据结构单独配置 Allocator 吧；global allocator 其实已经很够用了。