HashMap陷阱
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.440201369serialize: 0.071765342deserialize: 1.114031976
create: 1.391839734serialize: 0.081116361deserialize: 5.2052695
创建稍微快一些，序列化花的时间差不多，但是反序列化几乎比标准库散列慢5倍!在不同的集合尺寸下进行测试，反序列化时间接近二次曲线——1千万个元素的反序列化时间为5s，2千万个元素的反序列化时间为20s，4千万个元素的反序列化时间为69s，8千万个元素的反序列化时间为219s，我们已经看到陷阱了。
简而言之，将一个较大的表复制到一个较小的表中，将较大表的前半部分的键分配到连续的位置。然后，大表的下半部分的键必须与已经密集排列的键相匹配，这就形成了巨大的碰撞链。虽然这是一个临时的情况，在下一次调整大小时固定，但它明显影响性能。
尽管实现切换到不同的哈希探测策略，但是底层仍然使用带有线性探测和2的幂次方哈希表大小的开放寻址算法。
这个bug的所有修复都归结为对项目进行洗牌，以避免以不利的顺序建造。由于导致该问题的实际bug是在hashmap的实现中，所以我将这些bug称为变通方法，而不是适当的修复。
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来构建默认的散列。
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} 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}