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 算法》仓库中 哈希算法 一章展开系统讲解哈希算法的设计目标、四类简单哈希算法的源码级实现、为什么取模要选大质数以及 MD5/SHA 系列等常见标准哈希算法与各大语言内置哈希机制的差异读完可掌握既快又稳的哈希函数设计原则及在 Python、C、Java 等语言中计算内置哈希值的方法。为什么哈希冲突的治理要聚焦哈希算法在 哈希表 一节中介绍的开放寻址与链地址法只能保证哈希表在发生冲突时正常工作而无法减少冲突本身的发生。如果哈希冲突过于频繁哈希表性能会急剧劣化。如下图所示链地址哈希表在理想情况下键值对均匀分布在各个桶中查询效率最佳最差情况下所有键值对都落入同一个桶时间复杂度退化至 $O(n)$。键值对的分布情况由哈希函数决定。回忆哈希函数把键映射到桶索引的计算步骤——先计算哈希值再对数组长度取模index hash(key) % capacity当哈希表容量capacity固定时哈希算法hash()直接决定了输出值进而决定了键值对在表中的分布。因此要降低冲突概率注意力必须集中在hash()本身的设计上而不是只依赖冲突解决策略。哈希算法的设计目标为了实现既快又稳的哈希表数据结构哈希算法应具备三个基本特点确定性对于相同的输入始终产生相同的输出这样才能确保哈希表是可靠的效率高计算哈希值的过程应足够快计算开销越小哈希表的实用性越高均匀分布哈希算法应使键值对均匀分布在哈希表中分布越均匀冲突概率越低。哈希算法的用途远不止哈希表还广泛应用于其他领域密码存储系统通常不直接存储明文密码而是存储密码的哈希值用户登录时对新输入的密码计算哈希与存储值比对匹配即视为密码正确数据完整性检查发送方将数据的哈希值随数据一同发送接收方重新计算并比对匹配则数据完整。对于密码学相关应用为了防止从哈希值反推原始数据等逆向工程哈希算法还需要更高等级的安全特性单向性无法通过哈希值反推出关于输入数据的任何信息抗碰撞性极难找到两个不同的输入使得它们的哈希值相同雪崩效应输入的微小变化应当导致输出的显著且不可预测的变化。需要特别强调均匀分布与抗碰撞性是两个独立的概念满足均匀分布不一定满足抗碰撞性。例如在随机输入key下哈希函数key % 100可以产生均匀分布的输出然而该算法过于简单所有后两位相等的key输出都相同攻击者可以很容易地从哈希值反推出可用的key从而破解密码。四类简单哈希算法的源码解析哈希算法的设计是一个需要考虑许多因素的复杂问题但在要求不高的场景下可以设计一些简单哈希算法。哈希算法 一章给出了四类经典实现仓库中在 codes/python/chapter_hashing/simple_hash.py 提供了完整可运行代码C 与 C 版本分别见 codes/cpp/chapter_hashing/simple_hash.cpp 和 codes/c/chapter_hashing/simple_hash.c File: simple_hash.py Created Time: 2023-06-15 Author: krahets (krahets163.com) def add_hash(key: str) - int: 加法哈希 hash 0 modulus 1000000007 for c in key: hash ord(c) return hash % modulus def mul_hash(key: str) - int: 乘法哈希 hash 0 modulus 1000000007 for c in key: hash 31 * hash ord(c) return hash % modulus def xor_hash(key: str) - int: 异或哈希 hash 0 modulus 1000000007 for c in key: hash ^ ord(c) return hash % modulus def rot_hash(key: str) - int: 旋转哈希 hash 0 modulus 1000000007 for c in key: hash (hash 4) ^ (hash 28) ^ ord(c) return hash % modulus四类算法的核心思想加法哈希对输入的每个字符的 ASCII 码进行相加将总和作为哈希值乘法哈希利用乘法的不相关性每轮乘以一个常数此处为 31将各字符的 ASCII 码累积到哈希值中异或哈希将每个元素通过异或操作累积到一个哈希值中旋转哈希每累积一个字符前先对哈希值做左移 4 位再与右移 28 位结果异或的旋转操作hash (hash 4) ^ (hash 28) ^ ord(c)使高位信息向低位扩散。为什么最后一步要对大质数取模观察源码可以发现每种哈希算法的最后一步都是对大质数1000000007取模以确保哈希值在合适范围内。值得思考的是为什么要强调对质数取模对合数取模的弊端是什么结论是使用大质数作为模数可以最大化地保证哈希值的均匀分布。因为质数不与其他数字存在公约数可以减少因取模操作而产生的周期性模式从而避免哈希冲突。举个直观例子假设选择合数 9 作为模数它可以被 3 整除那么所有能被 3 整除的key都会被映射到 0、3、6 这三个哈希值上modulus 9 key { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, ... } hash { 0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6, ... }如果输入key恰好满足这种等差数列的数据分布哈希值就会出现聚堆从而加重哈希冲突。现在将modulus替换为质数 13由于key与modulus之间不存在公约数输出哈希值的均匀性明显提升modulus 13 key { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, ... } hash { 0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, ... }值得说明的是如果能保证key本身随机均匀分布那么选质数或合数作为模数都能输出均匀分布的哈希值而当key的分布存在某种周期性时对合数取模更容易出现聚集现象。总而言之通常选取质数作为模数且这个质数最好足够大以尽可能消除周期性模式提升哈希算法的稳健性。常见标准哈希算法MD5、SHA-1、SHA-2、SHA-3不难发现上述简单哈希算法都比较脆弱远未达到哈希算法的设计目标。例如由于加法和异或满足交换律加法哈希和异或哈希无法区分内容相同但顺序不同的字符串这可能会加剧哈希冲突并引起安全问题。实际工程中通常采用标准哈希算法例如 MD5、SHA-1、SHA-2 和 SHA-3它们能将任意长度的输入数据映射到恒定长度的哈希值。近一个世纪以来哈希算法处于不断升级与优化的过程中一方面研究人员努力提升性能另一方面另一部分研究人员和黑客致力于寻找其安全问题。实际应用中常见哈希算法的对比如下MD5SHA-1SHA-2SHA-3推出时间1992199520022008输出长度128 bit160 bit256/512 bit224/256/384/512 bit哈希冲突较多较多很少很少安全等级低已被成功攻击低已被成功攻击高高应用已被弃用仍用于数据完整性检查已被弃用加密货币交易验证、数字签名等可用于替代 SHA-2MD5 和 SHA-1 已多次被成功攻击被各类安全应用弃用SHA-2 系列中的 SHA-256 是最安全的哈希算法之一仍未出现成功的攻击案例常用在各类安全应用与协议中SHA-3 相较 SHA-2 的实现开销更低、计算效率更高但目前使用覆盖度不如 SHA-2 系列。主流语言的内置哈希值机制与差异哈希表的key可以是整数、小数或字符串等数据类型编程语言通常会为这些类型提供内置哈希算法用于计算哈希表中的桶索引。以 Python 为例可以调用hash()函数计算各种数据类型的哈希值仓库中对应示例见 codes/python/chapter_hashing/built_in_hash.py整数和布尔量的哈希值就是其本身浮点数和字符串的哈希值计算较为复杂元组的哈希值是对其中每个元素进行哈希再将这些哈希值组合成单一哈希值对象的哈希值基于其内存地址生成通过重写对象的哈希方法可实现基于内容生成哈希值。Pythonhash()覆盖常见类型num 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 的哈希值为 274267521Cstd::hash仅覆盖基本类型int 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仅提供基本数据类型的哈希值计算数组、对象的哈希值需要自行实现这一点在 codes/cpp/chapter_hashing/built_in_hash.cpp 示例中也有体现。Java / C# / KotlinhashCode()体系Java 通过包装类的静态方法与对象方法计算哈希例如Integer.hashCode(num)、Boolean.hashCode(bol)、Double.hashCode(dec)、str.hashCode()数组可用Arrays.hashCode(arr)对象obj.hashCode()基于内存地址。C# 与 Kotlin 语法类似直接调用num.GetHashCode()/num.hashCode()Boolean.hashCode固定为 1231。各语言对同一数值给出的哈希值往往不同例如 Dart 中整数 3 的hashCode是 34803Swift 的hashValue是一个大整数不同编程语言的内置哈希值计算函数的定义和方法各不相同跨语言不可直接比对。此外Go、JavaScript、TypeScript、C 等语言未提供内置 hash code 函数需要自行实现或借助标准库的哈希工具。哈希键的不可变性与字符串哈希加盐在许多编程语言中只有不可变对象才可作为哈希表的key。假如将列表动态数组作为key当列表内容发生变化时其哈希值随之改变我们就无法在哈希表中查询到原先的value了。虽然自定义对象比如链表节点的成员变量是可变的但它依然是可哈希的。这是因为对象的哈希值通常基于内存地址生成即使对象内容变化内存地址不变哈希值仍然不变。细心的读者可能发现在不同控制台中运行程序时字符串输出的哈希值是不同的。这是因为 Python 解释器在每次启动时都会为字符串哈希函数加入一个随机的盐salt值。这种做法可以有效防止 HashDoS 攻击——攻击者若无法预先知道盐值就难以构造大量哈希冲突的输入对服务器发起拒绝服务攻击从而提升哈希算法的安全性。小结冲突解决策略开放寻址、链地址只是善后真正降低冲突概率的钥匙是哈希函数hash()的均匀性简单哈希算法加法/乘法/异或/旋转对大质数1000000007取模质数模数能消除周期性模式、避免哈希值聚堆安全场景下应选用 SHA-256 等经过验证的标准哈希算法MD5 与 SHA-1 已不可用于安全校验各语言内置哈希机制差异明显且对象哈希通常基于内存地址只有不可变对象适合作为哈希键Python 的字符串哈希加盐是防御 HashDoS 的典型手段。【免费下载链接】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 算法》仓库中 哈希算法 一章展开系统讲解哈希算法的设计目标、四类简单哈希算法的源码级实现、为什么取模要选大质数以及 MD5/SHA 系列等常见标准哈希算法与各大语言内置哈希机制的差异读完可掌握既快又稳的哈希函数设计原则及在 Python、C、Java 等语言中计算内置哈希值的方法。为什么哈希冲突的治理要聚焦哈希算法在 哈希表 一节中介绍的开放寻址与链地址法只能保证哈希表在发生冲突时正常工作而无法减少冲突本身的发生。如果哈希冲突过于频繁哈希表性能会急剧劣化。如下图所示链地址哈希表在理想情况下键值对均匀分布在各个桶中查询效率最佳最差情况下所有键值对都落入同一个桶时间复杂度退化至 $O(n)$。键值对的分布情况由哈希函数决定。回忆哈希函数把键映射到桶索引的计算步骤——先计算哈希值再对数组长度取模index hash(key) % capacity当哈希表容量capacity固定时哈希算法hash()直接决定了输出值进而决定了键值对在表中的分布。因此要降低冲突概率注意力必须集中在hash()本身的设计上而不是只依赖冲突解决策略。哈希算法的设计目标为了实现既快又稳的哈希表数据结构哈希算法应具备三个基本特点确定性对于相同的输入始终产生相同的输出这样才能确保哈希表是可靠的效率高计算哈希值的过程应足够快计算开销越小哈希表的实用性越高均匀分布哈希算法应使键值对均匀分布在哈希表中分布越均匀冲突概率越低。哈希算法的用途远不止哈希表还广泛应用于其他领域密码存储系统通常不直接存储明文密码而是存储密码的哈希值用户登录时对新输入的密码计算哈希与存储值比对匹配即视为密码正确数据完整性检查发送方将数据的哈希值随数据一同发送接收方重新计算并比对匹配则数据完整。对于密码学相关应用为了防止从哈希值反推原始数据等逆向工程哈希算法还需要更高等级的安全特性单向性无法通过哈希值反推出关于输入数据的任何信息抗碰撞性极难找到两个不同的输入使得它们的哈希值相同雪崩效应输入的微小变化应当导致输出的显著且不可预测的变化。需要特别强调均匀分布与抗碰撞性是两个独立的概念满足均匀分布不一定满足抗碰撞性。例如在随机输入key下哈希函数key % 100可以产生均匀分布的输出然而该算法过于简单所有后两位相等的key输出都相同攻击者可以很容易地从哈希值反推出可用的key从而破解密码。四类简单哈希算法的源码解析哈希算法的设计是一个需要考虑许多因素的复杂问题但在要求不高的场景下可以设计一些简单哈希算法。哈希算法 一章给出了四类经典实现仓库中在 codes/python/chapter_hashing/simple_hash.py 提供了完整可运行代码C 与 C 版本分别见 codes/cpp/chapter_hashing/simple_hash.cpp 和 codes/c/chapter_hashing/simple_hash.c File: simple_hash.py Created Time: 2023-06-15 Author: krahets (krahets163.com) def add_hash(key: str) - int: 加法哈希 hash 0 modulus 1000000007 for c in key: hash ord(c) return hash % modulus def mul_hash(key: str) - int: 乘法哈希 hash 0 modulus 1000000007 for c in key: hash 31 * hash ord(c) return hash % modulus def xor_hash(key: str) - int: 异或哈希 hash 0 modulus 1000000007 for c in key: hash ^ ord(c) return hash % modulus def rot_hash(key: str) - int: 旋转哈希 hash 0 modulus 1000000007 for c in key: hash (hash 4) ^ (hash 28) ^ ord(c) return hash % modulus四类算法的核心思想加法哈希对输入的每个字符的 ASCII 码进行相加将总和作为哈希值乘法哈希利用乘法的不相关性每轮乘以一个常数此处为 31将各字符的 ASCII 码累积到哈希值中异或哈希将每个元素通过异或操作累积到一个哈希值中旋转哈希每累积一个字符前先对哈希值做左移 4 位再与右移 28 位结果异或的旋转操作hash (hash 4) ^ (hash 28) ^ ord(c)使高位信息向低位扩散。为什么最后一步要对大质数取模观察源码可以发现每种哈希算法的最后一步都是对大质数1000000007取模以确保哈希值在合适范围内。值得思考的是为什么要强调对质数取模对合数取模的弊端是什么结论是使用大质数作为模数可以最大化地保证哈希值的均匀分布。因为质数不与其他数字存在公约数可以减少因取模操作而产生的周期性模式从而避免哈希冲突。举个直观例子假设选择合数 9 作为模数它可以被 3 整除那么所有能被 3 整除的key都会被映射到 0、3、6 这三个哈希值上modulus 9 key { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, ... } hash { 0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6, ... }如果输入key恰好满足这种等差数列的数据分布哈希值就会出现聚堆从而加重哈希冲突。现在将modulus替换为质数 13由于key与modulus之间不存在公约数输出哈希值的均匀性明显提升modulus 13 key { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, ... } hash { 0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, ... }值得说明的是如果能保证key本身随机均匀分布那么选质数或合数作为模数都能输出均匀分布的哈希值而当key的分布存在某种周期性时对合数取模更容易出现聚集现象。总而言之通常选取质数作为模数且这个质数最好足够大以尽可能消除周期性模式提升哈希算法的稳健性。常见标准哈希算法MD5、SHA-1、SHA-2、SHA-3不难发现上述简单哈希算法都比较脆弱远未达到哈希算法的设计目标。例如由于加法和异或满足交换律加法哈希和异或哈希无法区分内容相同但顺序不同的字符串这可能会加剧哈希冲突并引起安全问题。实际工程中通常采用标准哈希算法例如 MD5、SHA-1、SHA-2 和 SHA-3它们能将任意长度的输入数据映射到恒定长度的哈希值。近一个世纪以来哈希算法处于不断升级与优化的过程中一方面研究人员努力提升性能另一方面另一部分研究人员和黑客致力于寻找其安全问题。实际应用中常见哈希算法的对比如下MD5SHA-1SHA-2SHA-3推出时间1992199520022008输出长度128 bit160 bit256/512 bit224/256/384/512 bit哈希冲突较多较多很少很少安全等级低已被成功攻击低已被成功攻击高高应用已被弃用仍用于数据完整性检查已被弃用加密货币交易验证、数字签名等可用于替代 SHA-2MD5 和 SHA-1 已多次被成功攻击被各类安全应用弃用SHA-2 系列中的 SHA-256 是最安全的哈希算法之一仍未出现成功的攻击案例常用在各类安全应用与协议中SHA-3 相较 SHA-2 的实现开销更低、计算效率更高但目前使用覆盖度不如 SHA-2 系列。主流语言的内置哈希值机制与差异哈希表的key可以是整数、小数或字符串等数据类型编程语言通常会为这些类型提供内置哈希算法用于计算哈希表中的桶索引。以 Python 为例可以调用hash()函数计算各种数据类型的哈希值仓库中对应示例见 codes/python/chapter_hashing/built_in_hash.py整数和布尔量的哈希值就是其本身浮点数和字符串的哈希值计算较为复杂元组的哈希值是对其中每个元素进行哈希再将这些哈希值组合成单一哈希值对象的哈希值基于其内存地址生成通过重写对象的哈希方法可实现基于内容生成哈希值。Pythonhash()覆盖常见类型num 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 的哈希值为 274267521Cstd::hash仅覆盖基本类型int 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仅提供基本数据类型的哈希值计算数组、对象的哈希值需要自行实现这一点在 codes/cpp/chapter_hashing/built_in_hash.cpp 示例中也有体现。Java / C# / KotlinhashCode()体系Java 通过包装类的静态方法与对象方法计算哈希例如Integer.hashCode(num)、Boolean.hashCode(bol)、Double.hashCode(dec)、str.hashCode()数组可用Arrays.hashCode(arr)对象obj.hashCode()基于内存地址。C# 与 Kotlin 语法类似直接调用num.GetHashCode()/num.hashCode()Boolean.hashCode固定为 1231。各语言对同一数值给出的哈希值往往不同例如 Dart 中整数 3 的hashCode是 34803Swift 的hashValue是一个大整数不同编程语言的内置哈希值计算函数的定义和方法各不相同跨语言不可直接比对。此外Go、JavaScript、TypeScript、C 等语言未提供内置 hash code 函数需要自行实现或借助标准库的哈希工具。哈希键的不可变性与字符串哈希加盐在许多编程语言中只有不可变对象才可作为哈希表的key。假如将列表动态数组作为key当列表内容发生变化时其哈希值随之改变我们就无法在哈希表中查询到原先的value了。虽然自定义对象比如链表节点的成员变量是可变的但它依然是可哈希的。这是因为对象的哈希值通常基于内存地址生成即使对象内容变化内存地址不变哈希值仍然不变。细心的读者可能发现在不同控制台中运行程序时字符串输出的哈希值是不同的。这是因为 Python 解释器在每次启动时都会为字符串哈希函数加入一个随机的盐salt值。这种做法可以有效防止 HashDoS 攻击——攻击者若无法预先知道盐值就难以构造大量哈希冲突的输入对服务器发起拒绝服务攻击从而提升哈希算法的安全性。小结冲突解决策略开放寻址、链地址只是善后真正降低冲突概率的钥匙是哈希函数hash()的均匀性简单哈希算法加法/乘法/异或/旋转对大质数1000000007取模质数模数能消除周期性模式、避免哈希值聚堆安全场景下应选用 SHA-256 等经过验证的标准哈希算法MD5 与 SHA-1 已不可用于安全校验各语言内置哈希机制差异明显且对象哈希通常基于内存地址只有不可变对象适合作为哈希键Python 的字符串哈希加盐是防御 HashDoS 的典型手段。【免费下载链接】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），仅供参考