字符串中的BKDRHash哈希函数

字符串中的BKDRHash哈希函数

在计算机科学中，哈希函数是一种将任意长度的输入（也称为“消息”）通过散列算法转换成固定长度的输出，该输出就是哈希值。哈希函数的一个重要特性是，对于相同的输入，无论何时执行哈希函数，它都应该产生相同的输出。然而，对于不同的输入，即使它们只有微小的差别，哈希函数也应该产生大不相同的输出。
BKDRHash是一种常用的字符串哈希函数，它是由布隆和卡恩于1977年提出的。BKDRHash的基本思想是：对每个字符的ASCII值乘以一个常数因子，然后将所有的乘积相加，最后取结果的模。
BKDRHash算法流程

• 选择一个质数作为乘数因子，通常选择的是31或者更大一些的质数。
  
• 初始化哈希值为0。
  
• 遍历字符串中的每个字符，将字符的ASCII值乘以乘数因子，然后加到哈希值上。
  
• 返回哈希值。
  

C++代码实现

以下是BKDRHash算法的C++实现：

1. unsigned int BKDRHash(const char *str) {
2.     unsigned int seed = 131; // 31 131 1313 13131 131313等质数
3.     unsigned int hash = 0;
4.     while (*str) {
5.         hash = hash * seed + (*str++);
6.     }
7.     return (hash & 0x7FFFFFFF);
8. }

复制代码

例题及题解

假设我们有一个字符串"Hello, World!"，我们想要使用BKDRHash函数来计算它的哈希值。首先，我们需要遍历字符串中的每个字符，然后将字符的ASCII值乘以乘数因子（在这个例子中是131），然后加到哈希值上。最后，我们返回哈希值。
以下是计算"Hello, World!"的BKDRHash值的C++代码：
[code]#include using namespace std;int main() {    const char *str = "Hello, World!";    unsigned int hash = BKDRHash(str);    cout