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

Question

我不明白为什么整数值 "hash" 越来越低 in/after 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 是下一个运行循环后的散列值。

Answer 1

I would guess this happen because the uint limitation is 2,147,483,647.

32 位 无符号 整数的最大值大约为 40 亿 (2³² - 1 = 4,294,967,295)。你想到的数字是 signed 整数的最大值 (2³¹ - 1).

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

Answer 2

I dont understand why the interger Value "hash" is getting lower in/after the 3 loop.

C 中的所有无符号整数运算都是 modular arithmetic。对于unsigned int，就是模UINT_MAX + 1；对于 unsigned long、modulo ULONG_MAX + 1，等等。

(a modulo m 表示 a 除以 m 的余数；在 C 中，a % m 如果 a 和 m 都是无符号整数类型。）

在许多当前的体系结构中，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;
}

输出为

What? How? How come the result ends up zero? That cannot happen!

当然可以。事实上，您可以从数学上证明它最终会在乘数为偶数时发生，并且模数是关于 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) 的结果。

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

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

How would you interpret the behaviour of my C Hash function (type of Fowler–Noll–Vo_hash_function)?

c

hash

xor

fnv