常用Hash算法(C语言的简单实现)

Hash算法是一种将任意长度的输入（也叫做预映射）通过一个特定的函数转换成固定长度输出的算法。这个输出通常称为哈希值或散列值。哈希算法在计算机科学中有广泛的应用，如数据存储、查找表、密码学、数字签名等。C语言中的简单实现通常使用基本的数据类型如`unsigned int`来存储哈希值。 1. **RSHash**（Robert Sedgewick哈希函数）： 这个函数使用两个常量`a`和`b`进行迭代计算。初始时，哈希值设为0，然后遍历字符串中的每个字符，将当前字符的值乘以`a`并加到哈希值上，同时更新`a`为`a * b`。最后返回计算得到的哈希值。 2. **JSHash**（Jenkin's One At-A-Time哈希函数）： JSHash使用一个初始哈希值，并结合位操作进行迭代计算。对于每个字符，它将哈希值左移5位，加上字符的值，并与右移2位的哈希值进行异或操作。这种方法使得每个字符对哈希值的影响独立且均匀分布。 3. **PJWHash**（Peter J. Weinberger哈希函数）： 这个函数利用了位运算，将哈希值左移一定位数后加上字符值。如果新的哈希值的高几位非零，则进行特定的位操作，避免高位溢出。这种方法旨在减少哈希冲突。 4. **ELFHash**（ ELF文件格式的哈希函数）： ELFHash的计算方式是将哈希值左移4位，加上当前字符值。如果哈希值的最高4位非零，则进行异或和位清除操作。这种方法也是为了使哈希值的分布更加均匀。 5. **BKDRHash**（Bernstein哈希函数）： 它使用一个种子值`seed`，并将哈希值与字符值相乘后累加。这种方式保证了连续的字符对哈希值的影响有累积效应，提高了哈希的区分度。 这些哈希函数虽然简单，但都具有一定的抗冲突能力，可以快速计算出字符串的哈希值。然而，它们并非最优，可能在处理大量数据或特定字符串时产生较多的哈希冲突。在实际应用中，更高效的哈希函数，如MD5、SHA系列，或者更高级的如CityHash、MurmurHash等，通常会提供更好的性能和冲突减少效果。在选择哈希函数时，需要根据具体需求权衡速度、冲突概率和安全性等因素。