RustのHashSetとBTreeMap

HashSet は、重複のない値を集めたコレクションです。同じ値を2回入れても、保存されるのは1回分だけです。入口にある招待客リストを思い浮かべてください。受付の人が気にするのは、あなたの名前がリストにあるかどうかだけで、何回書かれているかではありません。

Vec と HashMap はもう知っていますね。このページでは、ほかによく使うコレクションを紹介します。HashSet、並び順を保つ BTreeMap と BTreeSet、そしてキューに使う VecDeque です。最後に、どれを選べばいいかがわかる表も用意しています。

HashSetを作る

HashSet は std::collections にあるので、use の行が必要です。insert メソッドは bool を返します。値が新しければ true、すでにあれば false です。

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::new();

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // すでにある

    println!("重複のないタグは{}個", tags.len());
}

実行結果:

true
true
false
重複のないタグは2個

▶ 実際に試してみよう

この bool は、見た目以上に役に立ちます。追加するのと同時に「これは前に見たことがある？」に答えてくれるので、別にチェックを書く必要がありません。

値の確認と削除

contains は、値がセットに入っているかどうかを教えてくれます。remove は値を取り除き、insert と同じように、実際に何かが削除されたかどうかを bool で返します。

use std::collections::HashSet;

fn main() {
    let mut online: HashSet<&str> = HashSet::from(["ana", "ben", "chen"]);

    println!("benはオンライン？ {}", online.contains("ben"));

    println!("benを削除: {}", online.remove("ben"));
    println!("もう一度benを削除: {}", online.remove("ben"));

    println!("benはオンライン？ {}", online.contains("ben"));
    println!("オンラインは{}人", online.len());
}

実行結果:

benはオンライン？ true
benを削除: true
もう一度benを削除: false
benはオンライン？ false
オンラインは2人

▶ 実際に試してみよう

なぜここで Vec ではなくセットを使うのでしょうか。Vec で contains を使うと、要素をひとつずつ全部調べます。HashSet なら、どれだけ大きくなっても答えに一直線でたどり着きます。ユーザーが100万人いたら、この差はとても大きくなります。

注意

HashSet には決まった順番がありません。{:?} で表示したりループで回したりすると、実行するたびに順番が変わることがあります。表示するときに安定した順番がほしいなら、値を Vec にコピーして並べ替えるか、BTreeSet（このあと説明します）を使いましょう。

Vecから重複を取り除く

とてもよくある作業です。重複のあるリストがあって、それぞれの値を1回ずつにしたい。もとの順番を気にするかどうかで、よい方法が2つあります。

use std::collections::HashSet;

fn main() {
    let visits = vec![3, 1, 3, 2, 1, 5, 2];

    // 方法1: セットに集めてから、並べ替えて順番を安定させる
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("並べ替えた結果: {:?}", sorted);

    // 方法2: 各値が最初に出てきたものだけを、もとの順番のまま残す
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("もとの順番: {:?}", in_order);
}

実行結果:

並べ替えた結果: [1, 2, 3, 5]
もとの順番: [3, 1, 2, 5]

▶ 実際に試してみよう

方法2では、insert が返す bool を使っています。retain はクロージャが true を返した要素だけを残します。そして insert が true を返すのは、その値を初めて見たときだけです。

集合演算: 和集合、積集合、差集合

セットは、ベン図の円のように組み合わせることができます。どのメソッドもイテレータを返すので、結果を Vec に集め、表示する前に並べ替えます。こうすると、毎回同じ結果が表示されます。

use std::collections::HashSet;

fn main() {
    let alice: HashSet<&str> = HashSet::from(["rust", "python", "go"]);
    let bob: HashSet<&str> = HashSet::from(["go", "java", "rust"]);

    let mut both: Vec<_> = alice.intersection(&bob).collect();
    both.sort();
    println!("2人とも知っている: {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("どちらかが知っている: {:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("aliceだけ: {:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("片方だけが知っている: {:?}", only_one);
}

実行結果:

2人とも知っている: ["go", "rust"]
どちらかが知っている: ["go", "java", "python", "rust"]
aliceだけ: ["python"]
片方だけが知っている: ["java", "python"]

▶ 実際に試してみよう

intersection は積集合（共通部分）、union は和集合です。difference（差集合）には向きがあります。alice.difference(&bob) は「Aliceは知っているけれどBobは知らないもの」です。入れ替えると、Bobのリストが得られます。symmetric_difference（対称差）は両方向を一度に求めます。つまり、どちらか片方だけが知っているものすべてです。

BTreeMapとBTreeSet: いつも並んでいる

BTreeMap は HashMap とまったく同じように、BTreeSet は HashSet とまったく同じように使えます。違いは、キーを並べ替えた状態で保つことです。ループで回すと、いつでもキーが順番どおりに出てきます。

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let text = "the cat sat on the mat the end";

    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    for (word, count) in &counts {
        println!("{word}: {count}");
    }

    let scores: BTreeSet<u32> = BTreeSet::from([72, 95, 58, 88]);
    println!("最低点: {:?}", scores.first());
    println!("最高点: {:?}", scores.last());
    println!("全部: {:?}", scores);
}

実行結果:

cat: 1
end: 1
mat: 1
on: 1
sat: 1
the: 3
最低点: Some(58)
最高点: Some(95)
全部: {58, 72, 88, 95}

▶ 実際に試してみよう

entry は、HashMap のページで出てきたのと同じAPIです。マップが BTreeMap なので、並べ替えの手順を足さなくても、単語がアルファベット順に出てきます。

ここでは文章をあえて英語のままにしています。split_whitespace は空白で単語を区切るので、単語の間にスペースを入れない日本語の文ではうまく分けられません。また、アルファベット順に並ぶ様子も英単語のほうがわかりやすいからです。

どちらを選べばいい？

• 基本は HashMap / HashSet を選びましょう。たいていは検索が速いです。
• データを順番どおりに扱いたいときは BTreeMap / BTreeSet を選びます。並べ替えたレポートを表示する、最小や最大のキーを探す、ある範囲のキーを取り出す、といった場面です。

VecDeque: キュー

VecDeque（「ベックデック」と読みます）は、両端での追加と削除がすばやくできるリストです。そのため、キューにぴったりです。キューとは、列に並んで待つ人たちのように、先に入ったものから先に出ていく（先入れ先出し）しくみです。

use std::collections::VecDeque;

fn main() {
    let mut line: VecDeque<&str> = VecDeque::new();
    line.push_back("ana");
    line.push_back("ben");
    line.push_back("chen");

    while let Some(person) = line.pop_front() {
        println!("{person}さんの番です。残りは{}人", line.len());
    }
}

実行結果:

anaさんの番です。残りは2人
benさんの番です。残りは1人
chenさんの番です。残りは0人

▶ 実際に試してみよう

これを Vec::remove(0) で書くこともできます。でもそれだと、残りの要素を全部ひとつずつずらすことになります。VecDeque の pop_front はそれをしないので、列が長くなっても速いままです。

どのコレクションを使えばいい？

コレクション	こんなときに使う	例
Vec<T>	順番のあるリストを、位置でアクセスしたい	ファイルの各行、点数のリスト
HashMap<K, V>	キーから値をすばやく探したい	ユーザー名 → ユーザー情報
HashSet<T>	重複のない値と、「これは入ってる？」のすばやいチェック	訪れたページ、禁止ワード
BTreeMap<K, V>	キー → 値で、キーを並べた状態に保ちたい	アルファベット順に表示する単語の出現回数
VecDeque<T>	両端で追加・削除したい	タスクやメッセージのキュー

迷ったら、まずは Vec から始めましょう。何度も何度も中を検索していると気づいたらセットやマップに、先頭からの削除が多いと気づいたら VecDeque に切り替えればいいのです。

よくある間違い

必要なderiveをつけずに、自分の構造体をHashSetに入れてしまう。 HashSet は、値をハッシュ化したり、値どうしが等しいかを比べたりする必要があります。自分で作った構造体は、それを自動ではやってくれません。

use std::collections::HashSet;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
}

error[E0277]: the trait bound `Point: Eq` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Eq` is not implemented for `Point`

error[E0277]: the trait bound `Point: Hash` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Hash` is not implemented for `Point`

コンパイラは「Point には Eq トレイトも Hash トレイトも実装されていない」と言っています。直し方は、構造体の上に #[derive(PartialEq, Eq, Hash)] を1行足すだけです。BTreeSet の場合は、並べ方がわかるように PartialOrd と Ord も必要です。それぞれの意味はよく使うトレイトのページを見てください。

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
    visited.insert(Point { x: 1, y: 0 });
    visited.insert(Point { x: 0, y: 0 }); // 重複なので無視される
    println!("訪れたマスは{}個", visited.len());
}

実行結果:

訪れたマスは2個

▶ 実際に試してみよう

練習問題

1. 最初の重複

単語の配列 ["red", "blue", "green", "blue", "red"] から、2回目に登場した最初の単語を表示してください。ヒント：insert は、値がすでにセットに入っているときに false を返します。ループは break で止められます。

解答を見る

use std::collections::HashSet;

fn main() {
    let words = ["red", "blue", "green", "blue", "red"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("最初に重複した単語: {word}");
            break;
        }
    }
}

実行結果:

最初に重複した単語: blue

▶ 実際に試してみよう

!seen.insert(word) は「追加に失敗した」、つまり「これは前にも見た」という意味になります。最初に重複するのは "blue" です。"red" も重複しますが、それはもっと後です。

2. 文字をアルファベット順に数える

"mississippi" の中で、それぞれの文字が何回出てくるかを数え、アルファベット順に表示してください。ヒント：BTreeMapのセクションで使った entry(...).or_insert(0) のテクニックを BTreeMap でそのまま使い、word.chars() でループします。

解答を見る

use std::collections::BTreeMap;

fn main() {
    let word = "mississippi";
    let mut counts = BTreeMap::new();

    for letter in word.chars() {
        *counts.entry(letter).or_insert(0) += 1;
    }

    for (letter, count) in &counts {
        println!("{letter}: {count}");
    }
}

実行結果:

i: 4
m: 1
p: 2
s: 4

▶ 実際に試してみよう

HashMap だと、この4行はどんな順番で出てくるかわかりません。BTreeMap はキーを並べた状態に保つので、毎回 i、m、p、s のアルファベット順に表示されます。

まとめ

• HashSet は重複のない値を保存します。insert と remove は、何かが変わったかどうかを bool で返します。
• セットの contains は、とても大きなセットでも速いです。Vec では要素を全部調べます。
• union、intersection、difference、symmetric_difference で集合演算ができます。表示する前に結果を並べ替えましょう。
• BTreeMap と BTreeSet はキーを並べた状態に保ちます。順番が大事なときに使います。
• キューといえば VecDeque です。push_back で列に並び、pop_front で列から出ます。

理解度チェック

理解度チェック

1. x がすでにセットに入っているとき、set.insert(x) は何を返しますか？

true エラー false 古い値

2. 自分で並べ替えなくても、単語の出現回数をアルファベット順に表示したいです。いちばん合うマップはどれですか？

HashMap BTreeMap Vec VecDeque

3. HashSet を {:?} で表示すると、実行するたびに結果が変わることがあるのはなぜですか？

HashSet には決まった順番がないから {:?} がランダムだから 時間がたつとセットから値が消えるから デバッグモードでしか起きない

4. 先入れ先出しのキューにいちばん向いているコレクションはどれですか？

HashSet BTreeSet HashMap VecDeque

スコア: 0 / 4

さらに詳しく

• std::collections の概要 — 標準ライブラリのドキュメント（英語）：コレクションの選び方を詳しく解説したガイドです。各操作の速さも載っています。
• HashSet — Rust By Example 日本語版：union、intersection、difference を実際に動かせる例です。
• HashSet — 標準ライブラリのドキュメント（英語）：is_subset や retain も含めた、セットのすべてのメソッドです。
• BTreeMap — 標準ライブラリのドキュメント（英語）：並んだ状態を保つマップです。キーの一部を取り出す range も載っています。
• VecDeque — 標準ライブラリのドキュメント（英語）：push_front、pop_back、front など、キューのメソッドがすべてそろっています。