---
title: コレクション型
url: https://doc.liz6.com/ja/rust/10-standard-library-depth/02-collection-types
locale: ja
area: rust
tags:
- rust
- standard-library-depth
date: 2026-06-30
modified: 2026-07-16
description: Vec はヒープ上の連続配列（ランダムアクセスは O(1)、末尾への挿入は償却 O(1)）、HashMap は SwissTable で実装（キャッシュフレンドリーなオープンアドレス法）、BTreeMap はキーでソート済み（Vec のキャッシュ局所性 vs BTreeMap の順序付き走査——両立は不可能）。VecDeque はリングバッファで、両端へのプッシュはどちらも O(1)。選択はアクセスパターンによる：連続走査には Vec、キーによる検索には HashMap、範囲検索には BTreeMap。
---

# コレクション型

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

## Vec<T>: 動的配列

```rust
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 も可选

```rust
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)（リングバッファのポインタのみ移動）。

## 選択ガイド

| 要件 | 推奨 |
|------|------|
| 順序保存 + ランダムアクセス | Vec |
| FIFO | VecDeque |
| 双端キュー | VecDeque |
| キー値ペア、順序なし | HashMap (デフォルト) / FxHashMap (高性能) |
| キー値ペア、順序あり、範囲スキャン | BTreeMap |
| 小規模コレクション (< 20 アイテム)、ヒープ不使用 | smallvec / tinyvec |
| 固定サイズ、コンパイル時に既知 | `[T; N]` |

## 参考

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

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