[學習] 哈希碼：原理、用途與實現詳解（C代碼示例）

哈希碼：原理、用途與實現詳解

博主在《在C語言中使用字典》一文中，使用哈希來實現鍵值對的快速檢索，今天對哈希這一算法工具，進行一些深入的研究，爭取能能做到知其然亦知其所以然。

文章目錄

哈希碼：原理、用途與實現詳解
- 一、哈希碼的原理
- - 1.1 什么是哈希碼？
  - 1.2 哈希函數的特性
  - 1.3 哈希沖突
- 二、哈希的表達式
- - 2.1 通用哈希函數表達式
  - 2.2 多項式哈希函數（Polynomial Hashing）
  - 2.3 DJB2 哈希函數
  - 2.4 SHA-256 哈希函數
  - - (1) 初始化工作變量
    - (2) 主壓縮循環
    - (3) 更新哈希值
  - 2.5 MD5 哈希函數
  - - (1) 初始化緩沖區
    - (2) 主循環（四組 16 輪）
    - (3) 更新緩沖區
  - 2.6 哈希沖突解決方法的顯性表達式
  - - (1) 鏈地址法（拉鏈法）
    - (2) 開放定址法（線性探測）
    - (3) 雙散列函數法
  - 5. 小結
- 三、哈希碼的用途
- - 3.1 數據檢索
  - 3.2 數據完整性驗證
  - 3.3 密碼存儲
  - 3.4 分布式系統
- 四、哈希碼的實現
- - 4.1 C語言實現哈希碼計算
  - - 代碼解析：
    - 輸出示例：
  - 4.2 哈希表實現
  - - 代碼解析：
- 五、總結

哈希碼（Hash Code）是計算機科學中的核心概念之一，廣泛應用于數據存儲、檢索、安全等領域。本文將從原理、數學表達式、用途和實現四個方面詳細介紹哈希碼，并提供一個完整的C語言實現示例。

一、哈希碼的原理

1.1 什么是哈希碼？

哈希碼是通過哈希函數將任意長度的數據（如字符串、文件等）映射為固定長度數值的過程。其核心思想是通過數學變換，將復雜的數據結構轉換為一個唯一的標識符。

1.2 哈希函數的特性

哈希函數具有以下關鍵特性：

單向性
從原始數據計算哈希碼是單向的，即無法通過哈希碼反推出原始數據。
$\text{Hash}(x) = h \quad \text{但} \quad x \neq \text{Hash}^{-1}(h)$
確定性
相同的輸入數據始終生成相同的哈希碼。
$x_1 = x_2 \Rightarrow \text{Hash}(x_1) = \text{Hash}(x_2)$
敏感性
輸入的微小變化會導致哈希碼的顯著改變。
$x_1 \sim x_2 \quad \text{但} \quad \text{Hash}(x_1) \neq \text{Hash}(x_2)$
均勻性
哈希碼在輸出空間中均勻分布，減少沖突概率。
$\forall x, y, \quad \text{Hash}(x) \approx \text{UniformDistribution}$

1.3 哈希沖突

哈希沖突是指不同的輸入生成相同的哈希碼。由于哈希函數的輸出空間有限，而輸入空間無限，沖突是不可避免的。常見的解決方法包括：

鏈地址法：將沖突的鍵值對存儲在鏈表中。
開放尋址法：通過探查算法尋找空閑位置。

二、哈希的表達式

哈希函數的顯性表達式因具體算法而異，以下是幾種常見哈希函數的顯性表達式及其數學形式：

2.1 通用哈希函數表達式

哈希函數的基本形式為：
$\text{Addr} = H(\text{key})$
其中：

$\text{key}$ ：輸入數據（字符串、數值等）。
$H$ ：哈希函數。
$\text{Addr}$ ：輸出的哈希碼（通常為固定長度的整數或二進制串）。

2.2 多項式哈希函數（Polynomial Hashing）

多項式哈希函數通過將輸入字符串視為多項式系數，計算其模值：
$\left( \sum_{i=0}^{n-1} a_i \cdot x^i \right) \mod m$
其中：

$a_0a_1\ldots a_{n-1}$ ：輸入字符串，長度為 $n$ 。
$x$ ：基數（常選質數，如 31、37）。
$m$ ：模數（通常為哈希表大小）。
$m o d$ ：取模（求余）運算。

示例：
對于字符串 “abc”（ASCII 碼分別為 97, 98, 99），若 $x = 31$ , $m = 1000$ ：
$\cdot 31^0 + 98 \cdot 31^1 + 99 \cdot 31^2) \mod 1000$

2.3 DJB2 哈希函數

DJB2 是一種簡單高效的哈希算法，其顯性表達式為：
$\text{hash} = ((\text{hash} \ll 5) + \text{hash}) + c$
其中：

$\ll$ ：左移運算（等價于乘以 $2^5 = 32$ ）。
$c$ ：當前字符的 ASCII 碼。
初始值 $\text{hash} = 5381$ 。

等價數學形式：
$\text{hash}_{\text{new}} = (\text{hash}_{\text{old}} \times 33) + c$
迭代公式：
$\text{hash} = \sum_{i=0}^{n-1} c_i \cdot 33^{n-1-i}$

2.4 SHA-256 哈希函數

SHA-256 是一種密碼學哈希函數，其核心步驟包括多項式運算和位操作。以下是其關鍵步驟的顯性表達式：

(1) 初始化工作變量

$\begin{align*} a &= h_0, \quad b = h_1, \quad c = h_2, \quad d = h_3, \\ e &= h_4, \quad f = h_5, \quad g = h_6, \quad h = h_7 \end{align*}$
其中 $h_0 \sim h_7$ 為固定初始值（十六進制）：
$\begin{aligned} h_0 &= 0x6a09e667, \quad h_1 = 0xbb67ae85, \\ h_2 &= 0x3c6ef372, \quad h_3 = 0xa54ff53a, \\ h_4 &= 0x510e527f, \quad h_5 = 0x9b05688c, \\ h_6 &= 0x1f83d9ab, \quad h_7 = 0x5be0cd19 \end{aligned}$

(2) 主壓縮循環

對每個消息塊執行 64 輪迭代，每輪更新工作變量：
$\begin{aligned} T_1 &= h + \Sigma_1(e) + \text{Ch}(e,f,g) + K_t + W_t \\ T_2 &= \Sigma_0(a) + \text{Maj}(a,b,c) \end{aligned}$
其中：

$\Sigma_0(x) = \text{ROTR}^2(x) \oplus \text{ROTR}^{13}(x) \oplus \text{ROTR}^{22}(x)$
$\Sigma_1(x) = \text{ROTR}^6(x) \oplus \text{ROTR}^{11}(x) \oplus \text{ROTR}^{25}(x)$
$\text{Ch}(x,y,z) = (x \land y) \oplus (\lnot x \land z)$
$\text{Maj}(x,y,z) = (x \land y) \oplus (x \land z) \oplus (y \land z)$
$K_t$ ：第 $t$ 輪的常量。
$W_t$ ：消息擴展后的第 $t$ 個字。

(3) 更新哈希值

每輪迭代后更新工作變量：
$\begin{aligned} h &= g, \quad g = f, \quad f = e, \quad e = d + T_1 \\ d &= c, \quad c = b, \quad b = a, \quad a = T_1 + T_2 \end{aligned}$

2.5 MD5 哈希函數

MD5 將輸入分塊處理，每輪進行四組非線性變換。以下是其核心步驟的顯性表達式：

(1) 初始化緩沖區

$\quad B = 0xEFCDAB89, \quad C = 0x98BADCFE, \quad D = 0x10325476$

(2) 主循環（四組 16 輪）

每組使用不同的非線性函數 $F, G, H, I$ ：

第一組（$ F(X,Y,Z) = (X \land Y) \lor (\lnot X \land Z) $）：
$\lll^s (A + F(B,C,D) + X_k + T_i), \quad \text{其中 } s \in \{7,12,17,22\}$
第二組（$ G(X,Y,Z) = (X \land Z) \lor (Y \land \lnot Z) $）：
$\lll^s (D + G(A,B,C) + X_k + T_i), \quad s \in \{5,9,14,20\}$
第三組（$ H(X,Y,Z) = X \oplus Y \oplus Z $）：
$\lll^s (C + H(A,B,C) + X_k + T_i), \quad s \in \{4,11,16,23\}$
第四組（$ I(X,Y,Z) = Y \oplus (X \lor \lnot Z) $）：
$\lll^s (B + I(A,B,C) + X_k + T_i), \quad s \in \{6,10,15,21\}$

(3) 更新緩沖區

每組循環后更新 $A, B, C, D$ ：
$\begin{aligned} A &= A + T, \quad B = B + \text{new value}, \\ C &= C + \text{new value}, \quad D = D + \text{new value} \end{aligned}$

2.6 哈希沖突解決方法的顯性表達式

(1) 鏈地址法（拉鏈法）

對于哈希表 $T$ ，沖突鍵值對存儲在鏈表中：
$T[\text{index}] = \text{LinkedList}(\text{key}_1, \text{key}_2, \ldots)$
其中 $TABLE_SIZE \text{index} = H(\text{key}) \mod \text{TABLE\_SIZE}$ 。

(2) 開放定址法（線性探測）

沖突時按固定步長 $p (i) = i$ 探查：
$TABLE_SIZE \text{index}_i = (H(\text{key}) + i) \mod \text{TABLE\_SIZE}$
直到找到空閑位置。

(3) 雙散列函數法

沖突時使用第二個哈希函數 $H^{'}$ ：
$TABLE_SIZE \text{index}_i = (H(\text{key}) + i \cdot H'(\text{key})) \mod \text{TABLE\_SIZE}$

5. 小結

不同哈希函數的顯性表達式反映了其設計思想和數學特性。例如：

多項式哈希通過多項式展開實現均勻分布。
SHA-256/MD5依賴復雜的位運算和非線性函數保證安全性。
沖突解決方法通過數學公式動態調整存儲位置。

在實際應用中，選擇哈希函數時需權衡 速度、均勻性、抗碰撞性 等因素。

三、哈希碼的用途

3.1 數據檢索

哈希碼通過快速定位數據位置，顯著提升檢索效率。例如：

哈希表：通過哈希函數將鍵映射到數組索引，實現 $O (1)$ 時間復雜度的查找。
數據庫索引：B+樹結合哈希加速數據查詢。

3.2 數據完整性驗證

哈希碼可用于驗證數據是否被篡改。例如：

文件校驗：通過比較文件的哈希碼與已知值判斷文件是否被修改。
數字簽名：對文檔生成哈希碼后加密，接收方解密后驗證哈希碼一致性。

3.3 密碼存儲

哈希碼在密碼學中用于安全存儲密碼。例如：

密碼哈希同步：將用戶密碼的哈希值從本地系統同步到云端。
加鹽哈希：在密碼中添加隨機值（鹽），防止彩虹表攻擊。

3.4 分布式系統

哈希碼在分布式系統中用于數據分片和負載均衡。例如：

一致性哈希：動態分配節點時減少數據遷移。
布隆過濾器：通過多個哈希函數檢測元素是否存在。

四、哈希碼的實現

4.1 C語言實現哈希碼計算

以下是一個基于 DJB2算法 的哈希碼計算函數，該算法以低沖突率和高效性著稱。

#include <stdio.h>
#include <string.h>// 哈希碼計算函數（DJB2算法）
unsigned long hash_code(const char *str) {unsigned long hash = 5381;int c;while ((c = *str++)) {hash = ((hash << 5) + hash) + c; // hash * 33 + c}return hash;
}int main() {const char *test_str = "Hello, World!";unsigned long code = hash_code(test_str);printf("Input: %s\n", test_str);printf("Hash Code: %lu\n", code);return 0;
}

代碼解析：

DJB2算法
- 初始值 hash = 5381 是經驗值，用于優化分布。
- 每次迭代中，hash = ((hash << 5) + hash) + c 等價于 hash * 33 + c，其中 33 是經過實測的最優系數。
- 最終返回的哈希碼為無符號長整型。
編譯與運行
保存為 hash_code.c，使用以下命令編譯并運行：
```
gcc -o hash_code hash_code.c
./hash_code
```

輸出示例：

Input: Hello, World!
Hash Code: 11557940046392859113

4.2 哈希表實現

以下是基于哈希碼的簡單哈希表實現，支持插入和查找操作。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define TABLE_SIZE 100// 鍵值對結構體
typedef struct {char *key;int value;
} KeyValuePair;// 哈希表結構體
typedef struct {KeyValuePair *items[TABLE_SIZE];int size;
} HashTable;// 哈希碼計算函數
unsigned long hash_code(const char *str) {unsigned long hash = 5381;int c;while ((c = *str++)) {hash = ((hash << 5) + hash) + c;}return hash;
}// 插入鍵值對
void insert(HashTable *table, const char *key, int value) {unsigned long index = hash_code(key) % TABLE_SIZE;KeyValuePair *pair = (KeyValuePair *)malloc(sizeof(KeyValuePair));pair->key = strdup(key);pair->value = value;table->items[index] = pair;table->size++;
}// 查找鍵值對
int find(HashTable *table, const char *key) {unsigned long index = hash_code(key) % TABLE_SIZE;if (table->items[index] && strcmp(table->items[index]->key, key) == 0) {return table->items[index]->value;}return -1; // 未找到
}// 釋放哈希表
void free_table(HashTable *table) {for (int i = 0; i < TABLE_SIZE; i++) {if (table->items[i]) {free(table->items[i]->key);free(table->items[i]);}}free(table);
}int main() {HashTable table = {0};insert(&table, "apple", 10);insert(&table, "banana", 20);insert(&table, "orange", 30);printf("apple: %d\n", find(&table, "apple"));   // 輸出: 10printf("banana: %d\n", find(&table, "banana")); // 輸出: 20printf("grape: %d\n", find(&table, "grape"));   // 輸出: -1free_table(&table);return 0;
}