c - 我对哈希函数做得正确吗？

Question

我被分配做以下工作:

The easiest hashing function it to read the string a character by character and consider each character as an unsigned 8-bit number between 0 and 255. Then we add all the characters modulo some integer k resulting in an integer between 0 and k-1. We assume the previous hashing function. The hashing function adds the bytes of a string modulo k. The size of the hash table is k.

因此，我编码如下:

unsigned hash (char *s)
{
 unsigned hashval;

 for (hashval = 0; *s != '\0'; s++) { 
    hashval += *s;    
}

 return hashval % HASHSIZE;
}

这里，HASHSIZE相当于规范中的K。

但是我不确定我是否做对了，这真的是哈希函数吗？

非常感谢。

Answer 1

But I am not sure if I am doing correctly, Is this really hash function?

我认为您是在问您的代码是否准确地实现了您提供的规范。虽然很接近，但它不是，至少不是以便携的方式。主要问题是它未能解决规范的这一规定:

consider each character as an unsigned 8-bit number

C 允许 char类型是签名还是未签名，由实现自行决定。签名char这很常见，您的代码没有考虑到这一点。

此外，虽然 C 需要 char与 unsigned char 大小相同，并且需要 unsigned char拥有至少 8 位，其中没有填充位，它不需要恰好 8 位。然而，实际上，所有现代系统都使用 8 位 char s，并且该练习似乎不太可能要求您考虑更大的可能性。

要解决此问题，您需要转换每个 char在将字符串添加到累加器变量之前将其转换为无符号 8 位数字。有几种方法可以做到这一点。如果您愿意假设 unsigned char恰好有 8 位，那么最简单的方法就是在添加之前将每个字符转换为该类型。

<小时/>

作为次要问题，您的函数不一定实现规范中描述的模块化加法:

The hashing function adds the bytes of a string modulo k.

这里的风险是字符串中所有字符的总和足以溢出类型 unsigned 。该类型的最大值可以小至 65535(尽管在大多数现代实现中它要大得多)，并且在该大小下，输入字符串的字符总和可能会溢出。在这种情况下，等到最后计算余数将产生错误的结果，除非参数 K 是 2 的幂。

另请注意，选择类型 unsigned int因为结果将允许的 K 限制为最多 UINT_MAX + 1 ，并使用unsigned int因为内部累加器变量与 UINT_MAX - 254 之间的 K 值不一致和UINT_MAX (但是 UINT_MAX + 1 仍然可以)。

为了(主要)解决此问题，在添加每个字符后计算并存储模数，而不是等到最后才这样做。

如果您需要安置 K 靠近但小于 UINT_MAX + 1 ，那么您还需要注意加法溢出，并在发生溢出时进行更正。