PTRHash

PTRHash 是一个快速且空间效率高的 最小化完美哈希函数，可以将一组 n 个不同的键映射到 [n]。它是 PTHash 的改编版本，用 Rust 编写。

我在 https://curiouscoding.nl/posts/ptrhash 上维护了一个包含备注、想法、实现笔记和实验的博客文章。

联系

请随意提交问题/PR，在推特 @curious_coding 或 matrix @curious_coding:matrix.org 上联系。

性能

PTRHash 支持高达 $2^40$ 个键。对于默认参数 $\alpha = 0.98$，$c=9$，构建 $n=10^9$ 个整数键的 MPHF 需要

• 构建耗时 19s 在我的 i7-10750H (3.6GHz) 使用 6 个线程
  • 5s 对哈希进行排序，
  • 12s 找到飞行员。
• 内存使用量为 2.69bits/key
  • 2.46bits/key 用于飞行员，
  • 0.24bits/key 用于重新映射。
• 查询需要
  • 18ns/key 当顺序索引时，
  • 8.2ns/key 当使用预取进行流式传输时，
  • 2.9ns/key 当使用预取进行流式传输，使用 4 个线程时。
• 当放弃哈希的最小化并允许值高达 $n/\alpha$ 时，查询时间略有提高
  • 在顺序索引时，14ns/键。
  • 当使用预取流式传输时，7.5ns/键。
  • 当使用4个线程进行预取流式传输时，2.8ns/键。

每个线程的查询吞吐量完全饱和了每个核心的预取带宽，多线程查询完全饱和了DDR4内存带宽。

算法

参数

• 给定$n < 2^40 \approx 10^{11}$个键。
• 将它们分成$P$部分，每部分包含大约200000个键。
• 每部分由$B$个桶和$S$个槽组成，其中$S$是2的幂。
• 总桶数$B \cdot P$大约是$n/\log n \cdot c$，其中$c \sim 8$是参数。
• 总槽数$S \cdot P$大约是$n / \alpha$，其中$\alpha \sim 0.98$是参数。

查询

给定一个键$x$，按以下顺序计算

1. $h = h(x)$，键的哈希值在$[0, 2^{64})$范围内均匀分布。
2. $part = \left\lfloor \frac {P \cdot h}{2^{64}} \right\rfloor$，键的部分。
3. $h' = (P \cdot h) \mod 2^{64}$。
4. 我们将桶分为大桶和小桶。 (这可以加快构建速度。)具体来说，我们将$\beta = 0.6$的元素映射到$\gamma = 0.3$的桶中

$$bucket = B \cdot part + \begin{cases} \left\lfloor \frac{\gamma B}{\beta \cdot 2^{64}} h'\right\rfloor & \text{if } h' < \beta \cdot 2^{64} \\ \left\lfloor\gamma B + \frac{(1-\gamma)B}{(1-\beta) \cdot 2^{64}} h'\right\rfloor & \text{if } h' \geq \beta \cdot 2^{64} \end{cases}$$

5. 查找桶$bucket$的引导符$p$。
6. 对于某个64位混合常数$C$，槽位是

$$ slot = part \cdot S + ((h \oplus (C \cdot p)) \cdot C) \mod S $$

与PTHash相比

PTRHash在几个方面对其进行了扩展

• 8位引导符：我们不允许引导符取任何整数值，而是将它们限制在[0, 256)范围内，并以Vec<u8>的形式存储，而不是需要压缩或字典编码。

• 位移：为了使所有引导符都尽可能小，我们使用位移，类似于布谷鸟哈希：当我们找不到无冲突的引导符时，我们会找到具有最少冲突的引导符，并将所有冲突的桶位移，这些桶将被推到队列中，然后它们将搜索新的引导符。

• 分区：为了加快构建速度，我们将所有键/哈希分区，使每个分区包含$S=2^k$个槽，我们选择其大小约为L1缓存的大小。这显著加快了构建速度，因为现在对taken位向量 reads的读取现在都是非常局部的。

  这带来了好处，即所需的唯一全局内存仅用于存储每个分区的哈希。排序、分区和槽填充是每个分区进行的，所需内存相对较少。

• 重映射编码：我们使用分区Elias-Fano编码，将44个整数编码成单个缓存行。这比全局Elias-Fano编码多占用了30%的空间，但将所需的读取数量从全局Elias-Fano编码的三个读取减少到单个读取。

use ptr_hash::{PtrHash, PtrHashParams};
let n = 1_000_000_000;
let keys = ptr_hash::util::generate_keys(n);

let mphf = <PtrHash>::new(&keys, PtrHashParams::default());
let sum = mphf.index_stream::<32, true>(&keys).sum::<usize>();
assert_eq!(sum, (n * (n - 1)) / 2);

// Get the minimal index of a key.
let key = 0;
let idx = mphf.index_minimal(&key);
assert!(idx < n);
// Get the non-minimal index of a key. Slightly faster.
let _idx = mphf.index(&key);

// An iterator over the indices of the keys.
// 32: number of iterations ahead to prefetch.
// true: remap to a minimal key in [0, n).
let indices = mphf.index_stream::<32, true>(&keys);
assert_eq!(indices.sum::<usize>(), (n * (n - 1)) / 2);

// Test that all items map to different indices
let mut taken = vec![false; n];

for key in keys {
    let idx = mphf.index_minimal(&key);
    assert!(!taken[idx]);
    taken[idx] = true;
}