《Hello 算法》哈希算法ハッシュアルゴリズム精讲从哈希函数设计到素数取模与内置哈希实现【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇基于《Hello 算法》日文版「ハッシュアルゴリズム」章节hash_algorithm.md编写系统讲解哈希表性能的源头——哈希函数与哈希算法如何通过目标约束、简单哈希构造与大素数取模技巧降低哈希冲突并延伸到 MD5/SHA 系列密码学哈希与各语言内置哈希机制。读完本文你将理解index hash(key) % capacity每一环的设计动机能够评判一个哈希算法的好坏并掌握在 Python、Java、C、Rust 等语言中正确使用内置哈希与自定义对象哈希的方法。为什么关注哈希算法冲突处理≠冲突减少在本系列前两节中我们分别介绍了哈希表hash_map.md与哈希冲突的两种处理方案——链式地址法与开放寻址法hash_collision.md。但无论采用链式法还是开放寻址法它们能保证的只是冲突发生时哈希表依然可用而无法从根源上减少哈希冲突本身。冲突一旦过于频繁哈希表性能会急剧劣化。以链式哈希表为例对应源码 hash_map_chaining.py 与 hash_map_chaining.c理想情况键值对均匀散布于各个桶bucket每次查找只命中单个元素接近 $O(1)$最坏情况所有键值对坍缩到同一个桶中退化为在链表/红黑树上线性查找时间复杂度劣化至 $O(n)$。这正对应上方图片所展示的两种极端分布。而决定键值对落入哪个桶的关键正是哈希函数本身。回顾哈希表的寻址公式index hash(key) % capacity当哈希表容量capacity固定时真正决定输出值的是哈希算法hash()因此它也间接决定了键值对在表中的分布形态。要降低哈希冲突的发生概率就应该把设计重心放在哈希算法hash()上。仓库中的简易哈希表实现也印证了这一链路例如 array_hash_map.c 里hashFunc(int key)先直接返回key % MAX_SIZE得到桶下标而 hash_map_chaining.py 的hash_func同样先对key取模再落桶。哈希算法的三大基本目标为了成就快速且稳定的哈希表数据结构哈希算法必须具备以下特征确定性決定性同样的输入必须始终产生同样的输出这是哈希表可靠性的前提——否则同一把key每次算出的桶下标都不一致数据将无法被找回高效率高効率哈希值计算过程必须足够快计算开销越小哈希表的实用价值越高均匀分布均一分布哈希算法应使键值对在哈希表内尽量均匀铺开分布越均匀哈希冲突概率越低。哈希算法不止用于哈希表除哈希表实现外哈希算法还被广泛用于其他领域密码存储パスワード保存系统不直接保存明文密码而是保存其哈希值用户输入密码后系统重新计算哈希并与存储值比对一致即判定正确数据完整性校验データ完全性検査发送方计算数据哈希值并随数据一同发出接收方重新计算收到的数据哈希并与携带的哈希比对两者一致即认为数据完整、未被篡改。而在密码学场景中为防止由哈希值反推明文密码这类逆向攻击哈希算法还被要求具备更高等级的安全属性单向性一方向性无法从哈希值反推出输入数据的任何有效信息抗碰撞性耐衝突性要找到两个不同输入却产生相同哈希值在计算上极其困难雪崩效应アバランシェ効果输入发生哪怕一丁点变化输出也应产生巨大且不可预测的改变。需要特别指出均匀分布与抗碰撞性是两个相互独立的概念。满足均匀分布并不代表满足抗碰撞性。例如当输入key均匀随机时key % 100能产生均匀的输出分布但这一算法过于简单——只要后两位相同的key都会映射到同一个输出攻击者可轻易从哈希值反推出可用的key导致密码被破解。简单哈希算法的四种构造与源码实现哈希算法的设计是一个需多方权衡的复杂问题。但在要求不高的场合设计几种简单的哈希算法同样可行。本仓库在各语言下提供了统一实现以 Python 版 simple_hash.pyC 版见 simple_hash.c为例分别实现了四种构造加法哈希加法ハッシュ累加输入各字符的 ASCII 码以总和为哈希值乘法哈希乗法ハッシュ利用乘法的非相关性每一轮先乘以常数再累加当前字符的 ASCII 码使结果更分散异或哈希XOR ハッシュ将输入数据的各个元素通过 XOR 运算累积成一个哈希值旋转哈希回転ハッシュ每轮累加一个字符的 ASCII 码前先对已有哈希值做旋转左移与右移的异或组合以充分打散位模式。以下为文档内嵌展示的旋转哈希核心片段rot_hash在 simple_hash.py 中可运行def rot_hash(key: str) - int: 旋转哈希 hash 0 modulus 1000000007 for c in key: hash (hash 4) ^ (hash 28) ^ ord(c) return hash % modulusC 语言实现中的对应逻辑simple_hash.c几乎逐行同构/* 旋转哈希 */ int rotHash(char *key) { long long hash 0; const int MODULUS 1000000007; for (int i 0; i strlen(key); i) { hash ((hash 4) ^ (hash 28) ^ (unsigned char)key[i]) % MODULUS; } return (int)hash; }观察可见上述每种简单哈希的最后一步都是对一个大素数 $1000000007$ 取模从而把哈希值收敛到合理范围内。这里引出一个值得深究的问题为什么特别强调用素数取模用合数取模又有什么缺陷为什么模数要用大素数先给出结论采用大素数作为模数能最大限度地保证哈希值分布均匀。素数与其他数不存在公因数可削减取模运算带来的周期性规律从而更容易避开哈希冲突。以合数 $9$ 作为模数进行推演由于 $9$ 能被 $3$ 整除任何能被 $3$ 整除的key都会只被映射到 $0, 3, 6$ 三个哈希值上$$ \begin{aligned} \text{modulus} 9 \newline \text{key} { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, \dots } \newline \text{hash} { 0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6,\dots } \end{aligned} $$如果输入key恰好呈这种等差数列分布哈希值就会出现明显偏斜哈希冲突进一步加剧。而把模数换成素数 $13$ 后由于key与modulus不再存在公因数输出哈希值的均匀性显著改善$$ \begin{aligned} \text{modulus} 13 \newline \text{key} { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, \dots } \newline \text{hash} { 0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, \dots } \end{aligned} $$补充一点若可保证key本身随机且均匀分布那么模数选素数还是合数结果都均匀问题出在当key的分布带有某种周期性时合数取模更容易放大偏斜。因此在工程惯例中通常选用尽量大的素数作模数以尽可能消除周期性规律增强哈希算法的健壮性。文档章节末尾的 summary.md 也再次概括了这一要点哈希算法通常以一个大素数为模从而在最大程度上保证哈希值均匀分布、减少哈希冲突。从脆弱的简单哈希到主流密码学哈希上文介绍的简单哈希算法普遍比较脆弱远未达到哈希算法的设计目标。例如加法与 XOR 都满足交换律因此加法哈希与 XOR 哈希无法区分内容相同、顺序不同的字符串如abc与cba既会加剧冲突也可能引发安全隐患。这也是仓库将这些示例刻意保留为教学用例、而真实哈希表普遍采用工业级哈希函数的原因。实践中更常见的选择是MD5、SHA-1、SHA-2、SHA-3 等标准哈希算法它们都能把任意长度的输入数据映射为固定长度的哈希值。近一个世纪以来哈希算法持续演进一部分研究者致力于提升性能另一部分研究者与攻击者则不断寻找其安全弱点。下表汇总了实际应用中常见的哈希算法自原文档完整保留MD5SHA-1SHA-2SHA-3发布年份1992199520022008输出长度128 bit160 bit256/512 bit224/256/384/512 bit哈希冲突多多极少极少安全等级低已被成功攻击低已被成功攻击高高用途已废弃但仍用于数据完整性校验已废弃加密货币交易校验、数字签名等可作为 SHA-2 的替代要点归纳MD5 与 SHA-1均被多次成功攻击已退出各类安全用途MD5 目前仍见于文件完整性校验等非对抗场景SHA-2 系列尤其 SHA-256是目前最安全的哈希算法之一至今没有成功的攻击案例被大量安全应用与协议采用SHA-3相对 SHA-2 实现成本更低、计算效率更高但当前普及度仍不及 SHA-2 系列。各语言对数据结构的内置哈希如前所述哈希表的key可以是整数、小数、字符串等多种类型。主流编程语言通常会为这些内置类型提供哈希算法供哈希表计算桶下标时使用。下面以仓库中日文版配套代码built_in_hash.py 等为蓝本逐语言还原内置哈希的调用方式与输出特征。通用规律整数与布尔值的哈希值通常就是其自身或其规范形式浮点数与字符串的哈希计算相对复杂元组/数组等复合类型的哈希值是对各元素哈希再做组合的结果对象的哈希值一般基于其内存地址生成若重写对象的哈希方法则可实现基于内容的哈希。提示内置哈希值计算函数的定义与方式因编程语言而异同一份数据在不同语言、甚至同语言不同运行环境下得到的数值都可能不同切勿跨语言依赖具体数值。Pythonnum 3 hash_num hash(num) # 整数 3 的哈希值为 3 bol True hash_bol hash(bol) # 布尔值 True 的哈希值为 1 dec 3.14159 hash_dec hash(dec) # 小数 3.14159 的哈希值为 326484311674566659 str Hello アルゴリズム hash_str hash(str) # 字符串 Hello アルゴリズム 的哈希值为 4617003410720528961 tup (12836, シャオハ) hash_tup hash(tup) # 元组 (12836, シャオハ) 的哈希值为 1029005403108185979 obj ListNode(0) hash_obj hash(obj) # 节点对象 ListNode object at 0x1058fd810 的哈希值为 274267521Cint num 3; size_t hashNum hashint()(num); // 整数 3 的哈希值为 3 bool bol true; size_t hashBol hashbool()(bol); // 布尔值 1 的哈希值为 1 double dec 3.14159; size_t hashDec hashdouble()(dec); // 小数 3.14159 的哈希值为 4614256650576692846 string str Hello アルゴリズム; size_t hashStr hashstring()(str); // 字符串 Hello アルゴリズム 的哈希值为 15466937326284535026 // C 中内置 std::hash() 仅为基本数据类型提供哈希值计算 // 数组与自定义对象的哈希值需自行实现Javaint num 3; int hashNum Integer.hashCode(num); // 整数 3 的哈希值为 3 boolean bol true; int hashBol Boolean.hashCode(bol); // 布尔值 true 的哈希值为 1231 double dec 3.14159; int hashDec Double.hashCode(dec); // 小数 3.14159 的哈希值为 -1340954729 String str Hello アルゴリズム; int hashStr str.hashCode(); // 字符串 Hello アルゴリズム 的哈希值为 -727081396 Object[] arr { 12836, シャオハ }; int hashTup Arrays.hashCode(arr); // 数组 [12836, シャオハ] 的哈希值为 1151158 ListNode obj new ListNode(0); int hashObj obj.hashCode(); // 节点对象 utils.ListNode7dc5e7b4 的哈希值为 2110121908C#int num 3; int hashNum num.GetHashCode(); // 整数 3 的哈希值为 3; bool bol true; int hashBol bol.GetHashCode(); // 布尔值 true 的哈希值为 1; double dec 3.14159; int hashDec dec.GetHashCode(); // 小数 3.14159 的哈希值为 -1340954729; string str Hello アルゴリズム; int hashStr str.GetHashCode(); // 字符串 Hello アルゴリズム 的哈希值为 -586107568; object[] arr [12836, シャオハ]; int hashTup arr.GetHashCode(); // 数组 [12836, シャオハ] 的哈希值为 42931033; ListNode obj new(0); int hashObj obj.GetHashCode(); // 节点对象 0 的哈希值为 39053774;Go / JavaScript / TypeScript / C无内置哈希// Go 不提供内置的 hash code 函数// JavaScript 不提供内置的 hash code 函数// TypeScript 不提供内置的 hash code 函数// C 不提供内置的 hash code 函数对于这四类语言哈希值通常需借助语言标准库中的哈希表实现内部自动完成如 Go 的map、JS 的Map或自行实现/选用第三方哈希函数。Swiftlet num 3 let hashNum num.hashValue // 整数 3 的哈希值为 9047044699613009734 let bol true let hashBol bol.hashValue // 布尔值 true 的哈希值为 -4431640247352757451 let dec 3.14159 let hashDec dec.hashValue // 小数 3.14159 的哈希值为 -2465384235396674631 let str Hello アルゴリズム let hashStr str.hashValue // 字符串 Hello アルゴリズム 的哈希值为 -7850626797806988787 let arr [AnyHashable(12836), AnyHashable(シャオハ)] let hashTup arr.hashValue // 数组 [AnyHashable(12836), AnyHashable(シャオハ)] 的哈希值为 -2308633508154532996 let obj ListNode(x: 0) let hashObj obj.hashValue // 节点对象 utils.ListNode 的哈希值为 -2434780518035996159Dartint num 3; int hashNum num.hashCode; // 整数 3 的哈希值为 34803 bool bol true; int hashBol bol.hashCode; // 布尔值 true 的哈希值为 1231 double dec 3.14159; int hashDec dec.hashCode; // 小数 3.14159 的哈希值为 2570631074981783 String str Hello アルゴリズム; int hashStr str.hashCode; // 字符串 Hello アルゴリズム 的哈希值为 468167534 List arr [12836, シャオハ]; int hashArr arr.hashCode; // 数组 [12836, シャオハ] 的哈希值为 976512528 ListNode obj new ListNode(0); int hashObj obj.hashCode; // 节点对象 Instance of ListNode 的哈希值为 1033450432Rustuse std::collections::hash_map::DefaultHasher; use std::hash::{Hash, Hasher}; let num 3; let mut num_hasher DefaultHasher::new(); num.hash(mut num_hasher); let hash_num num_hasher.finish(); // 整数 3 的哈希值为 568126464209439262 let bol true; let mut bol_hasher DefaultHasher::new(); bol.hash(mut bol_hasher); let hash_bol bol_hasher.finish(); // 布尔值 true 的哈希值为 4952851536318644461 let dec: f32 3.14159; let mut dec_hasher DefaultHasher::new(); dec.to_bits().hash(mut dec_hasher); let hash_dec dec_hasher.finish(); // 小数 3.14159 的哈希值为 2566941990314602357 let str Hello アルゴリズム; let mut str_hasher DefaultHasher::new(); str.hash(mut str_hasher); let hash_str str_hasher.finish(); // 字符串 Hello アルゴリズム 的哈希值为 16092673739211250988 let arr (12836, シャオハ); let mut tup_hasher DefaultHasher::new(); arr.hash(mut tup_hasher); let hash_tup tup_hasher.finish(); // 元组 (12836, シャオハ) 的哈希值为 1885128010422702749 let node ListNode::new(42); let mut hasher DefaultHasher::new(); node.borrow().val.hash(mut hasher); let hash hasher.finish(); // 节点对象 RefCell { value: ListNode { val: 42, next: None } } 的哈希值为 15387811073369036852Kotlinval num 3 val hashNum num.hashCode() // 整数 3 的哈希值为 3 val bol true val hashBol bol.hashCode() // 布尔值 true 的哈希值为 1231 val dec 3.14159 val hashDec dec.hashCode() // 小数 3.14159 的哈希值为 -1340954729 val str Hello アルゴリズム val hashStr str.hashCode() // 字符串 Hello アルゴリズム 的哈希值为 -727081396 val arr arrayOfAny(12836, シャオハ) val hashTup arr.hashCode() // 数组 [12836, シャオハ] 的哈希值为 189568618 val obj ListNode(0) val hashObj obj.hashCode() // 节点对象 utils.ListNode1d81eb93 的哈希值为 495053715Rubynum 3 hash_num num.hash # 整数 3 的哈希值为 -4385856518450339636 bol true hash_bol bol.hash # 布尔值 true 的哈希值为 -1617938112149317027 dec 3.14159 hash_dec dec.hash # 小数 3.14159 的哈希值为 -1479186995943067893 str Hello アルゴリズム hash_str str.hash # 字符串 Hello アルゴリズム 的哈希值为 -4075943250025831763 tup [12836, シャオハ] hash_tup tup.hash # 元组 (12836, シャオハ) 的哈希值为 1999544809202288822 obj ListNode.new(0) hash_obj obj.hash # 节点对象 #ListNode:0x000078133140ab70 的哈希值为 4302940560806366381上述完整可运行示例分别存放于日文版配套代码目录例如 built_in_hash.cpp、built_in_hash.java、built_in_hash.py 等Go、JS、TS、C 因不提供内置 hash code 接口而未生成对应示例文件。可变与不可变哪些对象才能当 key很多编程语言规定只有不可变对象才能作为哈希表的key。设想若用列表动态数组作key其内容一旦变化哈希值也会随之改变那么原先存入的value便再也无法通过原key找到——这正是哈希表实现普遍要求键具有不可变性的根本原因。另一方面自定义对象如链表节点的成员变量通常是可变的却依然可哈希。这是因为对象的哈希值往往基于其内存地址生成只要对象内容变化而内存地址不变其哈希值就保持不变。因此这类对象进入哈希表后不会因为内容被修改而丢失。彩蛋为什么每次运行哈希值都不一样细心的读者可能会发现同一个字符串哈希在不同控制台/多次运行中输出的数值并不一致。这是因为 Python 解释器在每次启动时都会向字符串哈希函数注入一个随机的 salt 值。这一机制可以有效防御 HashDoS哈希洪水拒绝服务攻击——攻击者本可精心构造大量同哈希字符串把哈希表拖入 $O(n)$ 的最坏情形随机 salt 的存在使这类预构造攻击失去确定性基础从而显著提升哈希算法的安全性。Go、Rust 等语言的默认哈希器同样采用类似的随机化种子策略如本文 Rust 示例中的DefaultHasher。小结与延伸阅读哈希冲突的治本之道在于哈希算法设计确定性、高效率、均匀分布是三项基本要求密码学场景还需单向性、抗碰撞性与雪崩效应四种简单哈希加法/乘法/XOR/旋转演示了构造思路其共性收尾是对一个大素数如 $1000000007$取模以素数模数削弱周期性偏斜生产环境通常使用 MD5已降级为完整性校验、SHA-1已废弃与 SHA-2/SHA-3安全可靠等标准算法语言内置哈希的对象约束与进程级随机化 salt 是使用哈希表时必须理解的边界条件。若想进一步巩固建议阅读同一章节下的 hash_map.md哈希表原理与基本操作、hash_collision.md链式与开放寻址两种冲突处理以及 summary.md要点回顾与 QA并在本地运行 simple_hash.py 与 built_in_hash.py 亲手验证上述全部结论。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
《Hello 算法》哈希算法（ハッシュアルゴリズム）精讲：从哈希函数设计到素数取模与内置哈希实现
《Hello 算法》哈希算法ハッシュアルゴリズム精讲从哈希函数设计到素数取模与内置哈希实现【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇基于《Hello 算法》日文版「ハッシュアルゴリズム」章节hash_algorithm.md编写系统讲解哈希表性能的源头——哈希函数与哈希算法如何通过目标约束、简单哈希构造与大素数取模技巧降低哈希冲突并延伸到 MD5/SHA 系列密码学哈希与各语言内置哈希机制。读完本文你将理解index hash(key) % capacity每一环的设计动机能够评判一个哈希算法的好坏并掌握在 Python、Java、C、Rust 等语言中正确使用内置哈希与自定义对象哈希的方法。为什么关注哈希算法冲突处理≠冲突减少在本系列前两节中我们分别介绍了哈希表hash_map.md与哈希冲突的两种处理方案——链式地址法与开放寻址法hash_collision.md。但无论采用链式法还是开放寻址法它们能保证的只是冲突发生时哈希表依然可用而无法从根源上减少哈希冲突本身。冲突一旦过于频繁哈希表性能会急剧劣化。以链式哈希表为例对应源码 hash_map_chaining.py 与 hash_map_chaining.c理想情况键值对均匀散布于各个桶bucket每次查找只命中单个元素接近 $O(1)$最坏情况所有键值对坍缩到同一个桶中退化为在链表/红黑树上线性查找时间复杂度劣化至 $O(n)$。这正对应上方图片所展示的两种极端分布。而决定键值对落入哪个桶的关键正是哈希函数本身。回顾哈希表的寻址公式index hash(key) % capacity当哈希表容量capacity固定时真正决定输出值的是哈希算法hash()因此它也间接决定了键值对在表中的分布形态。要降低哈希冲突的发生概率就应该把设计重心放在哈希算法hash()上。仓库中的简易哈希表实现也印证了这一链路例如 array_hash_map.c 里hashFunc(int key)先直接返回key % MAX_SIZE得到桶下标而 hash_map_chaining.py 的hash_func同样先对key取模再落桶。哈希算法的三大基本目标为了成就快速且稳定的哈希表数据结构哈希算法必须具备以下特征确定性決定性同样的输入必须始终产生同样的输出这是哈希表可靠性的前提——否则同一把key每次算出的桶下标都不一致数据将无法被找回高效率高効率哈希值计算过程必须足够快计算开销越小哈希表的实用价值越高均匀分布均一分布哈希算法应使键值对在哈希表内尽量均匀铺开分布越均匀哈希冲突概率越低。哈希算法不止用于哈希表除哈希表实现外哈希算法还被广泛用于其他领域密码存储パスワード保存系统不直接保存明文密码而是保存其哈希值用户输入密码后系统重新计算哈希并与存储值比对一致即判定正确数据完整性校验データ完全性検査发送方计算数据哈希值并随数据一同发出接收方重新计算收到的数据哈希并与携带的哈希比对两者一致即认为数据完整、未被篡改。而在密码学场景中为防止由哈希值反推明文密码这类逆向攻击哈希算法还被要求具备更高等级的安全属性单向性一方向性无法从哈希值反推出输入数据的任何有效信息抗碰撞性耐衝突性要找到两个不同输入却产生相同哈希值在计算上极其困难雪崩效应アバランシェ効果输入发生哪怕一丁点变化输出也应产生巨大且不可预测的改变。需要特别指出均匀分布与抗碰撞性是两个相互独立的概念。满足均匀分布并不代表满足抗碰撞性。例如当输入key均匀随机时key % 100能产生均匀的输出分布但这一算法过于简单——只要后两位相同的key都会映射到同一个输出攻击者可轻易从哈希值反推出可用的key导致密码被破解。简单哈希算法的四种构造与源码实现哈希算法的设计是一个需多方权衡的复杂问题。但在要求不高的场合设计几种简单的哈希算法同样可行。本仓库在各语言下提供了统一实现以 Python 版 simple_hash.pyC 版见 simple_hash.c为例分别实现了四种构造加法哈希加法ハッシュ累加输入各字符的 ASCII 码以总和为哈希值乘法哈希乗法ハッシュ利用乘法的非相关性每一轮先乘以常数再累加当前字符的 ASCII 码使结果更分散异或哈希XOR ハッシュ将输入数据的各个元素通过 XOR 运算累积成一个哈希值旋转哈希回転ハッシュ每轮累加一个字符的 ASCII 码前先对已有哈希值做旋转左移与右移的异或组合以充分打散位模式。以下为文档内嵌展示的旋转哈希核心片段rot_hash在 simple_hash.py 中可运行def rot_hash(key: str) - int: 旋转哈希 hash 0 modulus 1000000007 for c in key: hash (hash 4) ^ (hash 28) ^ ord(c) return hash % modulusC 语言实现中的对应逻辑simple_hash.c几乎逐行同构/* 旋转哈希 */ int rotHash(char *key) { long long hash 0; const int MODULUS 1000000007; for (int i 0; i strlen(key); i) { hash ((hash 4) ^ (hash 28) ^ (unsigned char)key[i]) % MODULUS; } return (int)hash; }观察可见上述每种简单哈希的最后一步都是对一个大素数 $1000000007$ 取模从而把哈希值收敛到合理范围内。这里引出一个值得深究的问题为什么特别强调用素数取模用合数取模又有什么缺陷为什么模数要用大素数先给出结论采用大素数作为模数能最大限度地保证哈希值分布均匀。素数与其他数不存在公因数可削减取模运算带来的周期性规律从而更容易避开哈希冲突。以合数 $9$ 作为模数进行推演由于 $9$ 能被 $3$ 整除任何能被 $3$ 整除的key都会只被映射到 $0, 3, 6$ 三个哈希值上$$ \begin{aligned} \text{modulus} 9 \newline \text{key} { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, \dots } \newline \text{hash} { 0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6,\dots } \end{aligned} $$如果输入key恰好呈这种等差数列分布哈希值就会出现明显偏斜哈希冲突进一步加剧。而把模数换成素数 $13$ 后由于key与modulus不再存在公因数输出哈希值的均匀性显著改善$$ \begin{aligned} \text{modulus} 13 \newline \text{key} { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, \dots } \newline \text{hash} { 0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, \dots } \end{aligned} $$补充一点若可保证key本身随机且均匀分布那么模数选素数还是合数结果都均匀问题出在当key的分布带有某种周期性时合数取模更容易放大偏斜。因此在工程惯例中通常选用尽量大的素数作模数以尽可能消除周期性规律增强哈希算法的健壮性。文档章节末尾的 summary.md 也再次概括了这一要点哈希算法通常以一个大素数为模从而在最大程度上保证哈希值均匀分布、减少哈希冲突。从脆弱的简单哈希到主流密码学哈希上文介绍的简单哈希算法普遍比较脆弱远未达到哈希算法的设计目标。例如加法与 XOR 都满足交换律因此加法哈希与 XOR 哈希无法区分内容相同、顺序不同的字符串如abc与cba既会加剧冲突也可能引发安全隐患。这也是仓库将这些示例刻意保留为教学用例、而真实哈希表普遍采用工业级哈希函数的原因。实践中更常见的选择是MD5、SHA-1、SHA-2、SHA-3 等标准哈希算法它们都能把任意长度的输入数据映射为固定长度的哈希值。近一个世纪以来哈希算法持续演进一部分研究者致力于提升性能另一部分研究者与攻击者则不断寻找其安全弱点。下表汇总了实际应用中常见的哈希算法自原文档完整保留MD5SHA-1SHA-2SHA-3发布年份1992199520022008输出长度128 bit160 bit256/512 bit224/256/384/512 bit哈希冲突多多极少极少安全等级低已被成功攻击低已被成功攻击高高用途已废弃但仍用于数据完整性校验已废弃加密货币交易校验、数字签名等可作为 SHA-2 的替代要点归纳MD5 与 SHA-1均被多次成功攻击已退出各类安全用途MD5 目前仍见于文件完整性校验等非对抗场景SHA-2 系列尤其 SHA-256是目前最安全的哈希算法之一至今没有成功的攻击案例被大量安全应用与协议采用SHA-3相对 SHA-2 实现成本更低、计算效率更高但当前普及度仍不及 SHA-2 系列。各语言对数据结构的内置哈希如前所述哈希表的key可以是整数、小数、字符串等多种类型。主流编程语言通常会为这些内置类型提供哈希算法供哈希表计算桶下标时使用。下面以仓库中日文版配套代码built_in_hash.py 等为蓝本逐语言还原内置哈希的调用方式与输出特征。通用规律整数与布尔值的哈希值通常就是其自身或其规范形式浮点数与字符串的哈希计算相对复杂元组/数组等复合类型的哈希值是对各元素哈希再做组合的结果对象的哈希值一般基于其内存地址生成若重写对象的哈希方法则可实现基于内容的哈希。提示内置哈希值计算函数的定义与方式因编程语言而异同一份数据在不同语言、甚至同语言不同运行环境下得到的数值都可能不同切勿跨语言依赖具体数值。Pythonnum 3 hash_num hash(num) # 整数 3 的哈希值为 3 bol True hash_bol hash(bol) # 布尔值 True 的哈希值为 1 dec 3.14159 hash_dec hash(dec) # 小数 3.14159 的哈希值为 326484311674566659 str Hello アルゴリズム hash_str hash(str) # 字符串 Hello アルゴリズム 的哈希值为 4617003410720528961 tup (12836, シャオハ) hash_tup hash(tup) # 元组 (12836, シャオハ) 的哈希值为 1029005403108185979 obj ListNode(0) hash_obj hash(obj) # 节点对象 ListNode object at 0x1058fd810 的哈希值为 274267521Cint num 3; size_t hashNum hashint()(num); // 整数 3 的哈希值为 3 bool bol true; size_t hashBol hashbool()(bol); // 布尔值 1 的哈希值为 1 double dec 3.14159; size_t hashDec hashdouble()(dec); // 小数 3.14159 的哈希值为 4614256650576692846 string str Hello アルゴリズム; size_t hashStr hashstring()(str); // 字符串 Hello アルゴリズム 的哈希值为 15466937326284535026 // C 中内置 std::hash() 仅为基本数据类型提供哈希值计算 // 数组与自定义对象的哈希值需自行实现Javaint num 3; int hashNum Integer.hashCode(num); // 整数 3 的哈希值为 3 boolean bol true; int hashBol Boolean.hashCode(bol); // 布尔值 true 的哈希值为 1231 double dec 3.14159; int hashDec Double.hashCode(dec); // 小数 3.14159 的哈希值为 -1340954729 String str Hello アルゴリズム; int hashStr str.hashCode(); // 字符串 Hello アルゴリズム 的哈希值为 -727081396 Object[] arr { 12836, シャオハ }; int hashTup Arrays.hashCode(arr); // 数组 [12836, シャオハ] 的哈希值为 1151158 ListNode obj new ListNode(0); int hashObj obj.hashCode(); // 节点对象 utils.ListNode7dc5e7b4 的哈希值为 2110121908C#int num 3; int hashNum num.GetHashCode(); // 整数 3 的哈希值为 3; bool bol true; int hashBol bol.GetHashCode(); // 布尔值 true 的哈希值为 1; double dec 3.14159; int hashDec dec.GetHashCode(); // 小数 3.14159 的哈希值为 -1340954729; string str Hello アルゴリズム; int hashStr str.GetHashCode(); // 字符串 Hello アルゴリズム 的哈希值为 -586107568; object[] arr [12836, シャオハ]; int hashTup arr.GetHashCode(); // 数组 [12836, シャオハ] 的哈希值为 42931033; ListNode obj new(0); int hashObj obj.GetHashCode(); // 节点对象 0 的哈希值为 39053774;Go / JavaScript / TypeScript / C无内置哈希// Go 不提供内置的 hash code 函数// JavaScript 不提供内置的 hash code 函数// TypeScript 不提供内置的 hash code 函数// C 不提供内置的 hash code 函数对于这四类语言哈希值通常需借助语言标准库中的哈希表实现内部自动完成如 Go 的map、JS 的Map或自行实现/选用第三方哈希函数。Swiftlet num 3 let hashNum num.hashValue // 整数 3 的哈希值为 9047044699613009734 let bol true let hashBol bol.hashValue // 布尔值 true 的哈希值为 -4431640247352757451 let dec 3.14159 let hashDec dec.hashValue // 小数 3.14159 的哈希值为 -2465384235396674631 let str Hello アルゴリズム let hashStr str.hashValue // 字符串 Hello アルゴリズム 的哈希值为 -7850626797806988787 let arr [AnyHashable(12836), AnyHashable(シャオハ)] let hashTup arr.hashValue // 数组 [AnyHashable(12836), AnyHashable(シャオハ)] 的哈希值为 -2308633508154532996 let obj ListNode(x: 0) let hashObj obj.hashValue // 节点对象 utils.ListNode 的哈希值为 -2434780518035996159Dartint num 3; int hashNum num.hashCode; // 整数 3 的哈希值为 34803 bool bol true; int hashBol bol.hashCode; // 布尔值 true 的哈希值为 1231 double dec 3.14159; int hashDec dec.hashCode; // 小数 3.14159 的哈希值为 2570631074981783 String str Hello アルゴリズム; int hashStr str.hashCode; // 字符串 Hello アルゴリズム 的哈希值为 468167534 List arr [12836, シャオハ]; int hashArr arr.hashCode; // 数组 [12836, シャオハ] 的哈希值为 976512528 ListNode obj new ListNode(0); int hashObj obj.hashCode; // 节点对象 Instance of ListNode 的哈希值为 1033450432Rustuse std::collections::hash_map::DefaultHasher; use std::hash::{Hash, Hasher}; let num 3; let mut num_hasher DefaultHasher::new(); num.hash(mut num_hasher); let hash_num num_hasher.finish(); // 整数 3 的哈希值为 568126464209439262 let bol true; let mut bol_hasher DefaultHasher::new(); bol.hash(mut bol_hasher); let hash_bol bol_hasher.finish(); // 布尔值 true 的哈希值为 4952851536318644461 let dec: f32 3.14159; let mut dec_hasher DefaultHasher::new(); dec.to_bits().hash(mut dec_hasher); let hash_dec dec_hasher.finish(); // 小数 3.14159 的哈希值为 2566941990314602357 let str Hello アルゴリズム; let mut str_hasher DefaultHasher::new(); str.hash(mut str_hasher); let hash_str str_hasher.finish(); // 字符串 Hello アルゴリズム 的哈希值为 16092673739211250988 let arr (12836, シャオハ); let mut tup_hasher DefaultHasher::new(); arr.hash(mut tup_hasher); let hash_tup tup_hasher.finish(); // 元组 (12836, シャオハ) 的哈希值为 1885128010422702749 let node ListNode::new(42); let mut hasher DefaultHasher::new(); node.borrow().val.hash(mut hasher); let hash hasher.finish(); // 节点对象 RefCell { value: ListNode { val: 42, next: None } } 的哈希值为 15387811073369036852Kotlinval num 3 val hashNum num.hashCode() // 整数 3 的哈希值为 3 val bol true val hashBol bol.hashCode() // 布尔值 true 的哈希值为 1231 val dec 3.14159 val hashDec dec.hashCode() // 小数 3.14159 的哈希值为 -1340954729 val str Hello アルゴリズム val hashStr str.hashCode() // 字符串 Hello アルゴリズム 的哈希值为 -727081396 val arr arrayOfAny(12836, シャオハ) val hashTup arr.hashCode() // 数组 [12836, シャオハ] 的哈希值为 189568618 val obj ListNode(0) val hashObj obj.hashCode() // 节点对象 utils.ListNode1d81eb93 的哈希值为 495053715Rubynum 3 hash_num num.hash # 整数 3 的哈希值为 -4385856518450339636 bol true hash_bol bol.hash # 布尔值 true 的哈希值为 -1617938112149317027 dec 3.14159 hash_dec dec.hash # 小数 3.14159 的哈希值为 -1479186995943067893 str Hello アルゴリズム hash_str str.hash # 字符串 Hello アルゴリズム 的哈希值为 -4075943250025831763 tup [12836, シャオハ] hash_tup tup.hash # 元组 (12836, シャオハ) 的哈希值为 1999544809202288822 obj ListNode.new(0) hash_obj obj.hash # 节点对象 #ListNode:0x000078133140ab70 的哈希值为 4302940560806366381上述完整可运行示例分别存放于日文版配套代码目录例如 built_in_hash.cpp、built_in_hash.java、built_in_hash.py 等Go、JS、TS、C 因不提供内置 hash code 接口而未生成对应示例文件。可变与不可变哪些对象才能当 key很多编程语言规定只有不可变对象才能作为哈希表的key。设想若用列表动态数组作key其内容一旦变化哈希值也会随之改变那么原先存入的value便再也无法通过原key找到——这正是哈希表实现普遍要求键具有不可变性的根本原因。另一方面自定义对象如链表节点的成员变量通常是可变的却依然可哈希。这是因为对象的哈希值往往基于其内存地址生成只要对象内容变化而内存地址不变其哈希值就保持不变。因此这类对象进入哈希表后不会因为内容被修改而丢失。彩蛋为什么每次运行哈希值都不一样细心的读者可能会发现同一个字符串哈希在不同控制台/多次运行中输出的数值并不一致。这是因为 Python 解释器在每次启动时都会向字符串哈希函数注入一个随机的 salt 值。这一机制可以有效防御 HashDoS哈希洪水拒绝服务攻击——攻击者本可精心构造大量同哈希字符串把哈希表拖入 $O(n)$ 的最坏情形随机 salt 的存在使这类预构造攻击失去确定性基础从而显著提升哈希算法的安全性。Go、Rust 等语言的默认哈希器同样采用类似的随机化种子策略如本文 Rust 示例中的DefaultHasher。小结与延伸阅读哈希冲突的治本之道在于哈希算法设计确定性、高效率、均匀分布是三项基本要求密码学场景还需单向性、抗碰撞性与雪崩效应四种简单哈希加法/乘法/XOR/旋转演示了构造思路其共性收尾是对一个大素数如 $1000000007$取模以素数模数削弱周期性偏斜生产环境通常使用 MD5已降级为完整性校验、SHA-1已废弃与 SHA-2/SHA-3安全可靠等标准算法语言内置哈希的对象约束与进程级随机化 salt 是使用哈希表时必须理解的边界条件。若想进一步巩固建议阅读同一章节下的 hash_map.md哈希表原理与基本操作、hash_collision.md链式与开放寻址两种冲突处理以及 summary.md要点回顾与 QA并在本地运行 simple_hash.py 与 built_in_hash.py 亲手验证上述全部结论。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考