🔐 Hash 雜湊學習筆記

💪 魚～加油呀！呀呀呀、一起來學 Hash 吧！

📖 什麼是 Hash？

Hash（雜湊）是一種將任意大小的資料轉換成固定大小值的函數。

簡單說：輸入任何資料 → 產生一串獨特的「指紋」

🔑 基本概念

術語	說明
Hash 函數	將資料轉成 Hash 值的函數
Hash 表	用 Hash 快速存取資料的結構
鍵 (Key)	要儲存的資料的識別碼
值 (Value)	對應鍵要儲存的內容
碰撞 (Collision)	不同鍵產生相同 Hash 值

💻 Hash 函數範例

Python 內建的 hash() 函數：

>>> hash("apple")
-1275449552
>>> hash(123)
123
>>> hash((1, "hello"))
-811352108

自己寫一個簡單的 Hash 函數：

def simple_hash(key):
    """將字串轉成數字"""
    total = 0
    for char in str(key):
        total += ord(char)  # 取得字元的 ASCII 碼
    return total % 100      # 取餘數限制範圍

print(simple_hash("apple"))   # 例如：530
print(simple_hash("banana"))  # 例如：609

🗂️ Hash 表 (Hash Table)

Hash 表是一種鍵值對的資料結構，透過 Hash 函數快速找到資料。

示意圖：

┌─────────┬─────────┐
│ Key     │ Value   │
├─────────┼─────────┤
│ "apple" │ 蘋果     │
│ "banana"│ 香蕉     │
│ "cat"   │ 貓       │
└─────────┴─────────┘

用 "cat" 找 → Hash → 直接取得 "貓"

Python 實作：

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # 鏈結法

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        self.table[index].append((key, value))

    def get(self, key):
        index = self.hash_function(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# 使用
ht = HashTable()
ht.insert("name", "魚")
ht.insert("age", 18)
print(ht.get("name"))  # 輸出: 魚

⚠️ 碰撞處理

當兩個不同的鍵產生相同的 Hash 值時，叫「碰撞」。

解決方法：

鏈結法 (Chaining)：同一位置用串列儲存多個值
開放定址法 (Open Addressing)：找下一個空位

⏱️ 時間複雜度

操作	平均情況	最差情況
搜尋	O(1)	O(n)
插入	O(1)	O(n)
刪除	O(1)	O(n)

🎯 常見應用

🔍 字典 Python 的 dict 就是 Hash 表
🔐 加密 MD5、SHA-1、SHA-256
📁 檢查檔案確認檔案是否被修改
🗂️ 資料庫快速查找資料
🏷️ 快取快取常用資料

🛡️ 常見 Hash 演算法

演算法	輸出長度	用途
MD5	128 位元	檔案驗證（已被破解）
SHA-1	160 位元	已被淘汰
SHA-256	256 位元	加密貨幣、区塊鏈
SHA-512	512 位元	高安全性需求

💻 Python hashlib 實作

import hashlib

# MD5
md5 = hashlib.md5(b"hello").hexdigest()
print(md5)  # 5d41402abc4b2a76b9719d911017c592

# SHA-256
sha256 = hashlib.sha256(b"hello").hexdigest()
print(sha256)
# 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

✅ 重點整理

Hash 將任意資料轉成固定長度的值
Hash 表提供 O(1) 的快速查詢
碰撞是不同鍵產生相同 Hash
可用鏈結法或開放定址法解決碰撞
加密 Hash 不可逆，保證資料完整性

📝 練習題

寫一個簡單的 Hash 表實作
測試碰撞的情況
用 hashlib 產生檔案的 MD5 值

💪 魚～慢慢來呀！一點一點學，不急的呀！呀呀呀、你可以的！