谈谈hash算法
哈希算法的设计是一个需要考虑许多因素的复杂问题。然而对于某些要求不高的场景，我们也能设计一些简 单的哈希算法。
加法哈希：对输入的每个字符的 ASCII 码进行相加，将得到的总和作为哈希值。
乘法哈希：利用了乘法的不相关性，每轮乘以一个常数，将各个字符的 ASCII 码累积到哈希值中。
异或哈希：将输入数据的每个元素通过异或操作累积到一个哈希值中。
**旋转哈希 **：将每个字符的 ASCII 码累积到一个哈希值中，每次累积之前都会对哈希值进行旋转操作
1. 简单哈希算法代码实例
/* 加法哈希 */
int addHash(string key) {long long hash = 0;const int MODULUS = 1000000007;for (unsigned char c : key) {hash = (hash + (int)c) % MODULUS;}return (int)hash;
}/* 乘法哈希 */
int mulHash(string key) {long long hash = 0;const int MODULUS = 1000000007;for (unsigned char c : key) {hash = (31 * hash + (int)c) % MODULUS;}return (int)hash;
}/* 异或哈希 */
int xorHash(string key) {int hash = 0;const int MODULUS = 1000000007;for (unsigned char c : key) {hash ^= (int)c;}return hash & MODULUS;
}/* 旋转哈希 */
int rotHash(string key) {long long hash = 0;const int MODULUS = 1000000007;for (unsigned char c : key) {hash = ((hash << 4) ^ (hash >> 28) ^ (int)c) % MODULUS;}return (int)hash;
}
- 每种哈希算法的最后一步都是对大质数 1000000007 取模，以确保哈希值在合适的范围内。大家知道为什么要对质数取模，或者说对合数取模的弊端是什么？结论：当我们使用大质数作为模数时，可以因为质数不会与其他数字存在公约数，可以减少因取模操作而产生的周期性模式，从而避免哈希冲突，最大化地保证哈希值的均匀分布。
2.常见哈希算法
以上介绍的简单哈希算法都比较脆弱，远远没有达到哈希算法的设计目标。例如，由于加法和 异或满足交换律，因此加法哈希和异或哈希无法区分内容相同但顺序不同的字符串，这可能会加剧哈希冲突， 并引起一些安全问题。
- 在实际中，我们通常会用一些标准哈希算法，例如 MD5、SHA‑1、SHA‑2、SHA3 等。它们可以将任意长度 的输入数据映射到恒定长度的哈希值。
- MD5和SHA-1：已多次被成功攻击，因此它们被各类安全应用弃用。
- SHA‑2 系列中的 SHA‑256 是最安全的哈希算法之一，仍未出现成功的攻击案例，因此常被用在各类安全应用与协议中。
- SHA‑3 相较 SHA‑2 的实现开销更低、计算效率更高，但目前使用覆盖度不如 SHA‑2 系列。
| MD5 | SHA-1 | SHA-2 | SHA-3 | |
|---|---|---|---|---|
| 问世时间 | 1992 | 1995 | 2002 | 2008 |
| 输出长度 | 128bits | 160bits | 256/512 bits | 224/256/384/512 bits |
| 哈希冲突 | 较多 | 较多 | 很少 | 很少 |
| 安全等级 | 低，已被成功攻击 | 低，已被成功攻击 | 高 | 高 |
| 应用情况 | 已被弃用，仍用于数据完整 性检查 | 已被弃用 | 加密货币交易验证、数字 签名等 | 可用于替代 SHA‑2 |
3.数据结构的哈希值
-
我们知道，哈希表的 key 可以是整数、小数或字符串等数据类型。编程语言通常会为这些数据类型提供内置 的哈希算法，用于计算哈希表中的桶索引。以 Python 为例，我们可以调用
hash()函数来计算各种数据类型 的哈希值。- 整数和布尔量的哈希值就是其本身。
- 浮点数和字符串的哈希值计算较为复杂，有兴趣的同学请自行学习。
- 元组的哈希值是对其中每一个元素进行哈希，然后将这些哈希值组合起来，得到单一的哈希值。
- 对象的哈希值基于其内存地址生成。通过重写对象的哈希方法，可实现基于内容生成哈希值。
-
不同编程语言的内置哈希值计算函数的定义和方法不同，以下为C++语言的哈希函数
std:hash()，它仅提供基本数据类型的哈希值计算，数组、对象的哈希值计算需要自行实现// 整数 3 的哈希值为 3 int num = 3; size_t hashNum = hash<int>()(num);// 布尔量 1 的哈希值为 1 bool bol = true; size_t hashBol = hash<bool>()(bol);// 小数 3.14159 的哈希值为 4614256650576692846 double dec = 3.14159; size_t hashDec = hash<double>()(dec);// 字符串 Hello 算法 的哈希值为 15466937326284535026 string str = "Hello 算法"; size_t hashStr = hash<string>()(str);