hash: 値あたいから 32-bit 非暗号ひあんごうハッシュを得えるための trait

目的もくてき:

• map / set 系けいの実装じっそうが、キーごとの具体的ぐたいてきな関数名かんすうめいに依存いぞんせず Hash trait 経由けいゆでハッシュを取得しゅとくできるようにします。
• i32 や str のような既存きそんキー型を、共通きょうつう helper から同一どういつの流儀りゅうぎで扱あつかえるようにします。

実装じっそう:

• 返かえり値あたいは 32-bit の整数せいすうで、現在げんざいの stdlib が採用さいようしている alloc/hash/hash32::hash32 overload の分布ぶんぷを再利用さいりようします。
• trait Hash が hash32 <(Self)->i32> を要求ようきゅうし、helper hash32_by_trait が呼よび出だしを集約しゅうやくします。

注意ちゅうい:

• 暗号あんごうハッシュではありません。
• 永続化えいぞくかや通信つうしんで安定あんていした識別子しきべつしとして使つかうものではなく、主おもに内部ないぶの分散ぶんさんのために使つかいます。
• 同値どうちと Hash の実装じっそうは整合せいごうしている必要ひつようがあります。

計算量けいさんりょう:

• i32 は O(1) です。
• str は文字列長もじれつちょうを n として O(n) です。

#entry main
#target std
#import "std/test" as *
#import "core/traits/hash" as *
fn main <()*>i32> ():
    assert_eq_i32 hash32_by_trait 123456 hash32_by_trait 123456;
    assert ne hash32_by_trait 123456 hash32_by_trait 123457;
    0

Hash: map / set 向むけ 32-bit ハッシュ能力のうりょく

目的もくてき:

• 型かたごとのハッシュ計算けいさんを trait として宣言せんげんし、連想配列れんそうはいれつや集合しゅうごうの実装じっそうを共通化きょうつうかします。

注意ちゅうい:

• Eq 相当そうとうの同値性どうちせいと矛盾むじゅんしないように実装じっそうする必要ひつようがあります。

hash32_by_trait: Hash trait 経由けいゆで 32-bit ハッシュを得える

目的もくてき:

• trait 呼よび出だしを 1 箇所かしょへ集約しゅうやくし、collections 側がわが具体的ぐたいてきな関数名かんすうめいへ依存いぞんしないようにします。

実装じっそう:

• Hash::hash32 をそのまま呼よびます。

注意ちゅうい:

• 型推論かたすいろんが曖昧あいまいな場合ばあいは周囲しゅういの型注釈かたちゅうしゃくで解決かいけつします。

計算量けいさんりょう:

• 実際じっさいの計算量けいさんりょうは対象たいしょう型の Hash 実装じっそうに従したがいます。

Hash<i32>: i32 値あたいを固定長こていちょうキーとして混合こんごうする

目的もくてき:

• i32 を連想配列れんそうはいれつや集合しゅうごうのキーに使つかえるようにします。

実装じっそう:

• alloc/hash/hash32::hash32 overload を利用りようします。

計算量けいさんりょう:

• O(1)

Hash<bool>: bool を 0/1 として混合こんごうする

目的もくてき:

• bool を小ちいさな離散りさんキーとして扱あつかえるようにします。

実装じっそう:

• bool を i32 へ cast してから hash32 に委譲いじょうします。

計算量けいさんりょう:

• O(1)

Hash<u8>: u8 を 0..255 の小ちいさな整数せいすうキーとして扱あつかう

目的もくてき:

• 文字もじや小ちいさな分類値ぶんるいちを集合しゅうごうや表ひょうのキーへ使つかえるようにします。

実装じっそう:

• u8 を i32 に拡張かくちょうして hash32 に渡わたします。

計算量けいさんりょう:

• O(1)

Hash<i64>: i64 を 32-bit に折おりたたんで混合こんごうする

目的もくてき:

• i64 を広ひろい整数せいすうキーとして使つかうときの基本きほんハッシュを提供ていきょうします。

実装じっそう:

• 上位じょうい 32-bit と下位かい 32-bit を XOR で折おりたたみ、その結果けっかを hash32 に通とおします。

注意ちゅうい:

• 衝突しょうとつは理論上りろんじょうありえますが、内部ないぶのハッシュテーブル用途ようととしては十分じゅうぶんです。

計算量けいさんりょう:

• O(1)

Hash<str>: str の UTF-8 列れつを順じゅんに混合こんごうする

目的もくてき:

• str を文字列もじれつキーとして連想配列れんそうはいれつや集合しゅうごうに使つかえるようにします。

実装じっそう:

• alloc/hash/hash32::hash32 overload を利用りようします。

注意ちゅうい:

• UTF-8 の文字数もじすうではなくバイト列れつに対たいして計算けいさんします。

計算量けいさんりょう:

• 文字列長もじれつちょうを n として O(n)