# 機能設計書 14-Hashクラス

## 概要

本ドキュメントは、mrubyにおけるHashクラスの機能設計を記述する。Hashクラスはハッシュテーブル（連想配列）の生成・検索・追加・削除・イテレーション等を提供する組み込み型クラスである。

### 本機能の処理概要

Hashクラスは、キーと値のペアを管理する連想配列を実装する。ISO 15.2.13に準拠し、内部的にはAR（Array Table）とHT（Hash Table）の2段階構造を採用している。要素数が16以下の場合はAR（線形探索）を使用し、16を超えるとHT（ハッシュテーブル+オープンアドレス法）に自動的に切り替わる。挿入順序を保持するEntry Array（EA）を持ち、Ruby準拠の順序付きハッシュを実現している。Enumerableモジュールをインクルードしている。

**業務上の目的・背景**：連想配列は設定値の管理、データのマッピング、カウンター、キャッシュなど多用途に使用されるデータ構造である。小さなハッシュ（16要素以下）では線形探索の方がハッシュ計算のオーバーヘッドを含めた実効性能が良いため、AR方式を採用している。大きなハッシュではO(1)のハッシュテーブル方式に切り替えることで、スケーラビリティを確保している。

**機能の利用シーン**：設定パラメータの管理、オプション引数の受け渡し、キーワード引数、データのグルーピング、カウンティング、キャッシュなど。mrubyのキーワード引数はHash経由で実装される。

**主要な処理内容**：
1. ハッシュオブジェクトの生成とメモリ管理（AR/HT切り替え）
2. キー・値ペアの追加（[]=, store）
3. 値の取得（[], fetch）
4. キー・値ペアの削除（delete, clear）
5. キーの存在確認（has_key?, key?, include?）
6. イテレーション（each, each_key, each_value）
7. キー・値の一覧取得（keys, values）
8. ハッシュの結合（merge, merge!）
9. フィルタリング（select, reject, select!, reject!）
10. デフォルト値の管理（default, default=）

**関連システム・外部連携**：Enumerableモジュールをインクルードしており、map/select等の列挙メソッドが利用可能。キーのhashメソッドとeql?メソッドに依存する。

**権限による制御**：freezeされたハッシュへの破壊的操作はFrozenErrorを発生させる。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | CLIベースのランタイム機能のため関連画面なし |

## 機能種別

データ操作 / コレクション管理 / 連想配列

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| key | Object | Yes | ハッシュキー | hashメソッドとeql?メソッドが必要 |
| value | Object | No | ハッシュ値 | なし |
| default | Object | No | デフォルト値 | なし |
| block | Proc | No | デフォルトプロック/イテレーション用 | なし |

### 入力データソース

リテラル記法（`{}`）、C APIからの生成、キーワード引数。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 値 | Object | [], fetch等の値取得結果 |
| 配列 | Array | keys, values, select等の結果 |
| ハッシュ | Hash | merge, reject等の新ハッシュ |
| 真偽値 | Boolean | has_key?, empty?等の判定結果 |
| 整数 | Integer | size, length の結果 |

### 出力先

呼び出し元への戻り値として返却。

## 処理フロー

### 処理シーケンス

```
1. ハッシュオブジェクトの生成
   └─ RHash構造体の割り当て
   └─ AR方式で初期化（EA配列確保）
2. キー・値の追加
   └─ AR方式の場合: EA内を線形探索
   └─ HT方式の場合: IB（Index Buckets）でハッシュ検索
   └─ サイズが16を超えた場合: ARからHTへ変換
3. キー・値の取得
   └─ AR方式: EA内を線形走査
   └─ HT方式: ハッシュ値からIB位置を計算し、オープンアドレス法で探索
4. イテレーション
   └─ EA（Entry Array）を挿入順で走査
```

### フローチャート

```mermaid
flowchart TD
    A[ハッシュ操作要求] --> B{操作種別?}
    B -->|追加| C{現在AR方式?}
    C -->|Yes| D{size > 16?}
    D -->|Yes| E[HTに変換]
    D -->|No| F[EA内に追加]
    E --> G[IBにインデックス追加]
    C -->|No| G
    B -->|検索| H{AR方式?}
    H -->|Yes| I[EA線形探索]
    H -->|No| J[IBハッシュ検索]
    B -->|イテレーション| K[EA順次走査]
    F --> L[結果返却]
    G --> L
    I --> L
    J --> L
    K --> L
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-14-01 | AR/HT切り替え | size <= 16はAR（線形探索）、16超はHT（ハッシュテーブル） | 要素追加時 |
| BR-14-02 | 挿入順保持 | Entry Arrayにより挿入順序を保持 | 常時 |
| BR-14-03 | オープンアドレス法 | HT方式の衝突解決はオープンアドレス法 | HT方式時 |
| BR-14-04 | AR最大容量 | AR_MAX_SIZE = 16 | AR方式時 |
| BR-14-05 | ARデフォルト容量 | AR_DEFAULT_CAPA = 4 | ハッシュ生成時 |
| BR-14-06 | Enumerable包含 | HashはEnumerableをインクルードする | 常時 |

### 計算ロジック

- **IB初期ビット数**: ib_upper_bound_for(32)がAR_MAX_SIZE以下なら6ビット、そうでなければ5または4ビット
- **最大容量**: EA_MAX_CAPA = min(IB_MAX_CAPA - 2, MRB_INT_MAX)

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

該当なし（インメモリ操作のみ）。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | FrozenError | frozenなハッシュへの破壊的操作 | 非frozenハッシュを使用する |
| - | TypeError | mergeに非Hash型を渡した場合 | Hash型を渡す |
| - | KeyError | fetch でキーが見つからずデフォルトもない場合 | キーを確認する/デフォルト値を指定する |

### リトライ仕様

該当なし。

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

該当なし。

## パフォーマンス要件

- AR方式（16要素以下）: 検索O(n)、挿入O(n)だが、小さいnで実効性能が良い
- HT方式（17要素以上）: 検索O(1)平均、挿入O(1)平均
- AR→HT変換はO(n)

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

- ハッシュ値の衝突攻撃に対する直接的な対策は限定的

## 備考

- ISO 15.2.13に準拠
- deconstruct_keys メソッドによるパターンマッチングサポート
- 32ビット/64ビット環境で構造体レイアウトが異なる（MRB_64BIT/MRB_32BIT）

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | hash.h | `include/mruby/hash.h` | RHash構造体の定義、AR/HTフラグ管理 |
| 1-2 | hash.c | `src/hash.c` | hash_entry, hash_table構造体の内部定義（78-90行目） |

**読解のコツ**: hash.cの冒頭コメント（19-57行目）にGlossaryがあり、EA/AR/IB/HT等の用語が定義されている。まずこのGlossaryを読むことで全体構造を把握できる。RHash構造体のflagsフィールドのビット割り当て（MRB_HASH_HT, MRB_HASH_DEFAULT等）を理解することが重要。

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | hash.c | `src/hash.c` | `mrb_init_hash()`関数（2346行目）でクラス定義 |

**主要処理フロー**:
1. **2346-2354行目**: Hashクラス定義、ROMメソッドテーブル初期化

#### Step 3: 内部アルゴリズムを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | hash.c | `src/hash.c` | AR/HT方式の切り替えロジック、IBのビット操作 |

**主要処理フロー**:
- **59-73行目**: 定数定義（AR_MAX_SIZE=16, AR_DEFAULT_CAPA=4, IB_TYPE_BIT=32等）
- **78-90行目**: hash_entry, hash_table構造体（EA+IB配列）
- **92-100行目**: index_buckets_iter構造体（IBイテレーション用）

#### Step 4: Rubyレベルメソッドを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | hash.rb | `mrblib/hash.rb` | each, delete, merge, select, reject等のRuby実装 |

**主要処理フロー**:
- **10行目**: `include Enumerable` 宣言
- **26-31行目**: `delete` - ブロック付きdelete
- **54-66行目**: `each` - keys/valuesベースのイテレーション
- **87-92行目**: `each_key` - キーのイテレーション
- **112-117行目**: `each_value` - 値のイテレーション
- **142-155行目**: `merge` - ハッシュの結合
- **167-181行目**: `reject!` - 条件に一致する要素の破壊的削除
- **220-234行目**: `select!` - 条件に一致しない要素の破壊的削除
- **273-275行目**: `deconstruct_keys` - パターンマッチング対応

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

```
mrb_init_hash()
    |
    +-- mrb_define_class_id(Hash)
    +-- MRB_MT_INIT_ROM(hash_rom_entries)
            |
            +-- C実装メソッド群（[]=, [], keys, values等）
            |       |
            |       +-- AR方式: EA線形探索
            |       +-- HT方式: IB + オープンアドレス法
            |
            +-- mrblib/hash.rb
                    |
                    +-- include Enumerable
                    +-- each, delete, merge, select, reject等
```

### データフロー図

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

キー/値ペア         AR方式 (size<=16)                   値 / 配列
             ---->   EA線形探索/追加              ---->  / ハッシュ
                       |
                     HT方式 (size>16)
                       IB→EA インデックス解決
                       オープンアドレス法
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| hash.c | `src/hash.c` | ソース（C） | Hashクラスの主要実装（2355行） |
| hash.rb | `mrblib/hash.rb` | ソース（Ruby） | each, delete, merge等のRuby実装 |
| hash.h | `include/mruby/hash.h` | ヘッダ | RHash構造体とC APIの宣言 |
| enum.rb | `mrblib/enum.rb` | ソース（Ruby） | Enumerableモジュール（Hashがインクルード） |
