# 機能設計書 134-ハッシュ関数

## 概要

本ドキュメントは、Julia の `hash` / `objectid` による汎用ハッシュ値計算機能について、その設計・処理仕様を記述するものである。

### 本機能の処理概要

`hash` 関数は、Julia の任意のオブジェクトに対して整数ハッシュコードを計算する汎用ハッシュ関数である。`Dict` や `Set` のキー比較、`isequal` に基づく等価性判定と連動して動作する。rapidhash アルゴリズムをベースにした高性能なハッシュ実装を提供する。

**業務上の目的・背景**：ハッシュテーブル（Dict、Set）はプログラミングにおいて最も基本的なデータ構造の一つであり、その性能はハッシュ関数の品質に直結する。Julia のハッシュ関数は、`isequal(x, y)` ならば `hash(x) == hash(y)` という不変条件を保証しつつ、高い分散性と高速性を実現する。

**機能の利用シーン**：Dict のキーハッシュ計算、Set の要素ハッシュ計算、カスタム型の辞書キーとしての利用、データの一意性チェック、ハッシュベースの等価性比較など。

**主要な処理内容**：
1. `hash(x)` -- デフォルトシードによるハッシュ計算
2. `hash(x, h::UInt)` -- シードを指定したハッシュ計算（2引数形式）
3. 整数型の専用ハッシュ（hash_mix_linear + hash_finalizer）
4. 浮動小数点型のハッシュ（整数等価性を保証）
5. 文字列のハッシュ（rapidhash ベースの hash_bytes）
6. Real 型の汎用ハッシュ（decompose によるnum/pow/den分解）
7. `objectid` によるオブジェクトID取得（フォールバック）
8. バイト列のハッシュ（rapidhash アルゴリズム）

**関連システム・外部連携**：Dict / Set のキーハッシュ、isequal 関数、型システム（Type のハッシュ）、文字列システム、GC（objectid）と連携する。

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

## 関連画面

本機能は特定の画面との紐付けはない。

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 内部的に Dict/Set の操作時に自動的に呼び出される |

## 機能種別

計算処理 / ユーティリティ

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| data | Any | Yes | ハッシュ対象のオブジェクト | - |
| h | UInt | No | 混合するシード値（デフォルト: HASH_SEED） | - |

### 入力データソース

Julia のコード内での直接利用。Dict/Set による暗黙的な呼び出し。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| ハッシュ値 | UInt | 計算されたハッシュコード（UInt64 または UInt32） |

### 出力先

呼び出し元への戻り値。

## 処理フロー

### 処理シーケンス

```
1. hash(data) の呼び出し
   └─ HASH_SEED をシードとして hash(data, HASH_SEED) を呼び出す
2. 型に応じたディスパッチ
   a. UInt64/Int64 → hash_mix_linear + hash_uint64
   b. 小型整数（Bool, Int8-Int32 等） → Int64 に拡張してから hash
   c. Float64 → 整数等価チェック後に適切なハッシュ
   d. Float32/Float16 → Float64 変換後にハッシュ
   e. Real → decompose で num/pow/den に分解してハッシュ
   f. String → GC.@preserve + hash_bytes (ポインタベース)
   g. AbstractString → utf8units + hash_bytes (イテレータベース)
   h. Symbol → objectid を直接返す
   i. Type → ccall(:jl_type_hash) + hash
   j. その他 → objectid に基づくハッシュ
3. hash_bytes による rapidhash
   └─ バッファサイズに応じた処理（<=16, <=48, >48バイト）
```

### フローチャート

```mermaid
flowchart TD
    A["hash(data)"] --> B["hash(data, HASH_SEED)"]
    B --> C{"data の型"}
    C -->|UInt64/Int64| D["hash_mix_linear + hash_uint64"]
    C -->|"小型整数"| E["Int64拡張 -> hash"]
    C -->|Float64| F{"整数等価?"}
    F -->|Yes| G["hash(xi, h)"]
    F -->|NaN| H["hx_NaN xor h"]
    F -->|No| I["hash(bitcast(UInt64,x), h)"]
    C -->|Real| J["decompose -> hash_integer"]
    C -->|String| K["hash_bytes(ptr, len)"]
    C -->|Symbol| L["objectid(x)"]
    C -->|Type| M["jl_type_hash -> hash"]
    C -->|Other| N["hash(objectid(x), h)"]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-134-01 | 等価性保証 | `isequal(x, y)` ならば `hash(x) == hash(y)` | 常時 |
| BR-134-02 | 数値等価性 | `hash(1) == hash(1.0) == hash(1//1)` -- 同じ数学的値なら同じハッシュ | 数値型間 |
| BR-134-03 | NaN 安定性 | NaN は安定したビットパターンを持たないため専用ハッシュ値を使用 | isnan(x) の場合 |
| BR-134-04 | プロセス非安定 | ハッシュ値は Julia プロセス間で安定しない（HASH_SEED がプロセスごとに異なりうる） | プロセス間比較 |
| BR-134-05 | 2引数形式推奨 | 新型の hash 実装は2引数形式 `hash(x, h::UInt)` で行い、デフォルト引数は使用しない | カスタム型のhash定義時 |

### 計算ロジック

**hash_mix（52行目）**: `widemul(a, b)` の上位・下位64ビットの XOR
```
hash_mix(a, b) = xor(mul_parts(a, b)...)
mul_parts(a, b) = (p >> 64, p & 0xFFFFFFFFFFFFFFFF) where p = widemul(a, b)
```

**hash_finalizer（56-61行目）**: 64ビット整数の最終化
```
x ^= (x >> 32)
x *= 0x63652a4cd374b267
x ^= (x >> 33)
```

**hash_mix_linear（55行目）**: 小キー向け高速ミキシング `3h - x`

**浮動小数点のハッシュ（165-196行目）**:
- Float64 が Int64/UInt64 範囲内の整数と等しい場合、整数としてハッシュ（数値等価性保証）
- NaN の場合は専用のハッシュ値 `hx_NaN` を使用
- それ以外はビットパターンのハッシュ

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

本機能はデータベース操作を行わない。

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

該当なし。

## エラー処理

### エラーケース一覧

本機能は通常エラーをスローしない。任意のオブジェクトに対してハッシュ値を計算できる（objectid フォールバック）。

### リトライ仕様

該当なし。

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

該当なし。

## パフォーマンス要件

- 整数のハッシュは hash_mix_linear + hash_finalizer で最小コスト
- 文字列のハッシュは rapidhash アルゴリズム（ポインタベース直接アクセス）
- `@assume_effects :terminates_globally` アノテーションにより、コンパイラ最適化を許容
- `@assume_effects :total` により String の hash は副作用なしと宣言
- HASH_SECRET は4つの UInt64 定数タプルで、rapidhash のシークレットとして使用

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

- HASH_SEED はプロセス起動時に固定される定数であり、HashDoS 攻撃に対する保護は HASH_SECRET の固定値に依存する
- セキュリティ用途のハッシュには SHA モジュール等の暗号学的ハッシュ関数を使用すべき

## 備考

- `objectid(x)` は C ランタイムの `jl_object_id_` を呼び出し、オブジェクトのメモリアドレスまたはビットパターンに基づくIDを返す
- Symbol のハッシュは直接 `objectid` を返す（282行目）-- シンボルはインターンされるため
- `_jl_type_hash` は `@assume_effects :total` で修飾されている（型は削除されないため安全）
- rapidhash は [github.com/Nicoshev/rapidhash](https://github.com/Nicoshev/rapidhash) を Julia に移植したもの

---

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

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

### 推奨読解順序

#### Step 1: 定数とヘルパーを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | hashing.jl | `base/hashing.jl` | **3行目**: `HASH_SEED` -- デフォルトシード（UInt64/UInt32分岐） |
| 1-2 | hashing.jl | `base/hashing.jl` | **4-9行目**: `HASH_SECRET` -- rapidhash用の4つの秘密定数 |
| 1-3 | hashing.jl | `base/hashing.jl` | **48-61行目**: `mul_parts` / `hash_mix` / `hash_mix_linear` / `hash_finalizer` -- 基本ミキシング関数群 |

**読解のコツ**: `hash_mix` は widemul（128ビット乗算）の上位・下位の XOR で、rapidhash の中核。`hash_mix_linear` は小キー向けの簡易版。`hash_finalizer` は最終的なビットミキシング。

#### Step 2: プリミティブ型のハッシュを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | hashing.jl | `base/hashing.jl` | **40行目**: `hash(data::Any) = hash(data, HASH_SEED)` -- エントリーポイント |
| 2-2 | hashing.jl | `base/hashing.jl` | **75-77行目**: UInt64 / Int64 / 小型整数のハッシュ |
| 2-3 | hashing.jl | `base/hashing.jl` | **44-46行目**: Type / WeakRef / フォールバックのハッシュ |

**主要処理フロー**:
- **75行目**: `hash(x::UInt64, h) = hash_uint64(hash_mix_linear(x, h))`
- **76行目**: `hash(x::Int64, h) = hash(bitcast(UInt64, x), h)`
- **77行目**: 小型整数は Int64 に拡張してハッシュ

#### Step 3: 浮動小数点のハッシュを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | hashing.jl | `base/hashing.jl` | **164行目**: `hx_NaN` 定数 -- NaN 用のハッシュ値 |
| 3-2 | hashing.jl | `base/hashing.jl` | **165-196行目**: Float64 / Float32 / Float16 のハッシュ |

**読解のコツ**: 浮動小数点のハッシュは数値等価性を保証するのが最重要。`1.0` と `1` は `isequal` であるため同じハッシュ値でなければならない。`fptosi` で整数変換し、`isequal` で比較してから整数ハッシュに委譲する。

#### Step 4: Real 型の汎用ハッシュを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | hashing.jl | `base/hashing.jl` | **200-245行目**: `hash(x::Real, h)` -- decompose ベースの汎用ハッシュ |
| 4-2 | hashing.jl | `base/hashing.jl` | **147-159行目**: `hash_integer` / `_hash_integer` -- 任意精度整数のハッシュ |

#### Step 5: hash_bytes（rapidhash）を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | hashing.jl | `base/hashing.jl` | **288-361行目**: `hash_bytes(ptr, n, seed, secret)` -- ポインタベース版 |
| 5-2 | hashing.jl | `base/hashing.jl` | **384-458行目**: `hash_bytes(arr, seed, secret)` -- 配列ベース版 |
| 5-3 | hashing.jl | `base/hashing.jl` | **494-632行目**: `hash_bytes(iter, seed, secret)` -- イテレータベース版 |
| 5-4 | hashing.jl | `base/hashing.jl` | **634-638行目**: 文字列のハッシュ -- hash_bytes を呼び出す |

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

```
hash(data)
    |
    +-- hash(data, HASH_SEED)
            |
            +-- [UInt64] hash_uint64(hash_mix_linear(x, h))
            |       └── hash_finalizer(...)
            |
            +-- [Float64] fptosi(Int64, x) -> hash(xi, h) or hash(bitcast(...), h)
            |
            +-- [Real] decompose(x) -> hash_integer(num/pow/den, h)
            |       └── _hash_integer -> hash_bytes(codeunits(u), seed, secret)
            |
            +-- [String] hash_bytes(pointer(data), sizeof(data), h, HASH_SECRET)
            |       └── rapidhash アルゴリズム
            |
            +-- [Symbol] objectid(x)
            |
            +-- [Type] _jl_type_hash(T) -> hash(h_val, h)
            |
            +-- [Other] hash(objectid(data), h)
```

### データフロー図

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

hash(42)              --> hash(42, HASH_SEED)
                      --> hash(Int64(42), h)
                      --> hash(bitcast(UInt64, 42), h)
                      --> hash_uint64(hash_mix_linear(x, h))
                      --> hash_finalizer(...)           --> UInt ハッシュ値

hash("hello")         --> hash_bytes(ptr, 5, h, SECRET)
                      --> rapidhash(<=16 bytes path)    --> UInt ハッシュ値

hash(1.0)             --> fptosi(Int64, 1.0) = 1
                      --> isequal(1, 1.0) = true
                      --> hash(1, h)                    --> UInt ハッシュ値
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| hashing.jl | `base/hashing.jl` | ソース | hash関数の主要実装、rapidhash、整数・浮動小数点・文字列・Real型のハッシュ |
| hashing2.jl | `base/hashing2.jl` | ソース | 配列・タプル・その他コレクション型のハッシュ |
| essentials.jl | `base/essentials.jl` | ソース | objectid の定義元 |
| dict.jl | `base/dict.jl` | ソース | Dict のハッシュ利用箇所 |
| set.jl | `base/set.jl` | ソース | Set のハッシュ利用箇所 |
| test/hashing.jl | `test/hashing.jl` | テスト | ハッシュ関数の回帰テスト |
