哈希表

哈希函數

哈希表使用了哈希函數來完成key到地址的快速映射，所以在了解哈希表之前，需要先明白哈希函數的概念和特點。

哈希函數的定義

• 哈希函數
  • 哈希函數是一種將任意長度輸入的數據，轉換成固定長度輸出的算法
  • 哈希函數H可以表示為y=H(x)
    • H指代哈希函數
    • x是輸入數據，可以是任意長度
    • y是輸出的哈希值，具有固定長度
• Hashcode
  • 這部分被固定長度輸出的數據被稱為Hashcode哈希值或散列值

哈希函數的特點

• 確定性

  • 不管執行多少次，通過某個key所得到的內存數組索引位置（即哈希值）是不變的

• 固定長度輸出

  • 哈希函數的核心任務是將無限映射到有限，即不管輸入值數據大小是1kb還是1G，數據長度是1位還是1000位，它的通過哈希函數產生的哈希值長度都是固定的，具體輸出長度由算法決定
    • SHA-256算法輸出永遠是256位（32字節）
    • MD5算法輸出永遠是128位（16字節）
      

• 單向性

  • 輸入值可以單向通過哈希函數獲得哈希值，但是通過哈希值不可以反向獲取輸入值原數據。哈希函數是一個“單向門”或“單向函數”。從 x 計算 H(x) 很容易，但從H(x)反推出 x 極其困難。
    • 這一點在密碼存儲上至關重要，系統可以存儲用戶密碼的哈希值，即時數據庫泄漏，攻擊者也無法輕易從哈希值還原出用戶的原始密碼

• 高效性

  • 計算哈希值的過程快速且高效，即時是處理大量數據也能快速完成
  • 哈希函數算法是由簡單的位運算（與、或、非、異或、移位、旋轉）構成，這些操作在現代計算機上執行是非常快速的

• 需要處理哈希沖突/哈希碰撞

  • 哈希函數因為是無限映射到有限，輸入空間是無限的，所以有可能出現兩個不同的輸入，對應了同一個哈希值，即出現了碰撞
  • 哈希函數設計目標需要盡可能的避免出現碰撞

引申問題1：哈希函數和加密函數的區別

• 哈希函數和加密函數最大的區別是
  • 哈希函數是單向的，不可逆，即通過哈希值很困難找到原始值
  • 加密函數式雙向的，可逆（需密鑰解密），通過密文也可以找到原文

維度	哈希函數 (Hash)	加密函數 (Encryption)
可逆性	單向，不可逆	雙向，可逆（需密鑰解密）
密鑰	無密鑰	有密鑰（對稱或公私鑰）
輸出長度	固定（如 256 位）	可變（通常 ≥ 明文長度）
速度目標	盡量快，便于校驗	對稱快、非對稱慢，但都比哈希慢
碰撞	必須抗碰撞（難以找到兩輸入同輸出）	無碰撞概念（一對一映射）
典型應用	密碼摘要、數據完整性、數字簽名	機密傳輸、磁盤加密、HTTPS
示例算法	SHA-256, BLAKE3, MD5	AES, ChaCha20（對稱）；RSA, ECC（非對稱）

引申問題2：MD5算法和SHA256算法是哈希函數還是加密函數

• MD5算法和SHA256算法都是哈希算法，不算加密算法
  • 兩者都是任意長度的輸入，壓縮成固定長度摘要(SHA256為256bit，MD5為128bit)
  • 兩者都不設秘鑰，不可逆，不具備加密/界面功能
  • 常見用途
    • 校驗文件完整性
    • 數字簽名前置壓縮
    • 密碼存儲（配合鹽值和KDF）

引申問題3：位運算為什么快

• 位運算是直接在CPU寄存器上用最簡硬件邏輯完成的
  • AND/OR/XOR/NOT/SHIFT 都只需少量晶體管組成的組合邏輯門（與門、或門、異或門、移位器）
• 零內存訪問、零復雜算法、單周期延遲，是所有運算中成本最低的

哈希表的定義

定義

• 哈希表是一種動態數據結構，以key-value鍵值對存儲數據
• 核心思想是使用哈希函數將key轉換為數組下標索引保存后，下次再次查詢時，使用仍然通過哈希函數將key轉化為數組下標，快速定位到數據的位置

目的

• 實現快速的數據存儲和檢索
• 注意，此處的快速檢索指的是通過key來查詢value是快速的；如果僅僅只是查找某個value，數據檢索效率并不高

核心公式

• index = hash(key) mod capacity

組成部分

• 哈希函數

  • 將key轉換為數組索引的算法

• 數組

  • 用于存儲鍵值對數據的數組

• 哈希沖突/碰撞解決方法

  • 因為哈希函數式無限（輸入）轉化為有限（輸出），一定存在不同的輸入產生相同的輸出，即碰撞（或稱為沖突）
  • 沖突/碰撞解決方法，指的是當碰撞發生時，不同的key被映射到同一個數組下標索引時，如何處理，一般使用以下方法
    • 鏈表法
    • 開放尋址法

哈希表的優點

• 操作高效

  • 增、刪、查操作的時間復雜度為O(1)，非常高效

• 實現簡單

  • 大多數編程語言中都有內置支持（Java的Hashmap；Python的dict）

• 靈活性強

  • 可以存儲各種類型的鍵值對

哈希表的缺點

• 哈希沖突處理

  • 哈希沖突處理不當，會影響性能

• 空間浪費

  • 為了避免哈希沖突，一般都會預留較大的內存空間

• 不支持有序遍歷

  • 哈希表中的元素是無序的（因為保存時是通過hash函數計算出應該放在哪個數組下標，導致整體是隨機的）

• 設計復雜

  • 需精心設計哈希與沖突策略、負載因子、并發、縮容等工程細節，難度較高

引申問題4：哈希表為什么操作這么高效

• 哈希表操作時可以直接定位數據存儲位置（前提通過key來操作）

  • 哈希表的核心是哈希函數，哈希函數可以將key直接轉換為數據在數組中的下標，比如get(key)等同于直接查array[5]，時間復雜度是常數時間 O(1)

• 數據結構支持隨機訪問

  • 因為是直接查下標，不需要遍歷數據

• 哈希沖突處理優化

  • 對于可能存在的哈希沖突，哈希表會通過鏈表法、開放尋址法來優化防止出現哈希沖突，從而減少哈希沖突對性能的影響

哈希表的應用場景

• 快速查找

  • 通過索引key快速定位內容
  • 統計字符或單次出現的頻率
    • 計算方式：對于每個字符，如果它已經在哈希表（這一步可以使用哈希函數通過key快速索引）中，將對應的值加 1。
    • 如果它不在哈希表中，將其加入哈希表，值設為 1。
  • 快速判斷一個元素是否在數組中

• 數據庫索引

  • 數據庫中的哈希索引（比如MySQL的Memory引擎）

• 緩存系統

  • LRU 緩存（Least Recently Used Cache）常用哈希表 + 雙向鏈表實現