# 機能設計書 23-辞書（Dict）

## 概要

本ドキュメントは、Julia Base ライブラリが提供する辞書（Dict）機能の設計について記述する。辞書はキーと値のペアを格納する可変長連想コンテナであり、ハッシュテーブルを基盤として高速な挿入・検索・削除操作を提供する。

### 本機能の処理概要

辞書機能は、`Dict{K,V}` を中心とした標準的なハッシュテーブル実装と、`IdDict{K,V}`（オブジェクトIDによる等値比較）、`WeakKeyDict{K,V}`（弱参照キー）、`ImmutableDict{K,V}`（不変辞書）の各バリアントを提供する。オープンアドレス法（線形探査）によるハッシュテーブル実装であり、ショートハッシュによるスロットメタデータ管理で高速なルックアップを実現している。

**業務上の目的・背景**：プログラムにおいてキーと値の対応関係を管理することは最も基本的なデータ構造操作の一つである。設定値の管理、カウンタ、キャッシュ、ルックアップテーブルなど、あらゆる場面で使用される。Julia の Dict は isequal/hash ベースの等値比較を行い、線形探査法とショートハッシュ（7ビット）による高速化を実装している。

**機能の利用シーン**：設定パラメータの格納、データのインデックス付けとルックアップ、カウンタ（要素の出現回数集計）、キャッシュ・メモ化、環境変数の管理、JSON等の構造化データの表現で利用される。

**主要な処理内容**：
1. `Dict{K,V}()` による空辞書の作成
2. `Dict(pairs...)` / `Dict(itr)` による辞書の構築
3. `getindex` / `setindex!` によるキーアクセスと値設定
4. `get` / `get!` / `haskey` によるキー存在確認と安全なアクセス
5. `delete!` / `pop!` によるキーの削除
6. `keys` / `values` / `pairs` によるイテレーション
7. `merge` / `merge!` / `mergewith` による辞書のマージ
8. `sizehint!` / `rehash!` によるハッシュテーブルのリサイズ

**関連システム・外部連携**：なし。Base モジュール内で完結する。

**権限による制御**：なし。すべてのユーザーが利用可能である。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面関連なし（ライブラリ関数） |

## 機能種別

CRUD操作（キー値ペアの作成・読取・更新・削除）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| K | Type | No | キーの型 | 任意の型 |
| V | Type | No | 値の型 | 任意の型 |
| key | K | Yes（アクセス時） | 検索・挿入キー | convert(K, key) が可能であること |
| value | V | Yes（挿入時） | 格納する値 | convert(V, value) が可能であること |
| itr | Iterable | No | (key, value) ペアのイテラブル | 2-tupleを生成するイテラブル |

### 入力データソース

Julia プログラム内のリテラル、Pair オブジェクト、2-tuple を生成するイテラブル。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| value | V | キーに対応する値 |
| keys | KeySet | 全キーのビュー |
| values | ValueIterator | 全値のビュー |
| pairs | Pairs | 全キー値ペアのイテレータ |

### 出力先

呼び出し元への戻り値。

## 処理フロー

### 処理シーケンス

```
1. Dict{K,V}() 作成
   └─ slots/keys/vals の Memory を初期化（サイズ0）
2. setindex!(h, v, key) での挿入
   └─ convert(K, key), convert(V, v) で型変換
   └─ ht_keyindex2_shorthash!(h, key) でスロット検索
   └─ index > 0: 既存キー → 値を上書き
   └─ index < 0: 新規キー → _setindex! でスロットに書き込み
   └─ 充填率 > 2/3: rehash! でリサイズ
3. getindex(h, key) での取得
   └─ ht_keyindex(h, key) でスロット検索
   └─ index > 0: h.vals[index] を返す
   └─ index < 0: KeyError を投げる
4. delete!(h, key) での削除
   └─ ht_keyindex(h, key) でスロット検索
   └─ _delete!(h, index): スロットを 0x7f（tombstone）に設定
```

### フローチャート

```mermaid
flowchart TD
    A[setindex! 呼び出し] --> B[convert K/V 型変換]
    B --> C[hashindex: ハッシュ値計算]
    C --> D[ht_keyindex2_shorthash!]
    D --> E{スロット状態}
    E -->|empty 0x00| F[新規挿入: _setindex!]
    E -->|filled 0x80+| G{キー一致?}
    E -->|missing 0x7f| H[tombstoneに挿入候補記録]
    G -->|Yes| I[値を上書き]
    G -->|No| J[次のスロットへ線形探査]
    J --> E
    H --> J
    F --> K{充填率 > 2/3?}
    K -->|Yes| L[rehash! リサイズ]
    K -->|No| M[完了]
    I --> M
    L --> M
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 等値比較 | キーの比較は isequal を使用（==ではない） | 常時 |
| BR-02 | ハッシュ関数 | キーのハッシュは hash 関数を使用 | 常時 |
| BR-03 | 充填率制御 | (count + ndel) * 3 > size * 2 でリハッシュ | 挿入時 |
| BR-04 | ショートハッシュ | スロットメタデータとして上位7ビットを使用し、キー比較前にフィルタリング | 検索時 |
| BR-05 | tombstone | 削除されたスロットは 0x7f でマーク、次回のリハッシュまで保持 | delete! 時 |
| BR-06 | 可変キーの注意 | 可変オブジェクトをキーにした場合、変更後はテーブル不整合の可能性 | 可変キー使用時 |

### 計算ロジック

- `hashindex(key, sz)`: `hash(key)` の下位ビットでインデックス計算、上位7ビットでショートハッシュ生成
- `_shorthash7(hsh)`: `(hsh >> (8sizeof(UInt)-7)) | 0x80` - 最上位ビットを1にして「使用中」を示す
- テーブルサイズは常に2のべき乗（`_tablesz`）
- リハッシュ時のサイズ: count > 64000 なら 2倍、そうでなければ 4倍

## データベース操作仕様

### 操作別データベース影響一覧

該当なし（インメモリデータ構造）。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | KeyError | getindex / pop! で存在しないキーにアクセス | get / haskey で事前確認するか、get でデフォルト値を使用 |
| - | KeyTypeError | 型変換不可能なキーで setindex! | 正しい型のキーを使用 |
| - | AssertionError | 並行書き込み検出 | 排他制御を使用する |

### リトライ仕様

リトライは不要。

## トランザクション仕様

Dict はスレッドセーフではない。並行アクセス時は外部での排他制御が必要。`h.age` フィールドにより並行書き込みを検出する仕組みがある（rehash!時のアサーション）。

## パフォーマンス要件

- 平均 O(1) のキーアクセス・挿入・削除
- ショートハッシュによる早期フィルタリングで不要な isequal 呼び出しを削減
- 最大探査距離（maxprobe）を管理し、検索の上限を設定
- `sizehint!` で事前にテーブルサイズを確保可能

## セキュリティ考慮事項

- ハッシュ関数はランダムシードを使用（ハッシュ衝突攻撃への対策）

## 備考

- `IdDict` は objectid と === による比較を使用し、C ランタイムの jl_idtable_rehash に委譲
- `WeakKeyDict` はキーが GC で回収された際に自動的にエントリを除去
- `ImmutableDict` は永続データ構造として実装（連結リスト形式）
- Dict のスロットメタデータ: 0x00=空、0x7f=削除済み、0x80以上=使用中（上位7ビットがショートハッシュ）

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

Dict の内部構造とスロット管理方式を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | dict.jl | `base/dict.jl` | Dict{K,V} 構造体の内部フィールドとスロットメタデータ方式 |

**読解のコツ**: Julia の Dict はオープンアドレス法を採用しており、`slots` 配列のメタデータバイトが3状態（空=0x00、tombstone=0x7f、使用中=0x80+ショートハッシュ上位7ビット）を持つ。この3状態を理解することが全体の理解の鍵となる。

- **28-29行目**: `maxallowedprobe` と `maxprobeshift` 定数の定義
- **65-89行目**: `Dict{K,V}` 構造体定義 - slots, keys, vals, ndel, count, age, idxfloor, maxprobe フィールド
- **122行目**: `_shorthash7` - ハッシュ上位7ビットを取得
- **127-132行目**: `hashindex` - ハッシュからインデックスとショートハッシュを計算
- **134-136行目**: `isslotempty` / `isslotfilled` / `isslotmissing` - スロット状態判定

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | dict.jl | `base/dict.jl` | Dict のコンストラクタとユーザー向けAPI |

**主要処理フロー**:
1. **76-89行目**: `Dict{K,V}()` コンストラクタ - 空のテーブルを作成
2. **90-97行目**: `Dict{K,V}(kv)` - イテラブルからの構築
3. **98-106行目**: `Dict{K,V}(ps::Pair...)` - Pairからの構築
4. **344-349行目**: `setindex!(h, v0, key0)` - キーの型変換と挿入
5. **238-260行目**: `ht_keyindex(h, key)` - キー検索（読み取り用）

#### Step 3: ハッシュテーブル操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | dict.jl | `base/dict.jl` | ht_keyindex2_shorthash!, _setindex!, rehash! の実装 |

**主要処理フロー**:
- **267-319行目**: `ht_keyindex2_shorthash!` - 書き込み用スロット検索（リハッシュ含む）
- **324-342行目**: `_setindex!` - スロットへの実際の書き込みとリハッシュ判定
- **138-192行目**: `rehash!` - テーブルリサイズと全エントリの再配置

#### Step 4: バリアント辞書型を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | iddict.jl | `base/iddict.jl` | IdDict の実装（objectid/===ベース） |
| 4-2 | weakkeydict.jl | `base/weakkeydict.jl` | WeakKeyDict の実装（弱参照キー） |

**主要処理フロー**:
- **iddict.jl 27-47行目**: `IdDict{K,V}` 構造体 - Memory{Any} による簡易ハッシュテーブル
- **iddict.jl 61-63行目**: `rehash!` - C ランタイムの `jl_idtable_rehash` に委譲

### プログラム呼び出し階層図

```
Dict{K,V}() / Dict(pairs...)
    |
    +-- setindex!(h, v, key)
    |       +-- convert(K, key), convert(V, v)
    |       +-- ht_keyindex2_shorthash!(h, key)
    |       |       +-- hashindex(key, sz) → (idx, sh)
    |       |       +-- 線形探査ループ
    |       |       +-- [充填率超過時] rehash!(h, newsz)
    |       +-- _setindex!(h, v, key, index, sh)
    |
    +-- getindex(h, key)
    |       +-- ht_keyindex(h, key)
    |       |       +-- hashindex(key, sz) → (idx, sh)
    |       |       +-- 線形探査ループ（ショートハッシュフィルタ付き）
    |       +-- h.vals[index]
    |
    +-- delete!(h, key)
    |       +-- ht_keyindex(h, key)
    |       +-- _delete!(h, index)
    |               +-- slots[index] = 0x7f (tombstone)
    |
    +-- rehash!(h, newsz)
            +-- 新しいMemory確保
            +-- 全エントリを再ハッシュして再配置
```

### データフロー図

```
[入力]                    [処理]                              [出力]

key, value        ---->  hashindex(key, sz)
                         → (index, shorthash)
                         |
                         +-- ht_keyindex2_shorthash!
                         |   slots[i] チェック + 線形探査
                         |
                         +-- _setindex!
                             slots[i] = sh                   ---->  Dict{K,V}
                             keys[i] = key                          (更新された辞書)
                             vals[i] = value

key               ---->  ht_keyindex(key)
                         → slots[i] & sh マッチング
                         → isequal(key, keys[i])             ---->  value (V型)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| dict.jl | `base/dict.jl` | ソース | Dict{K,V} のメイン実装（ハッシュテーブル、挿入・検索・削除） |
| iddict.jl | `base/iddict.jl` | ソース | IdDict{K,V} の実装（objectid/===ベース） |
| weakkeydict.jl | `base/weakkeydict.jl` | ソース | WeakKeyDict{K,V} の実装（弱参照キー、GC連携） |
| abstractdict.jl | `base/abstractdict.jl` | ソース | AbstractDict の抽象インタフェース定義 |
| hashing.jl | `base/hashing.jl` | ソース | hash 関数の定義（Dict のキーハッシュに使用） |
