2026-10-04
g_counter.rs
use std::collections::HashMap;
fn merge(dst: &mut HashMap<char, u64>, src: &HashMap<char, u64>) {
for (&id, &n) in src {
dst.entry(id).or_insert(n);
}
}
fn total(c: &HashMap<char, u64>) -> u64 {
c.values().sum()
}
fn main() {
let mut a = HashMap::from([('a', 1)]);
let mut b = HashMap::from([('b', 1)]);
merge(&mut b, &a);
*a.entry('a').or_insert(0) += 1;
merge(&mut b, &a);
merge(&mut a, &b);
println!("{} {}", total(&a), total(&b));
}
レプリカ a と b は、それぞれ自分の名前のキーに自分が数えた回数を持つカウンタです。merge は src の内容を dst に取り込み、互いに統合し合えばどちらの合計も同じ値に揃うようにするつもりの関数です。引数も標準入力も使いません。いまの出力は 3 2 で、b の合計が a に追いつきません。本来の出力は 3 3 です。
Answer
Wrong
for (&id, &n) in src {
dst.entry(id).or_insert(n);
}
or_insert(n) は、キーが無いときだけ n を入れます。キーがすでにあるときは今の値への参照を返すだけで、値は書き換えません。1回目の merge(&mut b, &a) で、b は 'a' の回数 1 を受け取ります。そのあと a が 'a' を 2 に増やして2回目の統合をしても、b にはもう 'a' のキーがあるので 1 のまま残ります。
最後に b を a へ統合すると、a は持っていなかった 'b' の 1 を受け取り、合計は 2 + 1 で 3 です。b の合計は古い 'a' のまま 1 + 1 で 2 になり、何度統合し合っても 'a' は追いつきません。
Right
for (&id, &n) in src {
let mine = dst.entry(id).or_insert(0);
*mine = (*mine).max(n);
}
同じキーがあるときは、2つの回数の大きい方を残します。各レプリカの回数は増える一方なので、大きい方が新しい値です。足すのではなく大きい方を取るので、同じ内容を何度統合しても回数は増えず、統合する順番にも左右されません。b の 'a' は2回目の統合で 2 になり、どちらの合計も 3 に揃います1。
- 統合が結合的・可換的・冪等なので、状態を受け取る順番や回数によらず、すべてのレプリカが同じ状態に収束します。このように状態どうしを統合するデータ型を、状態ベースの CRDT と呼びます。