# 機能設計書 91-hashes（汎用ハッシュ関数）

## 概要

本ドキュメントは、Nim標準ライブラリの`hashes`モジュールの機能設計を記述する。このモジュールは、様々なNimデータ型に対する効率的なハッシュ値計算機能を提供する。

### 本機能の処理概要

hashesモジュールは、ハッシュテーブル（tables、sets等）の基盤となる汎用ハッシュ関数群を提供する。整数、浮動小数点数、文字列、配列、オブジェクト、タプルなど多様なデータ型に対応したハッシュ計算を行う。

**業務上の目的・背景**：ハッシュテーブルや集合などのデータ構造において、高速なキー検索を実現するためには、データ型に応じた効率的なハッシュ関数が不可欠である。このモジュールは、Nimの標準コレクション（tables、sets）が依存する基盤機能として、O(1)の平均検索時間を実現するための重要な役割を担う。

**機能の利用シーン**：
- ハッシュテーブル（Table、OrderedTable）のキーとして独自型を使用する際のハッシュ関数実装
- 集合（HashSet）への要素追加・検索
- 文字列やバイト列のハッシュ計算によるデータの同一性チェック
- カスタムデータ型をハッシュベースコレクションで使用する場合

**主要な処理内容**：
1. `!&`演算子: ハッシュ値の混合（ミキシング）
2. `!$`演算子: ハッシュ値の最終化（フィニッシング）
3. `hash`プロシージャ: 各データ型に対するハッシュ値計算
4. `hashWangYi1`: Wang Yi's hash_v1アルゴリズムによる64ビット整数ハッシュ
5. `hashIgnoreStyle`/`hashIgnoreCase`: スタイル/大文字小文字を無視したハッシュ
6. `murmurHash`/`hashFarm`: 文字列・バイト列用の高品質ハッシュ関数

**関連システム・外部連携**：
- tables（ハッシュテーブル）モジュールがhashプロシージャに依存
- sets（ハッシュセット）モジュールがhashプロシージャに依存
- strtabs（文字列テーブル）モジュールがhashIgnoreStyleに依存

**権限による制御**：特になし（純粋な計算ライブラリ）

## 関連画面

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

## 機能種別

計算処理 / ユーティリティライブラリ

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| x | T（ジェネリック） | Yes | ハッシュ計算対象の値 | 型に応じたhashプロシージャが存在すること |
| h | Hash | Yes | ミキシング対象のハッシュ値（!&演算子用） | なし |
| val | int | Yes | 混合する値（!&演算子用） | なし |
| data | pointer | Yes | ハッシュ対象のバイト列（hashData用） | 有効なポインタ |
| size | int | Yes | バイト列のサイズ（hashData用） | 0以上 |
| sPos, ePos | int | No | 部分文字列の開始・終了位置 | 0 <= sPos <= ePos < len(x) |

### 入力データソース

- アプリケーションコードからの直接呼び出し
- tablesモジュール、setsモジュール等からの内部呼び出し

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | Hash（int） | 計算されたハッシュ値。2のべき乗サイズのテーブルでand演算で切り詰め可能 |

### 出力先

- 呼び出し元への戻り値

## 処理フロー

### 処理シーケンス

```
1. hash(x)プロシージャ呼び出し
   └─ 型Tに応じた適切なハッシュアルゴリズムを選択

2. 整数型の場合
   └─ hashWangYi1関数でWang Yi's hash_v1アルゴリズムを適用
      └─ 64ビット乗算とXOR演算による高品質なスクランブル

3. 文字列/バイト列の場合
   └─ hashFarm関数（デフォルト）またはmurmurHash関数を使用
      └─ 長さに応じた最適化された処理（0-16, 17-32, 33-64, 65+バイト）

4. 複合型（タプル、オブジェクト）の場合
   └─ 各フィールドのハッシュ値を!&で順次混合
      └─ 最終的に!$で完了処理

5. コレクション型（配列、セット）の場合
   └─ 各要素のハッシュ値を順次混合
      └─ 最終的に!$で完了処理
```

### フローチャート

```mermaid
flowchart TD
    A[hash x 呼び出し] --> B{型の判定}
    B -->|整数/列挙| C[hashWangYi1]
    B -->|浮動小数点| D[hashWangYi1 with cast]
    B -->|文字列/バイト列| E{sHash2定義?}
    E -->|No| F[hashFarm]
    E -->|Yes| G[murmurHash]
    B -->|ポインタ| H[hash cast to int]
    B -->|タプル/オブジェクト| I[フィールド走査]
    B -->|配列/セット| J[要素走査]
    I --> K[!& でミキシング]
    J --> K
    K --> L[!$ でフィニッシュ]
    C --> M[result: Hash]
    D --> M
    F --> M
    G --> M
    H --> M
    L --> M
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | ハッシュ等価性 | 2つの値が==で等しい場合、そのハッシュ値も等しくなければならない | hashプロシージャ実装時 |
| BR-02 | ハッシュ分布 | 異なる値は可能な限り異なるハッシュ値を返すべき | 全てのhash呼び出し |
| BR-03 | 決定性 | 同じ入力に対して常に同じハッシュ値を返す | 単一プログラム実行内 |

### 計算ロジック

**!&（ミキシング）演算子**:
```nim
h = h + val
h = h + (h shl 10)
h = h xor (h shr 6)
```

**!$（フィニッシュ）演算子**:
```nim
h = h + (h shl 3)
h = h xor (h shr 11)
h = h + (h shl 15)
```

**Wang Yi's hash_v1**:
- 3つの64ビット素数定数（P0, P1, P58）を使用
- 128ビット乗算の上位64ビットと下位64ビットのXORを2回適用

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

該当なし（本モジュールはデータベース操作を行わない）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | コンパイルエラー | hashプロシージャが定義されていない型を使用 | 対象型に対するhashプロシージャを定義 |
| - | raiseAssert | VM用hashVmImpl実装が呼ばれた場合 | コンパイラ内部でオーバーライドされるため通常発生しない |

### リトライ仕様

該当なし（同期的な計算処理のため）

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

該当なし（データベース操作を行わない）

## パフォーマンス要件

- 整数ハッシュ: O(1)
- 文字列/バイト列ハッシュ: O(n) ※nはバイト長
- 複合型ハッシュ: O(フィールド数 * 各フィールドのハッシュコスト)

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

- 本モジュールは暗号学的ハッシュではない。セキュリティ目的には使用不可
- ハッシュ衝突攻撃に対する耐性は限定的
- 外部入力を直接ハッシュテーブルのキーとして使用する場合は、DoS攻撃に注意

## 備考

- `-d:nimPreviewHashRef`を指定するとref型のハッシュが有効になる
- `-d:nimStringHash2`を指定するとmurmurHashが使用される
- `-d:nimIntHash1`を指定すると整数に対してidentityハッシュが使用される

---

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

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

### 推奨読解順序

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

まず、Hash型の定義とハッシュ計算の基本概念を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | hashes.nim | `lib/pure/hashes.nim` | 74-77行目: `Hash* = int`の型定義。ハッシュテーブルが2のべき乗サイズを前提としている理由 |

**読解のコツ**: Hash型は単なるintのエイリアスだが、この型を通じて「ハッシュ値」という意味論を付与している。

#### Step 2: 基本演算子を理解する

ハッシュ計算の2つの基本ビルディングブロックを理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | hashes.nim | `lib/pure/hashes.nim` | 79-88行目: `!&`演算子（ミキシング）の実装。ビットシフトとXORによる拡散 |
| 2-2 | hashes.nim | `lib/pure/hashes.nim` | 90-98行目: `!$`演算子（フィニッシュ）の実装。最終的なスクランブル処理 |

**主要処理フロー**:
- **79-88行目**: `!&`は入力値をuintにキャストし、加算・シフト・XOR演算で混合
- **90-98行目**: `!$`は追加のシフト・XOR演算でビットを全体に拡散

#### Step 3: 高品質ハッシュ関数を理解する

Wang Yi's hash_v1とFarmHashの実装を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | hashes.nim | `lib/pure/hashes.nim` | 100-134行目: `hiXorLo`関数。128ビット乗算のエミュレーションとプラットフォーム別最適化 |
| 3-2 | hashes.nim | `lib/pure/hashes.nim` | 166-187行目: `hashWangYi1`関数。整数用の高品質ハッシュ |
| 3-3 | hashes.nim | `lib/pure/hashes.nim` | 336-384行目: `murmurHash`関数。MurmurHash3の実装 |
| 3-4 | hashes.nim | `lib/pure/hashes.nim` | 475-513行目: `hashFarm`関数。Google FarmHashの実装 |

**主要処理フロー**:
- **166-187行目**: hashWangYi1は3つの素数定数とhiXorLoを2回適用
- **475-513行目**: hashFarmは入力長に応じて4つの異なるパスを選択（0-16, 17-32, 33-64, 65+バイト）

#### Step 4: 型別ハッシュ実装を理解する

各データ型に対するhashプロシージャの実装を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | hashes.nim | `lib/pure/hashes.nim` | 209-216行目: 整数/列挙型のハッシュ |
| 4-2 | hashes.nim | `lib/pure/hashes.nim` | 273-283行目: 浮動小数点数のハッシュ |
| 4-3 | hashes.nim | `lib/pure/hashes.nim` | 521-536行目: 文字列のハッシュ |
| 4-4 | hashes.nim | `lib/pure/hashes.nim` | 666-704行目: タプル/オブジェクト/クロージャのハッシュ |
| 4-5 | hashes.nim | `lib/pure/hashes.nim` | 706-726行目: 配列のハッシュ |
| 4-6 | hashes.nim | `lib/pure/hashes.nim` | 760-766行目: セットのハッシュ |

**読解のコツ**:
- `when`ディレクティブでコンパイル時に分岐している箇所が多い
- `nimStringHash2`、`nimIntHash1`などのコンパイルフラグで挙動が変わる

#### Step 5: 特殊なハッシュ関数を理解する

スタイル無視・大文字小文字無視のハッシュを理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | hashes.nim | `lib/pure/hashes.nim` | 577-600行目: `hashIgnoreStyle`。アンダースコアを無視し小文字化 |
| 5-2 | hashes.nim | `lib/pure/hashes.nim` | 627-644行目: `hashIgnoreCase`。大文字小文字を無視 |

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

```
hash(x: T)
    │
    ├─ [整数型] hashWangYi1(x)
    │      └─ hiXorLo(a, b)
    │             ├─ [GCC/Clang] __uint128_t乗算
    │             ├─ [Windows] _umul128
    │             └─ [その他] hiXorLoFallback64
    │
    ├─ [文字列] hashFarm(x) または murmurHash(x)
    │      ├─ load4/load8（リトルエンディアン読み込み）
    │      └─ [len > 64] weakLen32withSeeds（チャンク処理）
    │
    ├─ [タプル/オブジェクト] fields(x)でフィールド走査
    │      └─ 各フィールドに対してhash呼び出し → !& → !$
    │
    └─ [配列/セット] items(x)で要素走査
           └─ 各要素に対してhash呼び出し → !& → !$
```

### データフロー図

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

整数値 x ─────────────▶ hashWangYi1 ─────────────────▶ Hash値
                          │
                          ▼
                    P0, P1, P58定数
                          │
                          ▼
                    hiXorLo(2回)
                          │
                          ▼
                    cast[Hash]

文字列 s ─────────────▶ toOpenArrayByte ─────────────▶
                          │
                          ▼
                    hashFarm/murmurHash
                          │
                          ▼
                    ブロック処理 + XOR混合
                          │
                          ▼
                    cast[Hash] ─────────────────────▶ Hash値

複合型 obj ───────────▶ fields(obj) ─────────────────▶
                          │
                          ▼
                    各フィールドにhash適用
                          │
                          ▼
                    h = h !& hash(field)
                          │
                          ▼
                    result = !$h ───────────────────▶ Hash値
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| hashes.nim | `lib/pure/hashes.nim` | ソース | 汎用ハッシュ関数のメイン実装 |
| tables.nim | `lib/pure/collections/tables.nim` | 依存先 | hashプロシージャを使用するハッシュテーブル |
| sets.nim | `lib/pure/collections/sets.nim` | 依存先 | hashプロシージャを使用するハッシュセット |
| strtabs.nim | `lib/pure/strtabs.nim` | 依存先 | hashIgnoreStyleを使用する文字列テーブル |
| jsbigints.nim | `lib/std/jsbigints.nim` | 依存元 | JavaScript BigInt用のハッシュサポート |
| endians.nim | `lib/std/endians.nim` | 依存元 | リトルエンディアン変換 |
| jsutils.nim | `lib/std/private/jsutils.nim` | 依存元 | JavaScript環境用ユーティリティ |
