HashMapを使ったループ(RUST)

Question

HashMapに設定した、すべての組み合わせでループで取得し処理をしたいと考えています。

let mut test= HashMap::new();
test.insert("aaa","1111");
test.insert("aaa","2222");
test.insert("bbb","3333");
test.insert("ccc","4444");

for( key, value ) in test.iter() {
    println!("key={},value={}", &key, &value);
}    

これを実行すると、以下のようになってしまうのですが、
key=bbb,value=3333
key=aaa,value=2222
key=ccc,value=4444

登録した順番通りに、すべてを取り出すにはどのように記載すればよいでしょうか。

Comments

[tatsuya6502]

「登録した順番通り」で取り出したいとのことですが、キー・バリューを以下の順番で登録したときは、どういう順番になってほしいのでしょうか？

"aaa", "1111"
"bbb", "3333"
"ccc", "4444"
"aaa", "2222"

案１：キー（"aaa"）が最初に現れたときの順番をキープ
"aaa", "2222"
"bbb", "3333"
"ccc", "4444"

案２："aaa"が最後に現れたときの順番
"bbb", "3333"
"ccc", "4444"
"aaa", "2222"

もし案１になって欲しいなら「キーの辞書順」に取り出すのではだめでしょうか？（登録順を実現するのはあまり簡単ではありませんが、キーの辞書順なら簡単です）

[IgaguriMK]

その候補だと、案1, 2 ともに「すべてを」取り出せていないので不適切だと思われます。

案１a：キー（"aaa"）が最初に現れたときの順番をキープ
"aaa", "1111"
"aaa", "2222"
"bbb", "3333"
"ccc", "4444"

案３：挿入順
"aaa", "1111"
"bbb", "3333"
"ccc", "4444"
"aaa", "2222"

になるのではないでしょうか。

[kokotao]

上記4ケースであれば、案３の挿入順になります。

[tatsuya6502]

案３で承知しました。IgaguriMKさんの回答が良いのかなと思いましたが、一応、別解としてVecを使ったやり方を回答しました。

Answer 1

全ての値が出ないのはなぜか
なぜ挿入順ではないのか

の2点に関して他の回答者さんが言及されているので、実装の例としてどうかなというのを置いておきます。
全ての値を保持するために Vec を使用し、挿入順で出力させるために linked_hash_map クレートを使用します。

use linked_hash_map::LinkedHashMap;
fn main() {
    let mut test = LinkedHashMap::new();

    let data = vec![
        ("aaa", "1111"),
        ("aaa", "2222"),
        ("bbb", "3333"),
        ("ccc", "4444"),
    ];

    for (key, value) in data {
        test.entry(key).or_insert_with(|| vec![]).push(value);
    }

    for (key, value) in test.iter() {
        for v in value {
            println!("key={},value={}", &key, &v);
        }
    }
}

key=aaa,value=1111
key=aaa,value=2222
key=bbb,value=3333
key=ccc,value=4444

この実装ではキーをまたいだ挿入順は保持できません。
保持する場合はそもそもMap系のデータ構造を使用するのが最適ではないかもしれません。

Comments

[kokotao]

どうもありがとうございます！ベストアンサー大変迷ってしまいました。。！助かりました！

Answer 2

要点が以下の2つに分かれるので、それぞれ説明します。

• 全ての値が出ないのはなぜか
• なぜ挿入順ではないのか

【全ての値が出ないのはなぜか】
Rustの標準ライブラリのMap系のコンテナはすべて１つのkeyに対して１つのvalueだけを持ちます。
ですから、 "aaa" をkeyにする挿入が2回行われているため、古いvalueはMapから削除されています。

このことは HashMap::insert()のドキュメントにも明記されています。

If the map did have this key present, the value is updated, and the old value is returned.

【なぜ挿入順ではないのか】
一般的に、ハッシュマップと呼ばれるデータ構造は挿入順を管理しません。
ハッシュマップはkeyのハッシュ値という整数値を用いて挿入/検索/削除を管理します。
ハッシュ値は一般的にランダムに分布するものを用いるので、内部での順番もランダムになります。

さらに、Rustの標準ライブラリの HashMap は、HashDoSという攻撃への対策として、HashMapごとに異なるハッシュ値が生成されるようになっています。
したがって、同じ順番で挿入しても、実行するたびに異なる順番で出力されます。

【解決案】
質問に含まれる（と思われる）条件は以下の3つです。

• 1つのkeyに対して複数のvalueが保持できる（multi-mapというもの）
• key, valueが挿入順に取得できる
• keyで検索してvalue(s)を取得できる

この3条件を満たしたMapを提供する total-order-multi-map というクレートがあるようです。
ただし、使用例は少ないようで、メンテナンスも止まっています。

この条件を満たすMapを自作する場合、比較的複雑なデータ構造になるため、まずデータ構造とアルゴリズムの分野をある程度把握しておく必要があるでしょう。

Answer 3

登録した順番通りに、すべてを取り出すにはどのように記載すればよいでしょうか。

他の回答にあるようにHashMapでは実現できません。他のコレクション型を使うことになりますが、質問に書かれている要件だけを満たせばいいのなら、Vecを使うのが簡単です。

let mut test = Vec::default();  // Vec<(&str, &str)> 型
test.push(("aaa", "1111"));
test.push(("bbb", "3333"));
test.push(("ccc", "4444"));
test.push(("aaa", "2222"));     // 質問のコードとは順番を変えた

for (key, value) in test {
    println!("key={},value={}", key, value);
}

実行結果

key=aaa,value=1111
key=bbb,value=3333
key=ccc,value=4444
key=aaa,value=2222

しかし、もしHashMapなどのマップが一般的に持つ以下の機能も必要なら話が変わってきます。

• keyで検索してvalue(s)を取得できる

Vec<(&str, &str)>でもできますが、要素数が多いときにマップと比べると効率が悪くなります。

一応、Vecでやる場合は以下のようにします。

let mut test = Vec::default();
test.push(("aaa", "1111"));
test.push(("bbb", "3333"));
test.push(("ccc", "4444"));
test.push(("aaa", "2222"));

// key "aaa"で検索して、対応する全てのvaluesを表示する
// testの全要素を検査するので、一般的なマップと比べると効率が悪い
for (key, value) in test.iter().filter(|(k, _)| k == &"aaa") {
    println!("key={},value={}", key, value);
}

// こう書くのと同じ
// for (key, value) in test {
//     if key == "aaa" {
//         println!("key={},value={}", key, value);
//     }
// }

実行結果

key=aaa,value=1111
key=aaa,value=2222

効率が悪いと困る場合（要素数が非常に多いときなど）は、他の回答にあるようにtotal-order-multi-mapのようなものが必要になります。

Comments

[kokotao]

どうもありがとうございます！ベストアンサー大変迷ってしまいました。。！助かりました！