Rustプログラミングにおいて、データの重複を許さず、かつ高速に要素を検索・管理したい場面は頻繁に登場します。

そのような要件を効率的に満たすのが、標準ライブラリの std::collections::HashSet です。

HashSet はハッシュテーブルを基盤としており、要素の挿入、検索、削除といった基本操作を平均して O(1) という驚異的な速さで実行できます。

本記事では、Rustにおける HashSet の基本的な使い方から、パフォーマンスを最大限に引き出すための最適化テクニックまで、実戦で役立つ知識を詳しく解説します。

目次 [ close ]
  1. RustにおけるHashSetの基本概念
  2. 基本的な操作：挿入、検索、削除
    1. 要素の挿入 (insert)
    2. 要素の検索 (contains)
    3. 要素の削除 (remove)
  3. HashSetの内部構造とパフォーマンス
    1. デフォルトのハッシュアルゴリズム：SipHash
    2. 時間計算量（Time Complexity）
  4. パフォーマンスを最適化する高度なテクニック
    1. キャパシティの事前割り当て
    2. カスタムハッシュ関数の利用
  5. 集合演算の活用方法
    1. 和集合、積集合、差集合
  6. ユーザー定義型でのHashSetの利用
  7. BTreeSetとの使い分け
  8. まとめ

RustにおけるHashSetの基本概念

HashSet は、数学における「集合」の概念をプログラム上で実現したデータ構造です。

同じ値を二重に保持することはできず、常に一意な要素のみが格納されます。

Rustの HashSet は、内部的に hashbrown と呼ばれる非常に効率的なハッシュマップ実装を採用しています。

この実装は、Googleが開発した「SwissTable」アルゴリズムをベースにしており、メモリ効率とCPUキャッシュの利用効率が極めて高いのが特徴です。

2026年現在のRustにおいても、この HashSet は標準的なコレクションとして、システムのパフォーマンスを支える重要な役割を担っています。

基本的な操作：挿入、検索、削除

HashSet を使用するためには、まず std::collections::HashSet をインポートする必要があります。

ここでは、最も基本的な操作である要素の追加、存在確認、そして削除の方法を見ていきましょう。

要素の挿入 (insert)

新しい要素を集合に追加するには、insert メソッドを使用します。

Rust
use std::collections::HashSet;

fn main() {
    // 空のHashSetを作成
    let mut books = HashSet::new();

    // 要素を挿入
    books.insert("The Rust Programming Language");
    books.insert("Rust in Action");
    
    // 既に存在する要素を挿入しようとした場合、falseを返します
    let is_new = books.insert("The Rust Programming Language");
    
    println!("Is new insert: {}", is_new);
}
実行結果
Is new insert: false

insert メソッドは、要素が新しく追加された場合は true を返し、既に存在していた場合は false を返します。

要素の検索 (contains)

特定の要素が集合に含まれているかを確認するには、contains メソッドを利用します。

この操作は非常に高速であり、リスト（Vec）を線形探索する場合と比較して、要素数が増えるほど大きなパフォーマンス差が生まれます。

Rust
if books.contains("Rust in Action") {
    println!("指定した本はコレクション内に存在します。");
}

検索時に所有権を奪うことはなく、不変の参照を渡すだけで高速なチェックが可能です。

要素の削除 (remove)

集合から要素を削除するには、remove メソッドを使用します。

Rust
books.remove("Rust in Action");

if !books.contains("Rust in Action") {
    println!("削除が完了しました。");
}

remove メソッドも insert と同様に、削除に成功したかどうかを bool 値で返却します。

HashSetの内部構造とパフォーマンス

HashSet のパフォーマンスを深く理解するためには、その内部構造を知ることが重要です。

Rustの HashSet は、デフォルトで SipHash というハッシュアルゴリズムを使用しています。

デフォルトのハッシュアルゴリズム：SipHash

SipHashは、ハッシュ衝突攻撃（Hash DoS攻撃）に対して非常に強い耐性を持っています。

これにより、外部からの入力をそのままハッシュキーとして扱うWebサーバーなどの用途でも、安全に利用することができます。

しかし、安全性を重視している分、計算速度においては後述する他のアルゴリズムに一歩譲る面があります。

時間計算量（Time Complexity）

HashSet の主な操作における平均的な時間計算量は以下の通りです。

操作平均計算量最悪計算量
挿入 (insert)O(1)O(n)
検索 (contains)O(1)O(n)
削除 (remove)O(1)O(n)

最悪の場合が O(n) となるのは、ハッシュ衝突が多発して全ての要素が同じバケットに集中した場合ですが、RustのSipHashではこれが起こりにくいよう設計されています。

パフォーマンスを最適化する高度なテクニック

標準の HashSet は十分に高速ですが、特定のシナリオではさらにパフォーマンスを向上させる手法があります。

キャパシティの事前割り当て

HashSet に大量のデータを挿入することがあらかじめ分かっている場合は、with_capacity を使用してメモリを事前に確保しましょう。

デフォルトの new メソッドで作成した場合、要素が増えるたびに「リハッシュ（メモリ再確保とデータの再配置）」が発生し、これがオーバーヘッドとなります。

Rust
// 1000個の要素を格納することを想定して作成
let mut large_set = HashSet::with_capacity(1000);

事前のメモリ割り当てを行うだけで、大量挿入時の実行時間を劇的に短縮できる場合があります。

カスタムハッシュ関数の利用

セキュリティよりも速度が最優先される計算集約的な処理では、デフォルトの SipHash ではなく、より高速な FxHash や AHash を使用することを検討してください。

これらは rustc 自体のコンパイル速度向上にも使われている手法です。

外部クレートである fxhash などを導入することで、ハッシュ計算そのもののコストを下げることが可能です。

集合演算の活用方法

HashSet の強力な機能の一つに、複数の集合を組み合わせる集合演算があります。

Rustでは、これらをイテレータを通じて直感的に実行できます。

和集合、積集合、差集合

以下のコードは、2つの集合間で共通する要素や、異なる要素を抽出する例です。

Rust
let set_a: HashSet<i32> = [1, 2, 3].iter().cloned().collect();
let set_b: HashSet<i32> = [3, 4, 5].iter().cloned().collect();

// 積集合 (どちらにも含まれる)
let intersection: HashSet<_> = set_a.intersection(&set_b).collect();
// {3}

// 和集合 (どちらか一方に含まれる)
let union: HashSet<_> = set_a.union(&set_b).collect();
// {1, 2, 3, 4, 5}

// 差集合 (set_aにのみ含まれる)
let difference: HashSet<_> = set_a.difference(&set_b).collect();
// {1, 2}

これらのメソッドは新しい集合を作成するのではなく、要素への参照を返すイテレータを提供するため、メモリ消費を抑えながら柔軟な処理が可能です。

ユーザー定義型でのHashSetの利用

自作の構造体（struct）を HashSet の要素として格納したい場合、特定のトレイトを実装する必要があります。

具体的には、Eq、PartialEq、そして Hash の3つが必要です。

これらは通常、derive マクロを使用して簡単に実装できます。

Rust
#[derive(PartialEq, Eq, Hash, Debug)]
struct User {
    id: u32,
    name: String,
}

fn main() {
    let mut users = HashSet::new();
    users.insert(User { id: 1, name: "Alice".to_string() });
}

この derive を忘れると、コンパイルエラーが発生して HashSet に格納することができません。

「等価性の判断」と「ハッシュ値の計算」が一貫していることが、HashSetが正しく動作するための絶対条件です。

BTreeSetとの使い分け

Rustには HashSet の他にも、要素を管理する BTreeSet が存在します。

どちらを使うべきか迷った際は、以下の基準を参考にしてください。

  • HashSet: 順序を気にせず、とにかく高速に検索・挿入を行いたい場合。
  • BTreeSet: 要素が常にソートされた状態を保ちたい場合や、範囲検索（レンジクエリ）を行いたい場合。

HashSet はハッシュ値に基づいた配置を行うため、イテレータで取り出す際の順番は実行のたびに変わる可能性があることに注意しましょう。

まとめ

Rustの HashSet は、一意なデータを高速かつ安全に扱うための極めて強力なツールです。

標準で備わっている SipHash アルゴリズムによる安全性と、hashbrown 実装による高速性が高度にバランスされています。

パフォーマンスをさらに追求する場合は、with_capacity による事前割り当てや、用途に応じたカスタムハッシュ関数の選択が鍵となります。

また、集合演算やユーザー定義型への適用をマスターすることで、Rustでのデータ処理はより簡潔で効率的なものになるでしょう。

今回紹介した基本操作と最適化手法を、ぜひ日々の開発に役立ててください。