# 機能設計書 47-ハッシュテーブル

## 概要

SQLiteにおける汎用ハッシュテーブルの設計書。Knuth乗算ハッシュ法を採用し、文字列キーによる高速なデータ検索を提供する。

### 本機能の処理概要

SQLiteのハッシュテーブルは、スキーマ情報（テーブル、インデックス、トリガー、外部キー）の管理に使用される汎用データ構造である。

**業務上の目的・背景**：SQLiteでは多数のデータベースオブジェクト（テーブル、インデックス等）を名前で高速に検索する必要がある。ハッシュテーブルを用いることで、O(1)に近い検索性能を実現し、大規模スキーマでも効率的なオブジェクト管理を可能にする。

**機能の利用シーン**：
- テーブル名からテーブル定義を検索（tblHash）
- インデックス名からインデックス定義を検索（idxHash）
- トリガー名からトリガー定義を検索（trigHash）
- 外部キー名から外部キー定義を検索（fkeyHash）

**主要な処理内容**：
1. 初期化：sqlite3HashInit()で空のハッシュテーブルを準備
2. 検索：sqlite3HashFind()でキーに対応するデータを取得
3. 挿入/更新：sqlite3HashInsert()でデータを追加または更新
4. 削除：sqlite3HashInsert()にNULLを渡して削除
5. クリア：sqlite3HashClear()で全エントリを削除

**関連システム・外部連携**：
- スキーマ管理（Schema構造体内のハッシュテーブル群）
- メモリアロケータ（sqlite3Malloc, sqlite3_free）

**権限による制御**：特になし（内部データ構造）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | （内部機能） | - | スキーマ管理で内部的に使用 |

## 機能種別

汎用データ構造 / ハッシュテーブル

## 入力仕様

### 入力パラメータ（sqlite3HashInsert）

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| pH | Hash* | Yes | ハッシュテーブル | NULL不可 |
| pKey | const char* | Yes | キー文字列 | NULL不可 |
| data | void* | No | 格納データ（NULLで削除） | - |

### 入力パラメータ（sqlite3HashFind）

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| pH | const Hash* | Yes | ハッシュテーブル | NULL不可 |
| pKey | const char* | Yes | キー文字列 | NULL不可 |

### 入力データソース

- SQLiteスキーマ管理からの呼び出し

## 出力仕様

### 出力データ（sqlite3HashInsert）

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 戻り値 | void* | 新規：NULL / 更新：旧データ / malloc失敗：新data |

### 出力データ（sqlite3HashFind）

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 戻り値 | void* | 見つかった：データ / 見つからない：NULL |

### 出力先

- 呼び出し元の戻り値

## 処理フロー

### 処理シーケンス

```
1. sqlite3HashInit(pNew)
   └─ first=0, count=0, htsize=0, ht=0を設定

2. sqlite3HashFind(pH, pKey)
   ├─ strHash(pKey)でハッシュ値計算
   ├─ findElementWithHash()で要素検索
   │   ├─ ht配列があればバケット内を走査
   │   └─ なければ全要素を走査
   └─ elem->dataを返却（見つからなければNULL）

3. sqlite3HashInsert(pH, pKey, data)
   ├─ findElementWithHash()で既存要素検索
   ├─ 既存あり
   │   ├─ data==NULL: removeElement()で削除
   │   └─ data!=NULL: dataを更新
   ├─ 既存なし かつ data==NULL: 何もせずNULL返却
   ├─ 既存なし かつ data!=NULL:
   │   ├─ HashElem確保
   │   ├─ count>=5 かつ count>2*htsize: rehash()
   │   └─ insertElement()で追加
   └─ 戻り値：新規=NULL, 更新=旧data, malloc失敗=新data

4. rehash(pH, new_size)
   ├─ SQLITE_MALLOC_SOFT_LIMITでサイズ制限
   ├─ 新しいht配列を確保
   ├─ 全要素を新バケットに再配置
   └─ 旧ht配列を解放
```

### フローチャート

```mermaid
flowchart TD
    A[sqlite3HashInsert] --> B[findElementWithHash]
    B --> C{既存要素あり?}
    C -->|Yes| D{data==NULL?}
    D -->|Yes| E[removeElement]
    D -->|No| F[dataを更新]
    E --> G[旧data返却]
    F --> G
    C -->|No| H{data==NULL?}
    H -->|Yes| I[NULL返却]
    H -->|No| J[HashElem確保]
    J --> K{確保成功?}
    K -->|No| L[data返却]
    K -->|Yes| M{リハッシュ必要?}
    M -->|Yes| N[rehash]
    N --> O[insertElement]
    M -->|No| O
    O --> P[NULL返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-47-01 | Knuth乗算ハッシュ | 定数0x9e3779b1を使用 | strHash()内 |
| BR-47-02 | 大文字小文字無視 | 0xDF（ASCII）でマスク | strHash()内 |
| BR-47-03 | リハッシュ条件 | count>=5 かつ count>2*htsize | 挿入時 |
| BR-47-04 | リハッシュサイズ | count*3 | rehash()呼び出し時 |
| BR-47-05 | 削除時クリア | count==0になったらHashClear | removeElement()後 |

### ハッシュテーブル構造

| フィールド | 型 | 説明 |
|-----------|-----|------|
| first | HashElem* | 全要素の双方向リストの先頭 |
| count | unsigned int | 要素数 |
| htsize | unsigned int | バケット数 |
| ht | struct _ht* | バケット配列 |

### HashElem構造

| フィールド | 型 | 説明 |
|-----------|-----|------|
| next | HashElem* | 次の要素（双方向リスト） |
| prev | HashElem* | 前の要素（双方向リスト） |
| pKey | const char* | キー文字列 |
| h | unsigned int | ハッシュ値 |
| data | void* | 格納データ |

### バケット構造（_ht）

| フィールド | 型 | 説明 |
|-----------|-----|------|
| count | unsigned int | バケット内の要素数 |
| chain | HashElem* | バケット内の最初の要素 |

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

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

本機能はデータベーステーブルを直接操作しない（メモリ内データ構造）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | メモリ不足 | HashElem確保失敗 | dataを返却（挿入失敗を通知） |
| - | メモリ不足 | rehash失敗 | リハッシュをスキップ（性能低下のみ） |

### リトライ仕様

ハッシュ操作はリトライ不要（同期処理）

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

ハッシュテーブルはトランザクションの対象外（メモリ内データ構造）

## パフォーマンス要件

- 平均検索時間：O(1)
- リハッシュは「良性malloc」として処理（失敗してもOK）
- sqlite3MallocSize()で実際に確保されたサイズを活用

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

- 特になし（内部データ構造）

## 備考

- SQLITE_EBCDICでEBCDIC対応
- nullElement静的変数で検索失敗時のNULL相当を返却
- sqlite3StrICmpで大文字小文字を無視した比較

---

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

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

### 推奨読解順序

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

ハッシュテーブルの基本構造を理解。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | hash.h | `src/hash.h` | Hash構造体、HashElem構造体、_ht構造体の定義 |

**読解のコツ**: Hash.firstは全要素の双方向リスト、Hash.htはバケット配列。要素は2つのリンク（全体リストとバケット内リスト）に属する。

#### Step 2: ハッシュ関数を理解する

Knuth乗算ハッシュの実装。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | hash.c | `src/hash.c` | strHash（55-73行目）：ハッシュ関数 |

**主要処理フロー**:
- **58-60行目**: Knuthの乗算ハッシュのコメント
- **68行目**: 0xDFマスクで大文字小文字を無視
- **70行目**: 0x9e3779b1（黄金比由来の素数）で乗算

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

初期化、クリア、検索の実装。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | hash.c | `src/hash.c` | sqlite3HashInit（23-29行目）：初期化 |
| 3-2 | hash.c | `src/hash.c` | sqlite3HashClear（35-50行目）：クリア |
| 3-3 | hash.c | `src/hash.c` | findElementWithHash（153-183行目）：検索 |
| 3-4 | hash.c | `src/hash.c` | sqlite3HashFind（222-226行目）：公開API |

**主要処理フロー**:
- **161行目**: nullElement静的変数（見つからない場合用）
- **163行目**: strHash()でハッシュ値計算
- **164-172行目**: バケットまたは全体リストから検索開始
- **176行目**: ハッシュ値とキーの両方を比較

#### Step 4: 挿入・削除を理解する

要素の追加・更新・削除の実装。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | hash.c | `src/hash.c` | insertElement（79-104行目）：要素挿入 |
| 4-2 | hash.c | `src/hash.c` | removeElement（188-216行目）：要素削除 |
| 4-3 | hash.c | `src/hash.c` | sqlite3HashInsert（242-272行目）：公開API |

**主要処理フロー**:
- **250-259行目**: 既存要素の更新または削除
- **260行目**: data==NULLで既存なしなら即リターン
- **261-262行目**: HashElem確保（失敗時はdataを返却）
- **267-268行目**: リハッシュ条件（count>=5, count>2*htsize）

#### Step 5: リハッシュを理解する

ハッシュテーブルの拡張。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | hash.c | `src/hash.c` | rehash（113-146行目）：リハッシュ |

**主要処理フロー**:
- **117-122行目**: SQLITE_MALLOC_SOFT_LIMITによるサイズ制限
- **132-134行目**: 良性malloc（失敗しても致命的でない）
- **139行目**: sqlite3MallocSize()で実サイズ取得
- **141-144行目**: 全要素を新バケットに再配置

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

```
sqlite3HashInit(pNew)
    └─ メンバ変数を0で初期化

sqlite3HashFind(pH, pKey)
    └─ findElementWithHash(pH, pKey, 0)
           ├─ strHash(pKey)
           └─ elem->data を返却

sqlite3HashInsert(pH, pKey, data)
    ├─ findElementWithHash(pH, pKey, &h)
    │      └─ strHash(pKey)
    ├─ [既存あり] removeElement() または data更新
    │      └─ sqlite3HashClear() [count==0時]
    ├─ [新規] sqlite3Malloc(HashElem)
    ├─ rehash(pH, count*3) [条件時]
    │      ├─ sqlite3BeginBenignMalloc()
    │      ├─ sqlite3Malloc(新ht配列)
    │      ├─ sqlite3MallocSize()
    │      └─ insertElement() x N
    └─ insertElement(pH, &ht[h%htsize], new_elem)

sqlite3HashClear(pH)
    ├─ sqlite3_free(pH->ht)
    └─ sqlite3_free(elem) x N
```

### データフロー図

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

キー文字列 ─────────▶ strHash() ────────────────────▶ ハッシュ値h
                         │
                         ▼
                  ┌─────────────────┐
                  │ Hash構造体       │
                  │ ・first         │──▶ HashElemリスト
                  │ ・count         │
                  │ ・htsize        │
                  │ ・ht            │──▶ バケット配列
                  └─────────────────┘
                         │
                         ▼
                  ┌─────────────────┐
                  │ findElementWithHash │
                  │ h % htsize でバケット │
                  │ ハッシュ+キー比較  │
                  └─────────────────┘
                         │
                         ▼
                  ┌─────────────────┐
                  │ HashElem         │
                  │ ・pKey          │──▶ キー文字列
                  │ ・h             │──▶ ハッシュ値
                  │ ・data          │──▶ 格納データ
                  └─────────────────┘
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| hash.c | `src/hash.c` | ソース | ハッシュテーブル実装 |
| hash.h | `src/hash.h` | ヘッダ | Hash, HashElem構造体定義 |
| sqliteInt.h | `src/sqliteInt.h` | ヘッダ | sqlite3StrICmp宣言 |
| malloc.c | `src/malloc.c` | ソース | sqlite3Malloc, sqlite3MallocSize |
