时间戳

首页 > 解决方案 > 您如何解释我的 C 哈希函数（Fowler–Noll–Vo_hash_function 的类型）的行为？

c - 您如何解释我的 C 哈希函数（Fowler–Noll–Vo_hash_function 的类型）的行为？

问题描述

我不明白为什么整数值“哈希”在 3 循环中/之后越来越低。

我猜这是因为 uint 限制是2,147,483,647. 但是...当我尝试逐步进行时，该值等于2146134658？。我数学不是很好，但应该低于限制。

#define FNV_PRIME_32 16777619
#define FNV_OFFSET_32 2166136261U

unsigned int hash_function(const char *string, unsigned int size)
{
    unsigned int str_len = strlen(string);

    if (str_len == 0) exit(0);

    unsigned int hash = FNV_OFFSET_32;

    for (unsigned int i = 0; i < str_len; i++)
    {
        hash = hash ^ string[i]; 
        // Multiply by prime number found to work well
        hash = hash * FNV_PRIME_32;
        if (hash > 765010506)
            printf("YO!\n");
        else
            printf("NOO!\n");
    }
    return hash % size;
}

如果您想知道这个 if 语句仅适用于我。

if (hash > 765010506)
    printf("YO!\n");
else
    printf("NOO!\n");

765010506是下一次循环运行后的哈希值。

标签： chashxorfnv

解决方案

我不明白为什么整数值“哈希”在 3 循环中/之后越来越低。

C 中的所有无符号整数运算都是模运算。因为unsigned int，它是模数 UINT_MAX + 1；对于unsigned long,模 ULONG_MAX + 1, 等等。

（a 模 m表示在 C中a除以; 的余数，如果两者都是无符号整数类型。）ma % mam

在许多当前架构上，unsigned int是 32 位无符号整数类型，带有UINT_MAX == 4294967295.

让我们看看这在实践中意味着什么，对于乘法（乘以 65520，这恰好是一个有趣的值；2 16 - 16）：

unsigned int  x = 1;
int           i;
for (i = 0; i < 10; i++) {
    printf("%u\n", x);
    x = x * 65520;
}

输出是

1
65520
4292870400
50327552
3221291008
4293918720
16777216
4026531840
0
0

什么？如何？为什么结果最终为零？那不可能发生！

当然可以。事实上，您可以在数学上证明，只要乘数为偶数，它最终就会发生，并且模数是关于 2 的幂（此处为 2 32）。

但是，您的特定乘数很奇怪；因此，它不会受到上述影响。但是，由于模运算，它仍然会环绕。如果我们用你的乘数重试同样的方法16777619，和更长的序列，

unsigned int  x = 1;
int           i;
for (i = 0; i < 20; i++) {
    printf("%u\n", x);
    x = x * 16777619;
}

我们得到

1
16777619
637696617
1055306571
1345077009
1185368003
4233492473
878009595
1566662433
558416115
1485291145
3870355883
3549196337
924097827
3631439385
3600621915
878412353
2903379027
3223152297
390634507

事实上，这个序列有 1,073,741,824 次迭代（在它自己重复之前），并且永远不会产生 0、2、4、5、6、7、8、10、12、13、14 或 15，因为例如——也就是说，如果它从 1 开始。它甚至需要 380 次迭代才能得到小于 16,777,619 (16,689,137) 的结果。

对于散列函数，没关系。每个新的非零输入都会改变状态，因此序列不会“锁定”。但是，没有理由期望哈希值会随着哈希数据长度的增加而单调增加；最好假设它是“大致随机”的：不是真正随机的，因为它仅取决于输入，但也不是明显的常规外观。

推荐阅读