Slowdown when inserting elements in the iteration order of another FxHashMap

It seems that in 2.0.0 there has been a regression in the fix to https://github.com/rust-lang/rustc-hash/issues/14.

In 1.2.0 it was possible to avoid the issue by using different seeds for different FxHashMaps (by manually setting the seed or using a randomized seed). This no longer works in 2.0.0. Even if you use two FxHashMaps/FxHashSets with different seeds you still get extremely bad performance when values are inserted in the iteration order of another FxHashMap/FxHashSet.

For example, try this:

fn main() {
    let mut rnd = rand::thread_rng();

    let t0 = Instant::now();
    let mut h1 = HashSet::with_hasher(FxSeededState::with_seed(9943));
    for _ in 0..10_000_000 {
        h1.insert(rnd.gen::<u64>());
    }
    let t1 = Instant::now();
    println!("build: {}", (t1 - t0).as_secs_f64());

    let t0 = Instant::now();
    let mut h2 = HashSet::with_hasher(FxSeededState::with_seed(1829319203));
    for &n in h1.iter() {
        h2.insert(n);
    }
    let t1 = Instant::now();
    println!("rebuild: {}", (t1 - t0).as_secs_f64());

    println!("{}", h2.len());
}

On my computer this takes 0.3 seconds for the inital build, but 2.6 seconds for the rebuild with 2.0.0. With 1.2.0 this takes 0.3 seconds for both build and rebuild.

Note that FxHashSetRand and FxHashMapRand have the same problem, since no matter what seeds they generate you get more or less the same 8-9x slowdown.

Start by comparing the rustc-hash 1.2.0 and 2.0.0 hashing and seed behavior, then run the supplied Rust reproducer to measure insertion order effects. Done means restoring comparable performance for values inserted in another FxHashMap/FxHashSet's iteration order, with a regression test covering distinct seeds and randomized variants.