[Swift]辞書型のハッシュテーブルについて

はじめに

辞書型は順序を保持しないと言われますが、内部的にどのように管理されているのか気になったため、調べてみることにしました。

Dictionary型の内部構造

ハッシュテーブルとは？

Dictionary型は「ハッシュテーブル」と呼ばれるデータ構造で実装されています。
基本的な仕組みは以下の通りです。

1. キーのハッシュ化
   各キーはハッシュ関数によって数値（ハッシュ値）に変換されます
2. 値の格納
   このハッシュ値を使って内部配列の特定位置に値を格納します

以下のコードは人間にとっては「key1, key2, key3」の順で定義されていますが、内部的には全く異なる仕組みで格納されています。

let dict = ["key1": "12345", "key2": "12345", "key3": "12345"]

内部実装の詳細

Dictionaryが内部で値を格納する簡略化した図は以下のようになります。

内部配列: [空, 空, 空, ..., 空]  // 初期状態

// キー「key1」のハッシュ値が42と仮定
「key1」→ ハッシュ関数 → 42
内部配列: [空, ..., 42番目:「12345」, ...]

// キー「key2」のハッシュ値が7と仮定
「u」→ ハッシュ関数 → 7
内部配列: [空, ..., 7番目:「12345」, ..., 42番目:「12345」, ...]

// キー「key3」のハッシュ値が23と仮定
「p」→ ハッシュ関数 → 23
内部配列: [空, ..., 7番目:「12345」, ..., 23番目:「12345」, ..., 42番目:「12345」, ...]

この仕組みにより、定義時の順序は完全に失われます。

まとめ

Swift辞書（Dictionary）は効率的なデータ構造ですが、その内部実装の特性上、キーの順序は保証されません。今後、順序が必要になりそうな場面では辞書を使わない方が改修がしやすいのかなと思いました。

参考