Hash

ハッシュ（散列(さんれつ) ）アルゴリズム - 任意(にんい) の長(なが) さのデータを固定長(こていちょう) に変換(へんかん) する技術(ぎじゅつ) 。

用語

Hashing Function

• ハッシュ関数(かんすう)
  • 基本要件(きほんようけん) ：
    • 入力(にゅうりょく) は任意(にんい) のサイズのデータ
    • 出力(しゅつりょく) は固定範囲(こていはんい) の値(あたい)
    • 同(おな) じ入力(にゅうりょく) は同(おな) じ出力(しゅつりょく) を得(え) る
    • できるだけ均一(きんいつ) に分布(ぶんぷ) （理想的(りそうてき) な場合(ばあい) ）

Hash Code

• ハッシュ値(ち)

Hash Table

• ハッシュテーブル

Bucket

• バケット

Collision

• 衝突(しょうとつ)

Overflow

• オーバーフロー

オーバーフロー処理

• 分離連鎖法(ぶんりれんさほう) Separate Chaining

• 開放(かいほう) アドレス法(ほう) Open Addressing Mode

  • 線形探査(せんけいたんさ) Linear Probing
  • 二次探査(にじたんさ) Quadratic Probing
  • 二重(にじゅう) ハッシュ Double Hashing

• h(k, i) は i 回目(かいめ) の探査位置(たんさいち)

• h'(k) は初期(しょき) ハッシュ関数(かんすう) （通常(つうじょう) key mod size）

• i は探査回数(たんさかいすう) （0, 1, 2, …）

• m はハッシュテーブルのサイズ

func (hm *HashMap) linearProbing(hash uint64) uint64 {
  return (hash + 1) % hm.capacity
}

// 二次探査
func (hm *HashMap) quadraticProbing(hash uint64, i int) uint64 {
  return (hash + uint64(i*i)) % hm.capacity
}

func (hm *HashMap) doubleHashing(hash uint64, key any) uint64 {
  // 第二ハッシュ関数を使用
  h2 := someOtherHashFunction(key)
  return (hash + h2) % hm.capacity
}

線形探査

二次探査

二重ハッシュ

Hash Algorithms

MD5 (Message Digest Algorithm 5)

• 出力(しゅつりょく) : 128-bit (32 hex characters)
• 用途(ようと) : ファイル整合性検証(せいごうせいけんしょう) 、checksum
• 注意(ちゅうい) : パスワードハッシュには非推奨(ひすいしょう) （既(すで) に破(やぶ) られている）

その他(ほか) の一般的(いっぱんてき) な Hash アルゴリズム