プログラム実行の間に一貫した順序付けを持つHas​​hMap実装がありますか？

Question

HashMapは、次のプログラム開始時に同じデータであっても要素の順序が異なります。 HashMapは、要素をソートするためにいくつかの絶対アドレスを使用しているようです。他のHashMap実装がありますか？同じデータが挿入された場合、同じ動作をしますか？

Answer 1

HashMapは、次回のプログラム開始時に同じデータであっても要素の順序が異なります。

あなたはに何を観察していない、これはdocumented by HashMapです：デフォルトでは

、HashMapはHashDoS攻撃に対する耐性を提供するように選択ハッシュアルゴリズムを使用しています。アルゴリズムはランダムにシードされ、プログラムをブロックせずにホストによって提供される高品質で安全な乱数源からこのシードを生成するための妥当なベストエフォートが作られます。

これは同じプログラムの実行で挿入された値の同じセットを持つ2つのHashMap sがそう異なる順序を持っていることを意味していることは注目に値します：

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)); 
} 

ドキュメントはまたどのようにわかりますハッシュアルゴリズムはdefault、を使用してパーHashMap的に交換することができます

：問題を解決しますおよびwith_capacity_and_hasherの方法が挙げられる。 fnv crateなど、多くの代替アルゴリズムがcrates.ioで利用できます。

私は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のような別のデータ構造を使用する必要があります。

実際には、の挿入の順番に注意してください。そのためにはordermap crateが適切です。

Answer 2

HashMap::with_hasher()には、デフォルトのRandomState以外を使用してください。

Answer 3

私はlinked-hash-mapがこれの事実上の箱であると信じています。