🧑‍💻

Dictionaryはなぜ高速なのか

に公開
C#
performance
dictionary
tech

はじめに

Dictionaryを参照するのは非常に高速と言われているのはよく聞いており、私もそれを鵜呑みにして業務でも便利なデータ構造として使用してきました。
ですが、内部構造を理解しておらず、なぜ「高速なのか」が曖昧となっていました。
したがって、今回はC#を例にした内部動作とパフォーマンスの内容について、調べたことを記載します。
※他言語でも基本的な内部動作は変わらないかと思うので、概念理解に良いと考えます。

対象読者

Dictionaryの内部動作について理解を深めたい方

Dictionaryの基本構造

Dictionary：ハッシュテーブルをベースとしており、キーのハッシュ値を使ってデータを格納・検索するコレクション
これにより、O(1)での操作が実現されている。
O(1): 定数時間で処理が完了するということ

なぜDictionaryの検索は高速なのか

Dictionaryの高速性は以下の仕組みにより成り立つ

  1. 要素追加時: キーをハッシュ化し、配列インデックスに変換して格納
  2. 検索時: 指定されたキーをハッシュ化し、一発で該当位置にアクセス

DBにおけるインデックスの考え方と同じ。
そのため、データ量に関係なく、一定の速度で検索が可能。

Dictionaryの初期化とメモリ管理

遅延初期化の仕組み

インスタンス生成時は、内部配列は生成されていない。
→メモリ効率とDictionaryオブジェクト生成コスト削減のため、遅延初期化となっている。

var dict = new Dictionary<string, int>();

最初の要素追加時の動作

dict["key"] = value;

このとき、以下の処理が実行される。

  1. 内部配列の存在有無を確認し、存在しないことを検知
  2. デフォルトサイズで内部配列を作成
  3. 要素を追加

リサイズの仕組み

手順2のデフォルトサイズとは、Dictionaryの容量を指す。
以下のコードで見ると分かりやすい。

var dict = new Dictionary<string, int>();

// 1つ目追加
dict["key1"] = 1;  // 内部容量3が作られ、1つ埋まる (1/3 = 33%)

// 2つ目追加
dict["key2"] = 2;  // 容量3のまま、2つ埋まる (2/3 = 67%)

// 3つ目追加
dict["key3"] = 3;  // 容量3のまま、3つ埋まる (3/3 = 100%)

// 4つ目追加
dict["key4"] = 4;  // ここでリサイズ発生。容量が7になる

つまり、容量が75%を超えると、リサイズが発生する。
リサイズ時は新しい配列を作成し、全要素を再配置するため、パフォーマンスに影響を与える。

では、初期容量を指定しないとDictionaryはパフォーマンス悪化の要因となってしまう？
→実際にはそんなことはなく、格納するデータ件数が1万件を超えてくる場合は初期容量を指定した方が良いとされている。

ループ処理での注意点

基本的なことだが、ループ内での初期化→破棄の繰り返しは、少量データでもパフォーマンス悪化につながるのでナンセンス。

// ❌ 悪い例：ループ内でDictionaryを初期化・破棄
for (int i = 0; i < 1000; i++)
{
    var dict = new Dictionary<string, int>();
    // 処理...
}

// ✅ 良い例：ループ外でDictionaryを定義
var dict = new Dictionary<string, int>();
for (int i = 0; i < 1000; i++)
{
    // 処理...
}

キー別のパフォーマンス

intやstringをキーとすると高速となる。
→intはハッシュ計算が軽量で、stringは.NETが最適化してくれるため
一方で独自クラスをキーとする場合、カスタムしたハッシュ化の実装が必要。。？

Discussion