suzuzusu日記

(´･ω･｀)

RustのHashMapの再現性を確保する

技術系

Rustの標準のHashMapのハッシュアルゴリズムでは再現性を確保することができないので，別のハッシュアルゴリズムを使って再現性を確保する方法をメモしておく．これはHashSetの場合も同様に再現性を確保することができます．

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.

doc.rust-lang.org

上記の引用のように，標準のHashMapのハッシュアルゴリズムではHashDoS攻撃を防ぐためにランダム性があり，同じコードでも再現不可能となる場合があります．

再現不可能なコード

例えば以下のようなコードは実行ごとに結果が異なります．

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    for i in 0..10 {
        map.insert(i, i);
    }
    let _ = map.iter().map(|x| print!("{:?},", x)).collect::<Vec<_>>();
    println!("");
}

実行1

(1, 1),(7, 7),(8, 8),(6, 6),(3, 3),(4, 4),(0, 0),(9, 9),(2, 2),(5, 5),

実行2

(0, 0),(3, 3),(5, 5),(6, 6),(2, 2),(4, 4),(7, 7),(8, 8),(9, 9),(1, 1),

rust-fnv

fnvはkeyのサイズが小さい場合に効率的に動作するハッシュアルゴリズムです． このライブラリには，標準のHashMapをfnvハッシュアルゴリズムに代替してエイリアスされたものがあります．今回はこれを使用して再現性を確保します．

再現可能なコード

use fnv::FnvHashMap;

fn main() {
    let mut map = FnvHashMap::default();
    for i in 0..10 {
        map.insert(i, i);
    }
    let _ = map.iter().map(|x| print!("{:?},", x)).collect::<Vec<_>>();
    println!("");
}

実行1

(5, 5),(4, 4),(7, 7),(6, 6),(1, 1),(0, 0),(3, 3),(2, 2),(9, 9),(8, 8),

実行2

(5, 5),(4, 4),(7, 7),(6, 6),(1, 1),(0, 0),(3, 3),(2, 2),(9, 9),(8, 8),

参考