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

Question

我不明白为什么整数值“哈希”在 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是下一次循环运行后的哈希值。

score 2 · Accepted Answer

我不明白为什么整数值“哈希”在 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）：

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

输出是

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

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

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

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

我们得到

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

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

score 0 · Accepted Answer

我猜这是因为 uint 限制为 2,147,483,647。

32 位无符号整数的最大值约为 40 亿（2 ³² - 1 = 4,294,967,295）。您正在考虑的数字是有符号整数的最大值（2 ³¹ - 1）。

2,146,134,658 略小于 2 ³¹（因此它甚至可以放入无符号 32 位整数），但仍然非常接近极限。将其乘以FNV_PRIME_32大约 2 ²⁴将得到大约 2 ⁵⁵的结果，这将导致溢出。

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

2 回答 2

Related

Reference