Namaran

Code daily. Without assist.

2026-09-04

pick.rs

use std::collections::HashMap;

struct Lcg(u64);

impl Lcg {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        self.0 >> 33
    }
}

fn main() {
    let stock = HashMap::from([("apple", 3), ("fig", 5), ("pear", 7)]);
    let mut rng = Lcg(42);
    let mut picked: Vec<(&str, u64)> = stock.iter().map(|(&k, &n)| (k, rng.next() % n)).collect();
    picked.sort();
    println!("{picked:?}");
}

在庫の果物ごとに、0 以上在庫数未満の数を乱数で1つずつ選ぶプログラムです。乱数生成器のシードを 42 に固定しているので、何度実行しても同じ結果になるつもりです。本来は毎回 [("apple", 1), ("fig", 1), ("pear", 0)] を出力するはずですが、いまは [("apple", 2), ("fig", 4), ("pear", 0)] や [("apple", 1), ("fig", 4), ("pear", 2)] のように、実行するたびに違う結果を出力します。

Answer

Wrong

let stock = HashMap::from([("apple", 3), ("fig", 5), ("pear", 7)]);
let mut rng = Lcg(42);
let mut picked: Vec<(&str, u64)> = stock.iter().map(|(&k, &n)| (k, rng.next() % n)).collect();
picked.sort();

Lcg(42) が返す値の並びは、実行ごとに変わりません。変わるのは、その値をどの果物が受け取るかです。HashMap を iter で回す順番は決まっておらず、標準の HashMap はプロセスごとにランダムに選んだ鍵でハッシュ値を計算するので、実行するたびに順番が変わります1。1つ目の乱数が apple に行く回もあれば、pear に行く回もあります。

最後の picked.sort() で出力は名前順にそろうので、反復の順番が変わっていることは出力からは見えません。並べ替えは乱数を引いた後なので、どの果物がどの乱数を受け取ったかは元に戻りません。

Right

use std::collections::BTreeMap;
let stock = BTreeMap::from([("apple", 3), ("fig", 5), ("pear", 7)]);

BTreeMap は鍵の順に反復するので、乱数は毎回 apple、fig、pear の順に引かれます。乱数の並びも、それを受け取る順番も固定されるので、結果は1つに決まります。picked は最初から名前順になるので、sort を残しても出力は変わりません。

  1. HashMap の既定のハッシャー RandomState がランダムな鍵を使うのは、ハッシュ値を外から予測して衝突を狙う攻撃(HashDoS)を防ぐためです。