# 機能設計書: Hashtable

## 1. 機能概要

### 1.1 機能名
Hashtable（ハッシュテーブル）

### 1.2 機能ID
No.21

### 1.3 機能分類
System.Collections - コレクション

### 1.4 概要説明
Hashtableは、キーのハッシュコードに基づいて編成されるキー/値ペアのコレクションを表す。.NET FrameworkのHashtableクラスをVB6で実装したもので、高速な検索、追加、削除操作を提供する。

### 1.5 主な用途
- キーと値のペアを効率的に格納・検索する
- 高速なルックアップが必要なシナリオでの利用
- 重複キーの検出と防止
- 辞書型データ構造の実装

---

## 2. 機能詳細

### 2.1 提供機能一覧

| No | 機能名 | 説明 |
|----|--------|------|
| 1 | Add | 指定したキーと値を持つ要素を追加 |
| 2 | Clear | すべての要素を削除 |
| 3 | Clone | 浅いコピーを作成 |
| 4 | Contains | 指定したキーが存在するか判定 |
| 5 | ContainsKey | 指定したキーが存在するか判定 |
| 6 | ContainsValue | 指定した値が存在するか判定 |
| 7 | CopyTo | 要素を配列にコピー |
| 8 | Item | キーに関連付けられた値を取得/設定 |
| 9 | Keys | キーのコレクションを取得 |
| 10 | Values | 値のコレクションを取得 |
| 11 | Remove | 指定したキーの要素を削除 |
| 12 | Clean | 削除済みバケットをクリーンアップ |
| 13 | GetEnumerator | 列挙子を取得 |

### 2.2 処理フロー

#### 2.2.1 要素追加フロー（Add/Item設定）
```
1. LoadSize超過チェック
   ↓ 超過時
2. Expand（容量拡張）
   ↓
3. InitHashCode（ハッシュコード計算）
   ↓
4. バケット検索
   ↓ 空きバケット発見
5. キー/値格納
   ↓
6. Count増加、Version更新
```

#### 2.2.2 要素検索フロー（Item取得）
```
1. InitHashCode（ハッシュコード計算）
   ↓
2. バケット検索開始
   ↓
3. ハッシュコード一致チェック
   ↓ 一致
4. キー比較（IEqualityComparer.Equals）
   ↓ 一致
5. 値を返却
```

### 2.3 データ構造

#### 2.3.1 HashBucket構造
```vb
' バケット構造（推定）
Type HashBucket
    Key As Variant        ' キー
    Value As Variant      ' 値
    HashCode As Long      ' ハッシュコード
    State As Long         ' 状態（Empty=0, Occupied=1, Deleted=2）
End Type
```

#### 2.3.2 クラスメンバ変数
```vb
Private mLoadFactor As Single      ' 負荷係数
Private mLoadSize As Long          ' 負荷サイズ閾値
Private mCount As Long             ' 要素数
Private mBuckets() As HashBucket   ' バケット配列
Private mCapacity As Long          ' 容量
Private mVersion As Long           ' バージョン（変更検出用）
Private mKeyComparer As IEqualityComparer  ' キー比較オブジェクト
```

### 2.4 アルゴリズム詳細

#### 2.4.1 ハッシュアルゴリズム
オープンアドレス法（ダブルハッシング）を採用：
- 一次ハッシュ: `Index = HashCode Mod Capacity`
- 二次ハッシュ: `Step = 1 + (((HashCode \ 32) + 1) Mod (Capacity - 1))`
- 衝突解決: `Index = (Index + Step) Mod Capacity`

#### 2.4.2 負荷係数管理
```vb
' デフォルト負荷係数
Private Const DefaultLoadFactor As Single = 1!
' 実効負荷係数 = LoadFactor * 0.72
mLoadFactor = LoadFactor * 0.72!
mLoadSize = mCapacity * mLoadFactor
```

### 2.5 実装インターフェース

| インターフェース | 説明 |
|------------------|------|
| IObject | 基本オブジェクト機能（Equals, GetHashCode, ToString） |
| IDictionary | 辞書型コレクション機能 |
| ICollection | コレクション基本機能 |
| IEnumerable | 列挙機能 |
| ICloneable | 複製機能 |
| IVersionable | バージョン管理機能 |

---

## 3. インターフェース仕様

### 3.1 パブリックAPI

#### 3.1.1 Add メソッド
```vb
Public Sub Add(ByRef Key As Variant, ByRef Value As Variant)
```
**パラメータ**:
- Key: 追加する要素のキー
- Value: 追加する要素の値

**例外**:
- ArgumentException: キーが既に存在する場合

#### 3.1.2 Item プロパティ
```vb
Public Property Get Item(ByRef Key As Variant) As Variant
Public Property Let Item(ByRef Key As Variant, ByRef Value As Variant)
Public Property Set Item(ByRef Key As Variant, ByRef Value As Variant)
```
**パラメータ**:
- Key: 取得/設定する要素のキー

**戻り値**: 指定したキーに関連付けられた値、キーが存在しない場合はEmpty

#### 3.1.3 Remove メソッド
```vb
Public Sub Remove(ByRef Key As Variant)
```
**パラメータ**:
- Key: 削除する要素のキー

**備考**: キーが存在しない場合は何もしない

#### 3.1.4 ContainsKey メソッド
```vb
Public Function ContainsKey(ByRef Key As Variant) As Boolean
```
**戻り値**: キーが存在すればTrue、存在しなければFalse

#### 3.1.5 ContainsValue メソッド
```vb
Public Function ContainsValue(ByRef Value As Variant) As Boolean
```
**戻り値**: 値が存在すればTrue、存在しなければFalse

**備考**: 線形探索のため、O(n)の計算量

---

## 4. 内部処理詳細

### 4.1 GetKeyIndex関数
キーのインデックスを検索する内部関数。

```vb
Private Function GetKeyIndex(ByRef Key As Variant) As Long
    ' ハッシュコード初期化
    HashCode = InitHashCode(Key, Step, Index)
    FirstIndex = Index

    Do
        Select Case mBuckets(Index).State
            Case EmptyState
                GetKeyIndex = -1
                Exit Function
            Case OccupiedState
                If mBuckets(Index).HashCode = HashCode Then
                    If mKeyComparer.Equals(Key, mBuckets(Index).Key) Then
                        GetKeyIndex = Index
                        Exit Function
                    End If
                End If
        End Select
        Index = (Index + Step) Mod mCapacity
    Loop While Index <> FirstIndex

    GetKeyIndex = -1
End Function
```
**処理概要**（482-511行目）:
1. ハッシュコードを計算
2. 計算されたインデックスからバケット探索開始
3. EmptyStateで見つからない場合は-1を返却
4. OccupiedStateでハッシュコードとキーが一致すればインデックス返却
5. DeletedStateはスキップして継続探索

### 4.2 InsertItem サブルーチン
要素を挿入する内部サブルーチン。

```vb
Private Sub InsertItem(ByRef Key As Variant, ByRef Value As Variant, _
                       ByVal Adding As Boolean, ByVal Steal As Boolean)
```
**処理概要**（519-598行目）:
1. Count > LoadSizeの場合、Expand実行
2. ハッシュコードを計算し探索開始
3. 空きバケット（EmptyまたはDeleted）を記録
4. 重複キーチェック（Addingモード時）
5. 見つかった空きバケットにキー/値を格納
6. Count増加、Version更新

### 4.3 ReinsertItems サブルーチン
バケット配列を再構築する内部サブルーチン。

**処理概要**（464-480行目）:
1. 現在のバケット配列を退避
2. 新しい容量でバケット配列を再作成
3. 占有状態のバケットのみを再挿入

---

## 5. 関連コンポーネント

### 5.1 依存クラス

| クラス名 | 用途 |
|----------|------|
| IEqualityComparer | キーの等価比較とハッシュコード計算 |
| EqualityComparer | デフォルトの等価比較実装 |
| HashtableEnumerator | ハッシュテーブル専用の列挙子 |
| HashtableKeyCollection | キーコレクションのビュー |
| HashtableValueCollection | 値コレクションのビュー |
| DictionaryEntry | キー/値ペアの表現 |

### 5.2 シリアライゼーション
PropertyBagを使用した永続化をサポート:
- Count, Comparer, Key/Value ペアを保存
- Empty/Nothing値の特別処理を実装

---

## 6. エラー処理

### 6.1 例外一覧

| 例外 | 発生条件 |
|------|----------|
| ArgumentException | 重複キーの追加時 |
| ArgumentNullException | 配列がNullの場合 |
| ArgumentOutOfRangeException | インデックスが範囲外の場合 |
| InvalidOperationException | 挿入失敗時（内部エラー） |

### 6.2 エラーメッセージ
```vb
' 重複キーエラー
Argument_AddingDuplicate_Key = "重複キー '{0}' を追加しようとしました"
```

---

## 7. パフォーマンス考慮

### 7.1 計算量

| 操作 | 平均 | 最悪 |
|------|------|------|
| Add | O(1) | O(n) |
| Remove | O(1) | O(n) |
| Item取得 | O(1) | O(n) |
| ContainsKey | O(1) | O(n) |
| ContainsValue | O(n) | O(n) |

### 7.2 推奨事項
- 大量の削除後はCleanメソッドで最適化
- 事前に容量がわかる場合は初期容量を指定
- カスタムオブジェクトをキーにする場合はIEqualityComparerを実装

---

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

### 8.1 推奨読解順序

1. **データ構造の理解**
   - `Hashtable.cls` 56-74行目: メンバ変数定義
   - HashBucket構造（別ファイル）

2. **初期化処理**
   - `Class_Initialize` (407-409行目): デフォルト初期化
   - `Init` (415-439行目): パラメータ付き初期化

3. **基本操作**
   - `Add` (84-86行目): 要素追加（InsertItemを呼出）
   - `Item Get` (258-265行目): 要素取得
   - `Remove` (333-357行目): 要素削除

4. **内部アルゴリズム**
   - `InitHashCode` (513-517行目): ハッシュ計算
   - `GetKeyIndex` (482-511行目): キー検索
   - `InsertItem` (519-598行目): 挿入ロジック

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

```
Hashtable.Add
  └── InsertItem
        ├── Expand (容量超過時)
        │     └── ReinsertItems
        │           └── InsertItem (再帰)
        └── InitHashCode
              └── IEqualityComparer.GetHashCode

Hashtable.Item(Get)
  └── GetKeyIndex
        ├── InitHashCode
        └── IEqualityComparer.Equals

Hashtable.Remove
  └── GetKeyIndex
```

### 8.3 データフロー図

```
[キー/値] ──→ [InitHashCode] ──→ [インデックス計算]
                  │                      │
                  ↓                      ↓
          [IEqualityComparer]     [バケット配列]
                  │                      │
                  └──────→ [衝突解決] ←──┘
                               │
                               ↓
                         [格納/取得]
```

### 8.4 関連ファイル一覧

| パス | 種別 | 役割 |
|------|------|------|
| Source/CorLib/System.Collections/Hashtable.cls | クラス | メインクラス |
| Source/CorLib/System.Collections/HashtableEnumerator.cls | クラス | 列挙子 |
| Source/CorLib/System.Collections/HashtableKeyCollection.cls | クラス | キーコレクション |
| Source/CorLib/System.Collections/HashtableValueCollection.cls | クラス | 値コレクション |
| Source/CorLib/System.Collections/EqualityComparer.cls | クラス | 等価比較 |
| Source/CorLib/System.Collections/IEqualityComparer.cls | インターフェース | 比較契約 |

### 8.5 読解のコツ
- VB6のPropertyプロシージャ（Get/Let/Set）に注意
- `Attribute VB_UserMemId = 0` はデフォルトプロパティを示す
- `Implements` によるインターフェース実装パターンを理解する
- `mVersion` はFor Each中の変更検出に使用される

---

## 9. 変更履歴

| 日付 | バージョン | 変更内容 |
|------|------------|----------|
| 2015 | 1.0 | 初期実装（Kelly Ethridge） |

---

## 10. 備考

- .NET FrameworkのSystem.Collections.Hashtableと互換性のあるAPI設計
- VB6のCollectionとは異なり、キーの重複を許可しない
- シリアライゼーション時のEmpty/Nothing値の特別処理に注意
