hashmap - 是否有任何 HashMap 实现在程序运行之间具有一致的顺序？

Question

我观察到 HashMap 具有不同的元素顺序，即使在下一个程序启动时具有相同的数据。看起来 HashMap 使用一些绝对地址来对元素进行排序。如果插入相同的数据，是否有任何其他 HashMap 实现具有相同的行为？

Answer 1

I've observed that HashMap has a different order of elements even with the same data on the next program start.

你不必观察任何东西，这是documented by HashMap :

By default, HashMap uses a hashing algorithm selected to provide resistance against HashDoS attacks. The algorithm is randomly seeded, and a reasonable best-effort is made to generate this seed from a high quality, secure source of randomness provided by the host without blocking the program.

值得注意的是，这意味着在相同的程序运行中具有相同插入值集的两个 HashMap 可能会有不同的顺序:

use std::collections::HashMap;

fn main() {
    let a = (0..100).zip(100..200);

    let hash_one: HashMap<_, _> = a.clone().collect();
    let hash_two: HashMap<_, _> = a.clone().collect();

    // prints "false", most of the time
    println!("{}", hash_one.into_iter().eq(hash_two));
}

文档还告诉您如何解决该问题:

The hashing algorithm can be replaced on a per-HashMap basis using the default, with_hasher, and with_capacity_and_hasher methods. Many alternative algorithms are available on crates.io, such as the fnv crate.

自从我在 twox-hash 上工作以来，我将展示它作为一个例子:

use std::hash::BuildHasherDefault;
use std::collections::HashMap;
use twox_hash::XxHash;

let mut hash: HashMap<_, _, BuildHasherDefault<XxHash>> = Default::default();
hash.insert(42, "the answer");
assert_eq!(hash.get(&42), Some(&"the answer"));

---

话虽这么说，依赖 HashMap 的顺序听起来不是个好主意。也许您应该使用不同的数据结构，例如 BTreeMap .

在其他情况下，您实际上关心插入的顺序。为此，indexmap crate是合适的。