# 機能設計書 124-ハッシュマップ

## 概要

本ドキュメントは、KShootManiaにおけるハッシュマップデータ構造機能(alib_hash)の設計を記述する。キー・値ペアの連想配列をHSP3のモジュールとして提供し、キー音ライブラリ管理等で使用される。

### 本機能の処理概要

本機能は、HSP3のプログラミング環境において連想配列（ハッシュマップ）を実現するサードパーティモジュールである。オープンアドレス法によるハッシュテーブルを用いて、文字列キーに対する値の高速な格納・検索・削除を可能にする。文字列型・整数型・実数型の3種類の値型に対応している。

**業務上の目的・背景**：HSP3には連想配列のネイティブサポートがないため、キー音ライブラリ管理のようにファイル名をキーとしてオブジェクトを管理する場面では、サードパーティのハッシュマップ実装が必要となる。本モジュールにより、文字列キーを使った高速なデータアクセスが実現される。

**機能の利用シーン**：
- キー音ライブラリ管理（key_sound.as）: キー音名からKeySoundオブジェクトへのマッピング
- キー・値ペアによるデータの格納・検索・削除が必要な場面全般

**主要な処理内容**：
1. HashInitStr/HashInitInt/HashInitDouble: ハッシュマップの初期化（3種類の値型）
2. HashElem: キーに対応する値の参照・代入（マクロ経由）
3. HashAddKey: キーの追加
4. HashCheckKey: キーの存在確認
5. HashDelKey: キーの削除
6. HashGetEach: イテレーション（全キー・値の列挙）
7. HashFromFile/HashToFile: ファイルとの入出力
8. HashClear: ハッシュマップのクリア
9. HashExt: ハッシュマップの動的拡張

**関連システム・外部連携**：特になし（純粋なデータ構造モジュール）。

**権限による制御**：特になし。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 5 | ゲームプレイ画面 | 参照画面 | キー音ライブラリ管理でHashMapを使用 |

## 機能種別

データ構造（連想配列/ハッシュマップ）

## 入力仕様

### 入力パラメータ

#### HashInitStr

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| hash_name | マクロ名 | Yes | ハッシュマップ名（_info, _keys, _valuesの3配列が自動生成） | なし |
| dim_max | int | No | ハッシュ配列サイズ(デフォルト257) | 1以上 |
| dim_ext | int | No | 拡張時の増分(デフォルト64) | 1以上 |
| key_max | int | No | キー文字列の最大長(デフォルト16) | 1以上 |
| value_max | int | No | 値文字列の最大長(デフォルト16) | 1以上 |

#### HashElem(参照・代入)

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| hash_name | マクロ名 | Yes | ハッシュマップ名 | 初期化済みであること |
| key | str | Yes | キー文字列 | 空文字列は"NULL"として扱われる |

### 入力データソース

プログラム内の変数・リテラル、またはファイルからの読み込み（HashFromFile使用時）。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| HashElem戻り値 | str/int/double | キーに対応する値（初期化時の値型に依存） |
| HashAddKey戻り値 | int | 追加されたキーのインデックス（-1は追加失敗） |
| HashCheckKey戻り値 | int | 1=キーが存在する、0=存在しない |
| HashGetEach戻り値 | int | イテレータのインデックス（-1は列挙終了） |

### 出力先

呼び出し元モジュールの変数

## 処理フロー

### 処理シーケンス

```
1. ハッシュマップ初期化 (HashInitStr等)
   └─ hash_info配列(管理情報6要素)を確保
   └─ hash_keys配列(キー文字列)を確保
   └─ hash_values配列(値)を確保

2. キー追加・値設定 (HashAddKey / HashElem)
   └─ HashFunc: キー文字列からハッシュ値を計算
   └─ オープンアドレス法でスロットを探索
   └─ 空きスロットにキーを格納（衝突時は線形探索）
   └─ 配列が満杯の場合はHashExtで自動拡張

3. 値参照 (HashElem)
   └─ HashIndexF: キーのインデックスを取得
   └─ hash_valuesの対応インデックスの値を返却

4. キー削除 (HashDelKey)
   └─ 対象キーのスロットを空にする
   └─ 全キー・値を一時退避
   └─ 再ハッシュ（全データを再配置）
```

### フローチャート

```mermaid
flowchart TD
    A[HashInitStr] --> B[hash_info/keys/values配列確保]
    B --> C{操作選択}
    C -->|参照/代入| D[HashElem]
    C -->|キー追加| E[HashAddKey]
    C -->|キー削除| F[HashDelKey]
    C -->|キー確認| G[HashCheckKey]
    D --> H[HashFunc: ハッシュ値計算]
    E --> H
    F --> H
    G --> H
    H --> I[オープンアドレス法でスロット探索]
    I --> J{空きスロット?}
    J -->|Yes| K[キー格納]
    J -->|No, キー一致| L[既存スロット返却]
    J -->|No, 満杯| M[HashExt: 配列拡張]
    M --> I
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-124-01 | ハッシュ関数 | hash_value = hash_value * 137 + peek(s,cnt) の累積乗算加算 | HashFunc呼び出し時 |
| BR-124-02 | 衝突解決 | オープンアドレス法(線形探索: h = (h+1) % hash_max) | キー追加・検索時 |
| BR-124-03 | 空キー禁止 | 空文字列""は"NULL"として扱われる | キー操作全般 |
| BR-124-04 | 自動拡張 | 配列が満杯の場合、dim_ext分だけ自動拡張 | HashAddKey失敗時 |
| BR-124-05 | 削除時再ハッシュ | キー削除後、全データを再配置する | HashDelKey実行時 |
| BR-124-06 | デフォルトサイズ | dim_max=257, dim_ext=64, key_max=16, value_max=16 | 初期化時省略時 |

### 計算ロジック

ハッシュ関数: `hash_value = abs(hash_value % hash_max)` ただし `hash_value` は各文字のバイト値を `137 * hash_value + byte` で累積。

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

該当なし。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| -1 | キー追加失敗 | 配列が満杯でキー追加不可 | HashExtで自動拡張が呼ばれる |
| - | キー未存在 | HashCheckKeyで0が返却 | 呼び出し元で判定して処理分岐 |

### リトライ仕様

HashAddKeyが-1を返した場合、HashExtが自動的に配列を拡張して再試行する（HashIndexF内で実装）。

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

該当なし。

## パフォーマンス要件

- 平均的なキー検索・追加: O(1)（ハッシュ衝突がない場合）
- 最悪ケース: O(n)（全スロットが衝突する場合）
- キー削除: O(n)（再ハッシュのため全データを再配置）

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

特になし。メモリ内のデータ構造であり、外部からの直接アクセスはない。

## 備考

- Version 0.04 (2008年9月25日)が最新版
- 著者: 綾織友恵 (フリーソフトウェア)
- ハッシュマップ名はHSP3のマクロとして定義する必要がある（例: `#define ctype hash(%1) HashElem( hash, %1 )`）
- 1つのハッシュマップに対して3つの配列(`_info`, `_keys`, `_values`)が自動生成される
- kshootmania.hsp(176行目)とkshooteditor.hsp(29行目)の両方でインクルードされている
- key_sound.as(1行目)でもインクルードされ、キー音ライブラリ管理に使用されている

---

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

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

### 推奨読解順序

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

ハッシュマップの内部構造（3配列構成と管理情報）を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | alib_hash.as | `third_party/alib_hash.as` | HASH_INFO定数の定義(153-159行目): DIM_MAX, DIM_EXT, KEY_MAX, VALUE_MAX, NUM_KEYS, ITER |
| 1-2 | alib_hash.as | `third_party/alib_hash.as` | デフォルト定数(161-164行目): HASH_DEFAULT_DIM_MAX=257等 |

**読解のコツ**: HSP3の`#enum global`は列挙型定数の定義。ハッシュマップ名`hash`に対して`hash_info`(管理情報), `hash_keys`(キー配列), `hash_values`(値配列)の3配列が内部的に使用される。マクロ展開で`%1_info`, `%1_keys`, `%1_values`に変換される。

#### Step 2: 初期化処理を理解する

ハッシュマップの初期化と3種類の値型の違いを理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | alib_hash.as | `third_party/alib_hash.as` | HashInitS(213-223行目): 文字列型ハッシュマップ初期化 |
| 2-2 | alib_hash.as | `third_party/alib_hash.as` | HashInitI(228-237行目): 整数型ハッシュマップ初期化 |
| 2-3 | alib_hash.as | `third_party/alib_hash.as` | マクロ定義(255-257行目): HashInitStr/Int/Doubleの展開 |

**主要処理フロー**:
1. **214行目**: `dim hash_info, HASH_INFO_MAX` - 管理情報配列の確保
2. **215-219行目**: 管理情報(DIM_MAX, DIM_EXT等)の設定、デフォルト値の適用
3. **221行目**: `sdim hash_keys` - キー配列の確保(文字列型)
4. **222行目**: `sdim hash_values` - 値配列の確保(文字列型の場合)

#### Step 3: ハッシュ関数と検索を理解する

ハッシュ値計算とオープンアドレス法による検索処理を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | alib_hash.as | `third_party/alib_hash.as` | HashFunc(143-148行目): ハッシュ関数 |
| 3-2 | alib_hash.as | `third_party/alib_hash.as` | HashAddKeyF(306-317行目): キー追加(オープンアドレス法) |
| 3-3 | alib_hash.as | `third_party/alib_hash.as` | HashIndexF(389-392行目): インデックス取得(自動拡張付き) |

**主要処理フロー**:
- **146行目**: `hash_value = hash_value * 137 + peek(s,cnt)` - ハッシュ値の計算
- **147行目**: `return abs(hash_value \ hash_max)` - モジュロ演算でインデックスを算出
- **311行目**: `repeat hash_max` - 線形探索によるスロット検索開始
- **312行目**: 空きスロット発見時にキーを格納し、NUM_KEYSをインクリメント
- **314行目**: `h = (h+1) \ hash_max` - 衝突時の次スロットへの移動

#### Step 4: 使用例を理解する

実際の使用箇所を確認する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | key_sound.as | `src/audio/key_sound.as` | HashInitInt(18行目), HashCheckKey(58行目), HashClear(19,107行目)の使用 |

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

```
呼び出し元 (key_sound.as等)
    |
    +-- HashInitStr/Int/Double (初期化)
    |       |
    |       +-- HashInitS/I/D (内部命令)
    |               +-- sdim/dim/ddim (配列確保)
    |
    +-- HashElem (値の参照・代入) [マクロ]
    |       |
    |       +-- HashIndexF
    |               |
    |               +-- HashAddKeyF
    |               |       +-- HashFunc (ハッシュ値計算)
    |               |
    |               +-- HashExtF (満杯時の拡張)
    |
    +-- HashCheckKey (キー存在確認) [マクロ]
    |       |
    |       +-- HashCheckKeyF
    |               +-- HashFunc
    |
    +-- HashDelKey (キー削除) [マクロ]
    |       |
    |       +-- HashDelKeyF
    |               +-- 再ハッシュ(全データ再配置)
    |
    +-- HashClear (クリア) [マクロ]
            |
            +-- HashClearF
                    +-- HashInitS/I/D (再初期化)
```

### データフロー図

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

キー文字列 + 値 ---------> HashElem(代入) ----------------> hash_values配列に格納
                               |
                               +-- HashFunc: ハッシュ値計算
                               +-- HashAddKeyF: スロット確保
                               +-- hash_keys配列にキー格納

キー文字列 ---------------> HashElem(参照) ----------------> 対応する値を返却
                               |
                               +-- HashFunc: ハッシュ値計算
                               +-- hash_values配列から値取得

キー文字列 ---------------> HashCheckKeyF -----------------> 1(存在) / 0(不存在)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| alib_hash.as | `third_party/alib_hash.as` | ソース | ハッシュマップモジュール本体 |
| key_sound.as | `src/audio/key_sound.as` | ソース | ハッシュマップの主要な使用箇所（キー音ライブラリ管理） |
| kshootmania.hsp | `kshootmania.hsp` | ソース | alib_hash.asのインクルード元(176行目) |
| kshooteditor.hsp | `kshooteditor.hsp` | ソース | alib_hash.asのインクルード元(29行目) |
