HashMap 陷阱

背景

Rust 的 HashMap 是谷歌的 SwissTable 的一個實現，雖然這確保了哈希表本身的優秀性能，但默認情況下使用的哈希函數旨在以犧牲性能爲代價防止 DoS 一類的攻擊。對於更關心性能的需求，可以切換到更有效的哈希函數可以顯著提高性能。Rust 哈希映射使得通過切換到不同的哈希函數來更改哈希算法變得相當容易，Rust 性能手冊推薦使用 rustc-hash crate 中的 FxHasher 和更高質量的 ahash crate。然而，這種建議的代價很少被提及——一些 O(n) 散列映射操作，包括反序列化，會降級爲 O(n**2)！

問題

因爲在反序列化 hashmap 時很容易發現這個問題，所以我們以它爲例。爲了簡單起見，我們將構造一個 HashSet，HashMap 與其具有相同的行爲。這段代碼創建了一個 1 千萬隨機數的集合，使用 bincode 將其序列化爲 Vec，並將其反序列化回 HashSet：

 1use std::time::Instant;
 2use rand::Rng;
 3
 4type TestHashSet<K> = std::collections::HashSet<K>;
 5//type TestHashSet<K> = rustc_hash::FxHashSet<K>;
 6
 7fn main() {
 8    let mut rnd = rand::thread_rng();
 9    let nums: Vec<_> = (0..10_000_000).map(|_| rnd.gen::<u64>()).collect();
10
11    let t0 = Instant::now();
12    let h: TestHashSet<u64> = nums.into_iter().collect();
13    let t1 = Instant::now();
14    println!("create: {}", (t1 - t0).as_secs_f64());
15
16    let out = bincode::serialize(&h).unwrap();
17    let t2 = Instant::now();
18    println!("serialize: {}", (t2 - t1).as_secs_f64());
19
20    let h2: TestHashSet<u64> = bincode::deserialize(&out).unwrap();
21    let t3 = Instant::now();
22    println!("deserialize: {}", (t3 - t2).as_secs_f64());
23
24    println!("{}", h2.len());
25}

在我的機器上輸出：

create: 1.440201369
serialize: 0.071765342
deserialize: 1.114031976

現在切換到 fxhash 來加快速度。我們只需要將 TestHashSet 別名指向 rustc_hash::FxHashSet，就設置好了。注意，FxHashSet 本身是 std::collections::HashSet 的別名，它的散列器是 fxhashher，所以它隻影響散列函數，而不影響表的實現。通過這個更改，我得到這個輸出：

create: 1.391839734
serialize: 0.081116361
deserialize: 5.2052695

創建稍微快一些，序列化花的時間差不多，但是反序列化幾乎比標準庫散列慢 5 倍! 在不同的集合尺寸下進行測試，反序列化時間接近二次曲線——1 千萬個元素的反序列化時間爲 5s，2 千萬個元素的反序列化時間爲 20s，4 千萬個元素的反序列化時間爲 69s，8 千萬個元素的反序列化時間爲 219s，我們已經看到陷阱了。

爲什麼會發生？

簡而言之，將一個較大的表複製到一個較小的表中，將較大表的前半部分的鍵分配到連續的位置。然後，大表的下半部分的鍵必須與已經密集排列的鍵相匹配，這就形成了巨大的碰撞鏈。雖然這是一個臨時的情況，在下一次調整大小時固定，但它明顯影響性能。

儘管實現切換到不同的哈希探測策略，但是底層仍然使用帶有線性探測和 2 的冪次方哈希表大小的開放尋址算法。

通過引入隨機化，對默認散列器的二次探測行爲進行了修正，但這個問題仍然存在，因爲底層的 bug 仍然存在，可以在非隨機散列器中看到，如上面的代碼所示。

變通方法

這個 bug 的所有修復都歸結爲對項目進行洗牌，以避免以不利的順序建造。由於導致該問題的實際 bug 是在 hashmap 的實現中，所以我將這些 bug 稱爲變通方法，而不是適當的修復。

預分配 HashSet/HashMap

這是目前爲止最簡單的解決方法，你不能控制 map 的確切類型，但可以控制它的創建。在非 serde 情況下，這意味着初始化 h2 哈希映射並給出容量：

1// fast because h2 is of the correct size to begin with
2// note: can't just call with_capacity() because it assumes RandomState from stdlib
3let mut h2: TestHashSet<u64> = TestHashSet::with_capacity_and_hasher(h.len(), Default::default());
4for &n in &h {
5    h2.insert(n);
6}

這可以與 serde 一起工作，但需要編寫自定義反序列化器。

混排元素

混排元素也可以解決這個問題。例如：

1// fast because h2 is built of elements which are not in iteration order of h
2let mut elems: Vec<_> = h.iter().copied().collect();
3elems.shuffle(&mut rnd);
4let mut h2: TestHashSet<u64> = TestHashSet::default();
5for n in elems {
6    h2.insert(n);
7}

當你不能控制表的構造方式，但要控制流入表的數據時，這是一個很好的 “快速解決方案”。要應用於 serde 情況就不那麼容易了，因爲它需要一個自定義序列化器。

隨機化散列器

這是最通用的解決方案，也是在標準庫中解決問題的方法。標準庫使用 RandomState 來構建默認的散列。

如果你使用另一個散列器，你只需要確保你使用的是隨機的那個。如果你的散列沒有提供一個隨機的散列構建器，你可以使用公共 API 創建一個。例如，對於 fxhash，我們可以創建一個實現 BuildHasher 的 FxRandomState：

 1#[derive(Copy, Clone, Debug)]
 2pub struct FxRandomState(usize);
 3
 4impl BuildHasher for FxRandomState {
 5    type Hasher = FxHasher;
 6
 7    fn build_hasher(&self) -> FxHasher {
 8        let mut hasher = FxHasher::default();
 9        hasher.write_usize(self.0);
10        hasher
11    }
12}

理想情況下，build_hash() 將只返回 fxhash::with_seed(self.0)，但 with_seed() 沒有提供，所以我們通過創建一個散列器並將種子混合到其中來獲得等價的功能。剩下的部分是爲散列生成器實現 Default，它將獲得實際的種子。爲了提高效率，我們不會每次都獲得隨機種子，而是隻在創建新線程時獲得。然後在一個線程內，我們將分配每個 FxRandomState(因此每個哈希表) 一個新的連續種子。

 1impl Default for FxRandomState {
 2    fn default() -> Self {
 3        thread_local! {
 4            static SEED: Cell<usize> = Cell::new(rand::thread_rng().gen())
 5        }
 6        let seed = SEED.with(|seed| {
 7            let n = seed.get();
 8            seed.set(n.wrapping_add(1));
 9            n
10        });
11        FxRandomState(seed)
12    }
13}

有了這個，我們可以將 TestHashSet 別名爲 HashSet<K, FxRandomState>，二次探測行爲就消失了。

本文翻譯自：

https://morestina.net/blog/1843/the-stable-hashmap-trap

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/usYRsJnBNQ-XBthltTbAlA