コレクション型

Vec はヒープ上の連続配列（ランダムアクセスは O(1)、末尾への挿入は償却 O(1)）、HashMap は SwissTable で実装（キャッシュフレンドリーなオープンアドレス法）、BTreeMap はキーでソート済み（Vec のキャッシュ局所性 vs BTreeMap の順序付き走査——両立は不可能）。VecDeque はリングバッファで、両端へのプッシュはどちらも O(1)。選択はアクセスパターンによる：連続走査には Vec、キーによる検索には HashMap、範囲検索には BTreeMap。

Vec: 動的配列

let mut v = Vec::with_capacity(100);  // 事前割り当て — push 時の再割り当てを回避
v.push(42);

内部（64 ビット環境でスタック上 24 バイト）: [ptr: 8B | len: 8B | cap: 8B]。ptr はヒープ上の [T; cap] 配列を指す。

成長戦略: len == cap の場合、新しい capacity は max(old × 2, len + 1) となる。これは償却 O(1) の push に经典的な戦略である。注意: realloc はデータを新しいアドレスにコピーする可能性がある——旧 Vec の要素への参照は、realloc 後にダングリングポインタになる。これが、要素への参照を保持している間に push を行うと borrow checker がエラーになる理由である。

HashMap: デフォルトは SipHash、FxHash も可选

use std::collections::HashMap;
let mut map = HashMap::new();
map.insert("key", 42);

std の HashMap はデフォルトで SipHash 1-3 を使用する。なぜより高速なハッシュ関数ではないのか？SipHash の設計目標は HashDoS 攻撃への耐性である——攻撃者が大量のハッシュ衝突を引き起こすキーを生成し、HashMap の検索を O(n) に劣化させて CPU リソースを枯渇させる。SipHash のキーはランダム（プロセス起動ごとに生成）であり、攻撃者はハッシュ結果を予測できない。

代償: SipHash は FxHash よりも 10〜30% 遅い。入力が制御可能で外部にキーを公開しない場合は、rustc_hash::FxHashMap（rustc 自身が使用するハッシュテーブル）を使用できる——これは整数演算に基づく高速なハッシュ関数だが、HashDoS には弱い。

BTreeMap: 順序付きコレクション

B-tree 構造: キーは順序付きで保存され、各ノードには B 個のキーがある。検索/挿入は O(log N)。HashMap との比較での利点:

• 範囲スキャン⁠: map.range("a".."z") は O(log N + K) で実行可能。HashMap では不可能（順序なしのため）
• 予測可能なパフォーマンス⁠: 最悪ケースの O(N) への劣化がない（HashMap は衝突時に劣化する可能性がある）
• メモリの局所性⁠: B-tree のノードは連続している（キャッシュフレンドリー）

適用場面: 順序付き走査やキー範囲による検索が必要な場合。

VecDeque: 両端操作の最適化

内部はリングバッファ——push_front と push_back はどちらも償却 O(1)。FIFO キューや双端キューに適している。Vec との違い: Vec::remove(0) は O(n)（全要素の memmove が必要）、VecDeque::pop_front は O(1)（リングバッファのポインタのみ移動）。

選択ガイド

参考

• Rust Book: 第 8 章
• hashbrown: Rust HashMap の実装（現在は std に統合）
• smallvec: docs.rs/smallvec

Keywords: Vec, HashMap, BTreeMap, VecDeque, SipHash, FxHash, ring buffer, reallocation