Hash – LexYu Hive

Hash

雜湊（散列）演算法 - 將任意長度資料映射到固定長度的技術。

H(x) = Hash Code

Nouns

Hashing Function

雜湊函數
- 基本要求：
  - 輸入可以是任意大小的數據
  - 輸出是固定範圍的值
  - 相同的輸入必須得到相同的輸出
  - 應該盡量均勻分布（理想情況）

詳細說明

將資料透過特定的計算方式，計算出來的結果可轉換成資料儲存的位址，好的 Hashing Function 應計算簡單，少碰撞，讓雜湊表的儲存狀況能平均

Hash Code

雜湊值

詳細說明

原始資料 x 經過雜湊函數 H 所計算的結果，計算出來的結果無法回推原始資料，為不可逆

Hash Table

雜湊表

詳細說明

為連續的記憶體，用來儲存資料，每一筆資料會對應到一個位置 (Bucket)

Bucket

詳細說明

雜湊表中的某一筆資料，會存放在某一個位址 (Bucket Address)

Slot

詳細說明

一筆資料會有好幾各欄位，例如：一筆資料有 2 個欄位，則代表桶中有 2 個槽

Collision

碰撞

詳細說明

若多筆資料經過雜湊函數的雜湊值皆相同，則會使用到同一個桶位址(Bucket Address)

Overflow

溢位

詳細說明

資料經過雜湊函數的計算後，雜湊值所指向的桶位址已經被其它資料存滿，此筆資料無法儲存在該位址

溢位處理

分離鏈接法 Separate Chaining
線性開放定址 Open Addressing Mode
- 線性探測 Linear Probing
- 二次探測 Quadratic Probing
- 雙重哈希 Double Hashing
- memo
  - 重新插入法
  - 群聚重整法
h(k, i) 是第 i 次探測的位置
h'(k) 是初始哈希函數，通常表示為 key mod size
i 是探測次數 （0, 1, 2, ...）
m 是哈希表的大小（在代碼中通常表示為 size）

線性探測

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
}

線性探測

公式說明

公式：

h(k, i) = (h'(k) + i) \mod m

代碼中表示為: (key%size + i) % size

二次探測

公式說明

公式：

h(k, i) = (h'(k) + i^2) \mod m

代碼中表示為: (key%size + i*i) % size

雙重哈希

公式說明

公式：

h(k, i) = (h1(k) + i \times h2(k)) \mod{m}

代碼中表示為: (h1 + i*h2) % size

h1 = key % size
h2 = 1 + (key % (size - 1))

Hash Algorithms

MD5 (Message Digest Algorithm 5)

輸出: 128-bit (32 hex characters)
用途: 檔案完整性驗證、checksum
注意: 不建議用於密碼雜湊（已被破解）

其他常見 Hash 演算法

演算法	輸出長度	安全性	用途
MD5	128-bit	弱	檔案校驗
SHA-1	160-bit	弱	舊版 Git
SHA-256	256-bit	強	區塊鏈、TLS
SHA-3	可變	強	新標準

Bloom Filter Hash Table