# 機能設計書 39-tables

## 概要

本ドキュメントは、Nimプログラミング言語の汎用ハッシュテーブルモジュールである`tables`モジュールの機能設計を記載する。tablesモジュールはキーから値へのマッピングを行う効率的なハッシュテーブル（辞書）のバリエーションを提供する。

### 本機能の処理概要

tablesモジュールは3種類のハッシュテーブルを提供する：通常のTable、挿入順序を保持するOrderedTable、出現回数をカウントするCountTable。それぞれに値セマンティクス版とref版（TableRef等）がある。

**業務上の目的・背景**：キーバリューストアはほぼすべてのプログラムで必要とされる基本的なデータ構造である。tablesモジュールは、任意のハッシュ可能な型をキーとして使用できる汎用的なハッシュテーブルを提供し、高速な検索・挿入・削除操作を実現する。

**機能の利用シーン**：
- 設定情報の管理
- キャッシュの実装
- カウンタ・集計処理
- グラフのエッジリスト
- オブジェクトの識別子マッピング

**主要な処理内容**：
1. Table[A, B]型（通常のハッシュテーブル）
2. OrderedTable[A, B]型（挿入順序保持）
3. CountTable[A]型（出現回数カウント）
4. 参照版（TableRef, OrderedTableRef, CountTableRef）
5. テーブル操作（initTable, toTable, [], []=, del, hasKey, contains, getOrDefault, mgetOrPut）
6. イテレータ（pairs, keys, values, mpairs, mvalues）
7. ハッシュ関数のカスタマイズ対応

**関連システム・外部連携**：hashesモジュールのHash型とhash関数を使用。

**権限による制御**：権限による制御は存在しない。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面には関連しない（ライブラリモジュール） |

## 機能種別

データ構造 / ハッシュテーブル / コレクション

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| A | type | Yes | キーの型（hash関数が必要） | ハッシュ可能 |
| B | type | Yes | 値の型 | なし |
| key | A | Yes | キー | なし |
| val | B | Yes | 値 | なし |
| initialSize | int | No | 初期サイズ（デフォルト64） | 正の整数 |

### 入力データソース

プログラム内のデータ。キー型にはhash関数と==演算子が必要。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Table[A, B] | object | ハッシュテーブル |
| value | B | キーに対応する値 |
| exists | bool | キーの存在確認結果 |
| count | int | 要素数 |

### 出力先

戻り値として呼び出し元に返される。

## 処理フロー

### 処理シーケンス

```
1. テーブルの作成
   └─ initTable/toTableで初期化
2. ハッシュ計算
   └─ キーのhash関数を呼び出し
3. スロット検索
   └─ 開放アドレス法（線形探査）
4. 操作実行
   └─ 挿入、検索、削除
5. リハッシュ（必要時）
   └─ 負荷率に応じてテーブル拡張
```

### フローチャート

```mermaid
flowchart TD
    A[操作要求] --> B{操作種別}
    B -->|挿入| C[hash計算]
    B -->|検索| D[rawGet呼び出し]
    B -->|削除| E[del呼び出し]
    C --> F[スロット検索]
    F --> G{空きスロット?}
    G -->|Yes| H[値を挿入]
    G -->|No| I[次のスロットへ]
    I --> G
    H --> J{リハッシュ必要?}
    J -->|Yes| K[テーブル拡張]
    J -->|No| L[完了]
    K --> L
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 値セマンティクス | =演算子はテーブルをコピー | Table, OrderedTable, CountTable |
| BR-02 | refセマンティクス | 参照を共有 | TableRef, OrderedTableRef, CountTableRef |
| BR-03 | ハッシュ要件 | キー型にはhash関数と==演算子が必要 | すべてのテーブル |
| BR-04 | 初期化不要 | Nim v0.20以降はデフォルトで初期化済み | initTable/initOrderedTable |

### 計算ロジック

ハッシュテーブルの実装:
- 開放アドレス法（線形探査）
- 負荷率に応じた自動リハッシュ
- ハッシュコードをスロットに保存（比較の高速化）

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

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

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | データベース操作なし |

### テーブル別操作詳細

データベース操作は行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| KeyError | Exception | 存在しないキーへのアクセス | hasKeyでチェック、getOrDefault使用 |

### リトライ仕様

リトライは不要。事前チェックで対処。

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

トランザクション管理は不要。

## パフォーマンス要件

- 検索、挿入、削除: 平均O(1)
- リハッシュ: O(n)（負荷率に応じて発生）
- OrderedTableの挿入順序イテレーション: O(n)

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

- ハッシュ衝突攻撃に対する耐性は標準的なレベル
- ユーザー入力をキーとして大量に挿入する場合は注意が必要

## 備考

文字列から文字列へのマッピングのみが必要な場合はstrtabsモジュールの使用も検討すること。

---

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

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

### 推奨読解順序

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

Table型の定義を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | tables.nim | `lib/pure/collections/tables.nim` | KeyValuePair, Table型（203-218行目） |

**読解のコツ**: Table[A, B]はdata（KeyValuePairSeq）とcounter（要素数）を持つ。KeyValuePairはhcode、key、valのタプル。

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

モジュール冒頭のドキュメントを確認。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | tables.nim | `lib/pure/collections/tables.nim` | モジュールドキュメント（10-193行目） |

**主要処理フロー**:
1. **10-24行目**: Table, OrderedTable, CountTableの概要
2. **19-28行目**: 値セマンティクスの説明
3. **132-155行目**: カスタムhash関数の必要性

#### Step 3: 基本操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | tables.nim | `lib/pure/collections/tables.nim` | initTable, toTable（268-314行目） |
| 3-2 | tables.nim | `lib/pure/collections/tables.nim` | [], []=（284-298行目, 316-353行目） |
| 3-3 | tables.nim | `lib/pure/collections/tables.nim` | hasKey, contains（355-381行目） |

**主要処理フロー**:
- **268-282行目**: initTable - 空のテーブルを作成
- **284-298行目**: []=演算子 - キーと値のペアを挿入
- **316-353行目**: []演算子 - キーに対応する値を取得
- **355-371行目**: hasKey - キーの存在確認

#### Step 4: ヘルパー関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | tables.nim | `lib/pure/collections/tables.nim` | enlarge（246-259行目） |
| 4-2 | tables.nim | `lib/pure/collections/tables.nim` | rawGet（tableimpl内） |

**主要処理フロー**:
- **246-259行目**: enlarge - テーブルの拡張（リハッシュ）
- **tableimpl**: rawGet - キー検索の実装

#### Step 5: hasKeyOrPut, mgetOrPutを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | tables.nim | `lib/pure/collections/tables.nim` | hasKeyOrPut（383-399行目） |

**主要処理フロー**:
- **383-399行目**: hasKeyOrPut - キーがなければ挿入

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

```
tables.nim (メインモジュール)
    │
    ├─ Table[A, B]
    │      ├─ initTable / toTable
    │      ├─ [] / []= / del
    │      ├─ hasKey / contains
    │      ├─ getOrDefault / mgetOrPut
    │      └─ pairs / keys / values (イテレータ)
    │
    ├─ OrderedTable[A, B]
    │      └─ 挿入順序を保持するバリアント
    │
    ├─ CountTable[A]
    │      └─ 出現回数をカウントするバリアント
    │
    └─ include tableimpl
           └─ rawGet / rawInsert / putImpl 等
```

### データフロー図

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

{1:"one", 2:"two"} ───▶  toTable              ───▶  Table[int,string]
                         (テーブル構築)

t[3] = "three"    ───▶  []=演算子            ───▶  テーブル更新
                         (hash→検索→挿入)

t[1]              ───▶  []演算子             ───▶  "one"
                         (hash→検索→取得)

t.hasKey(4)       ───▶  hasKey               ───▶  false
                         (hash→検索)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| tables.nim | `lib/pure/collections/tables.nim` | ソース | メインモジュール、Table型、主要操作 |
| tableimpl.nim | `lib/pure/collections/tableimpl.nim` | インクルード | rawGet, rawInsert等の実装 |
| hashes.nim | `lib/pure/hashes.nim` | ソース | Hash型、hash関数 |
| math.nim | `lib/pure/math.nim` | ソース | 数学関数（テーブルサイズ計算） |
| algorithm.nim | `lib/pure/algorithm.nim` | ソース | アルゴリズム（ソート等） |
