建个网站视频教程,百度seo推广方案,毕业设计网站建设题目,百度论坛首页哈希码#xff1a;原理、用途与实现详解
博主在《在C语言中使用字典》一文中#xff0c;使用哈希来实现键值对的快速检索#xff0c;今天对哈希这一算法工具#xff0c;进行一些深入的研究#xff0c;争取能能做到知其然亦知其所以然。 文章目录 哈希码#xff1a;原理、…哈希码原理、用途与实现详解
博主在《在C语言中使用字典》一文中使用哈希来实现键值对的快速检索今天对哈希这一算法工具进行一些深入的研究争取能能做到知其然亦知其所以然。 文章目录 哈希码原理、用途与实现详解一、哈希码的原理1.1 什么是哈希码1.2 哈希函数的特性1.3 哈希冲突 二、哈希的表达式2.1 通用哈希函数表达式2.2 多项式哈希函数Polynomial Hashing2.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 哈希函数的特性
哈希函数具有以下关键特性 单向性 从原始数据计算哈希码是单向的即无法通过哈希码反推出原始数据。 Hash ( x ) h 但 x ≠ Hash − 1 ( h ) \text{Hash}(x) h \quad \text{但} \quad x \neq \text{Hash}^{-1}(h) Hash(x)h但xHash−1(h) 确定性 相同的输入数据始终生成相同的哈希码。 x 1 x 2 ⇒ Hash ( x 1 ) Hash ( x 2 ) x_1 x_2 \Rightarrow \text{Hash}(x_1) \text{Hash}(x_2) x1x2⇒Hash(x1)Hash(x2) 敏感性 输入的微小变化会导致哈希码的显著改变。 x 1 ∼ x 2 但 Hash ( x 1 ) ≠ Hash ( x 2 ) x_1 \sim x_2 \quad \text{但} \quad \text{Hash}(x_1) \neq \text{Hash}(x_2) x1∼x2但Hash(x1)Hash(x2) 均匀性 哈希码在输出空间中均匀分布减少冲突概率。 ∀ x , y , Hash ( x ) ≈ UniformDistribution \forall x, y, \quad \text{Hash}(x) \approx \text{UniformDistribution} ∀x,y,Hash(x)≈UniformDistribution
1.3 哈希冲突
哈希冲突是指不同的输入生成相同的哈希码。由于哈希函数的输出空间有限而输入空间无限冲突是不可避免的。常见的解决方法包括
链地址法将冲突的键值对存储在链表中。开放寻址法通过探查算法寻找空闲位置。 二、哈希的表达式
哈希函数的显性表达式因具体算法而异以下是几种常见哈希函数的显性表达式及其数学形式
2.1 通用哈希函数表达式
哈希函数的基本形式为 Addr H ( key ) \text{Addr} H(\text{key}) AddrH(key) 其中 key \text{key} key输入数据字符串、数值等。 H H H哈希函数。 Addr \text{Addr} Addr输出的哈希码通常为固定长度的整数或二进制串。
2.2 多项式哈希函数Polynomial Hashing
多项式哈希函数通过将输入字符串视为多项式系数计算其模值 H ( s ) ( ∑ i 0 n − 1 a i ⋅ x i ) m o d m H(s) \left( \sum_{i0}^{n-1} a_i \cdot x^i \right) \mod m H(s)(i0∑n−1ai⋅xi)modm 其中 s a 0 a 1 … a n − 1 s a_0a_1\ldots a_{n-1} sa0a1…an−1输入字符串长度为 n n n。 x x x基数常选质数如 31、37。 m m m模数通常为哈希表大小。 m o d mod mod取模求余运算。
示例 对于字符串 “abc”ASCII 码分别为 97, 98, 99若 x 31 x31 x31, m 1000 m1000 m1000 H ( a b c ) ( 97 ⋅ 31 0 98 ⋅ 31 1 99 ⋅ 31 2 ) m o d 1000 H(abc) (97 \cdot 31^0 98 \cdot 31^1 99 \cdot 31^2) \mod 1000 H(abc)(97⋅31098⋅31199⋅312)mod1000
2.3 DJB2 哈希函数
DJB2 是一种简单高效的哈希算法其显性表达式为 hash ( ( hash ≪ 5 ) hash ) c \text{hash} ((\text{hash} \ll 5) \text{hash}) c hash((hash≪5)hash)c 其中 ≪ \ll ≪左移运算等价于乘以 2 5 32 2^5 32 2532。 c c c当前字符的 ASCII 码。初始值 hash 5381 \text{hash} 5381 hash5381。
等价数学形式 hash new ( hash old × 33 ) c \text{hash}_{\text{new}} (\text{hash}_{\text{old}} \times 33) c hashnew(hashold×33)c 迭代公式 hash ∑ i 0 n − 1 c i ⋅ 33 n − 1 − i \text{hash} \sum_{i0}^{n-1} c_i \cdot 33^{n-1-i} hashi0∑n−1ci⋅33n−1−i 2.4 SHA-256 哈希函数
SHA-256 是一种密码学哈希函数其核心步骤包括多项式运算和位操作。以下是其关键步骤的显性表达式
(1) 初始化工作变量 a h 0 , b h 1 , c h 2 , d h 3 , e h 4 , f h 5 , g h 6 , h h 7 \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*} aeh0,bh1,ch2,dh3,h4,fh5,gh6,hh7 其中 h 0 ∼ h 7 h_0 \sim h_7 h0∼h7 为固定初始值十六进制 h 0 0 x 6 a 09 e 667 , h 1 0 x b b 67 a e 85 , h 2 0 x 3 c 6 e f 372 , h 3 0 x a 54 f f 53 a , h 4 0 x 510 e 527 f , h 5 0 x 9 b 05688 c , h 6 0 x 1 f 83 d 9 a b , h 7 0 x 5 b e 0 c d 19 \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} h0h2h4h60x6a09e667,h10xbb67ae85,0x3c6ef372,h30xa54ff53a,0x510e527f,h50x9b05688c,0x1f83d9ab,h70x5be0cd19
(2) 主压缩循环
对每个消息块执行 64 轮迭代每轮更新工作变量 T 1 h Σ 1 ( e ) Ch ( e , f , g ) K t W t T 2 Σ 0 ( a ) Maj ( a , b , c ) \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} T1T2hΣ1(e)Ch(e,f,g)KtWtΣ0(a)Maj(a,b,c) 其中 Σ 0 ( x ) ROTR 2 ( x ) ⊕ ROTR 13 ( x ) ⊕ ROTR 22 ( x ) \Sigma_0(x) \text{ROTR}^2(x) \oplus \text{ROTR}^{13}(x) \oplus \text{ROTR}^{22}(x) Σ0(x)ROTR2(x)⊕ROTR13(x)⊕ROTR22(x) Σ 1 ( x ) ROTR 6 ( x ) ⊕ ROTR 11 ( x ) ⊕ ROTR 25 ( x ) \Sigma_1(x) \text{ROTR}^6(x) \oplus \text{ROTR}^{11}(x) \oplus \text{ROTR}^{25}(x) Σ1(x)ROTR6(x)⊕ROTR11(x)⊕ROTR25(x) Ch ( x , y , z ) ( x ∧ y ) ⊕ ( ¬ x ∧ z ) \text{Ch}(x,y,z) (x \land y) \oplus (\lnot x \land z) Ch(x,y,z)(x∧y)⊕(¬x∧z) Maj ( x , y , z ) ( x ∧ y ) ⊕ ( x ∧ z ) ⊕ ( y ∧ z ) \text{Maj}(x,y,z) (x \land y) \oplus (x \land z) \oplus (y \land z) Maj(x,y,z)(x∧y)⊕(x∧z)⊕(y∧z) K t K_t Kt第 t t t 轮的常量。 W t W_t Wt消息扩展后的第 t t t 个字。
(3) 更新哈希值
每轮迭代后更新工作变量 h g , g f , f e , e d T 1 d c , c b , b a , a T 1 T 2 \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} hdg,gf,fe,edT1c,cb,ba,aT1T2 2.5 MD5 哈希函数
MD5 将输入分块处理每轮进行四组非线性变换。以下是其核心步骤的显性表达式
(1) 初始化缓冲区 A 0 x 67452301 , B 0 x E F C D A B 89 , C 0 x 98 B A D C F E , D 0 x 10325476 A 0x67452301, \quad B 0xEFCDAB89, \quad C 0x98BADCFE, \quad D 0x10325476 A0x67452301,B0xEFCDAB89,C0x98BADCFE,D0x10325476
(2) 主循环四组 16 轮
每组使用不同的非线性函数 F , G , H , I F, G, H, I F,G,H,I
第一组$ F(X,Y,Z) (X \land Y) \lor (\lnot X \land Z) $ T D ⋘ s ( A F ( B , C , D ) X k T i ) , 其中 s ∈ { 7 , 12 , 17 , 22 } T D \lll^s (A F(B,C,D) X_k T_i), \quad \text{其中 } s \in \{7,12,17,22\} TD⋘s(AF(B,C,D)XkTi),其中 s∈{7,12,17,22}第二组$ G(X,Y,Z) (X \land Z) \lor (Y \land \lnot Z) $ T C ⋘ s ( D G ( A , B , C ) X k T i ) , s ∈ { 5 , 9 , 14 , 20 } T C \lll^s (D G(A,B,C) X_k T_i), \quad s \in \{5,9,14,20\} TC⋘s(DG(A,B,C)XkTi),s∈{5,9,14,20}第三组$ H(X,Y,Z) X \oplus Y \oplus Z $ T B ⋘ s ( C H ( A , B , C ) X k T i ) , s ∈ { 4 , 11 , 16 , 23 } T B \lll^s (C H(A,B,C) X_k T_i), \quad s \in \{4,11,16,23\} TB⋘s(CH(A,B,C)XkTi),s∈{4,11,16,23}第四组$ I(X,Y,Z) Y \oplus (X \lor \lnot Z) $ T A ⋘ s ( B I ( A , B , C ) X k T i ) , s ∈ { 6 , 10 , 15 , 21 } T A \lll^s (B I(A,B,C) X_k T_i), \quad s \in \{6,10,15,21\} TA⋘s(BI(A,B,C)XkTi),s∈{6,10,15,21}
(3) 更新缓冲区
每组循环后更新 A , B , C , D A, B, C, D A,B,C,D A A T , B B new value , C C new value , D D new value \begin{aligned} A A T, \quad B B \text{new value}, \\ C C \text{new value}, \quad D D \text{new value} \end{aligned} ACAT,BBnew value,Cnew value,DDnew value
2.6 哈希冲突解决方法的显性表达式
(1) 链地址法拉链法
对于哈希表 T T T冲突键值对存储在链表中 T [ index ] LinkedList ( key 1 , key 2 , … ) T[\text{index}] \text{LinkedList}(\text{key}_1, \text{key}_2, \ldots) T[index]LinkedList(key1,key2,…) 其中 index H ( key ) m o d TABLE_SIZE \text{index} H(\text{key}) \mod \text{TABLE\_SIZE} indexH(key)modTABLE_SIZE。
(2) 开放定址法线性探测
冲突时按固定步长 p ( i ) i p(i) i p(i)i 探查 index i ( H ( key ) i ) m o d TABLE_SIZE \text{index}_i (H(\text{key}) i) \mod \text{TABLE\_SIZE} indexi(H(key)i)modTABLE_SIZE 直到找到空闲位置。
(3) 双散列函数法
冲突时使用第二个哈希函数 H ′ H H′ index i ( H ( key ) i ⋅ H ′ ( key ) ) m o d TABLE_SIZE \text{index}_i (H(\text{key}) i \cdot H(\text{key})) \mod \text{TABLE\_SIZE} indexi(H(key)i⋅H′(key))modTABLE_SIZE
5. 小结
不同哈希函数的显性表达式反映了其设计思想和数学特性。例如
多项式哈希通过多项式展开实现均匀分布。SHA-256/MD5依赖复杂的位运算和非线性函数保证安全性。冲突解决方法通过数学公式动态调整存储位置。
在实际应用中选择哈希函数时需权衡 速度、均匀性、抗碰撞性 等因素。 三、哈希码的用途
3.1 数据检索
哈希码通过快速定位数据位置显著提升检索效率。例如
哈希表通过哈希函数将键映射到数组索引实现 O ( 1 ) O(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: 115579400463928591134.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;
}代码解析 哈希表结构 使用数组 items 存储键值对指针。TABLE_SIZE 定义哈希表大小。 插入与查找 插入时通过哈希码取模定位数组索引。查找时直接通过哈希码定位索引并比较键值。 冲突处理 当多个键映射到同一索引时当前实现会覆盖旧值。实际应用中可通过链地址法链表或开放寻址法解决冲突。 五、总结
哈希码是计算机科学中不可或缺的技术其核心价值在于高效的数据映射与快速检索。通过合理设计哈希函数和冲突解决策略可以显著提升系统的性能与安全性。本文通过理论讲解和代码实现展示了哈希码的原理、用途及其实现方式。希望读者能通过本文深入理解哈希码的本质并在实际开发中灵活应用。 研究学习不易点赞易。 工作生活不易收藏易点收藏不迷茫
