0

该站点对旋转哈希的描述如下。

unsigned rot_hash ( void *key, int len )
{
    unsigned char *p = key;
    unsigned h = 0;
    int i;

    for ( i = 0; i < len; i++ )
        h = ( h << 4 ) ^ ( h >> 28 ) ^ p[i];

   return h;
}

此处返回值为 32 位。但是，我想返回一个 16 位的哈希值。为此，h在循环中进行如下分配是否正确？考虑h在这里声明为 16 位整数。

for ( i = 0; i < len; i++ )
          h = ( h << 4 ) ^ ( h >> 12 ) ^ p[i];
4

2 回答 2

4

最好保留大哈希，并且只在返回时截断，例如：

for ( i = 0; i < len; i++ )
    h = ( h << 4 ) ^ ( h >> 28 ) ^ p[i];

return h & 0xffff;

移位常数 4 和 28 可能不是最好的（简而言之：因为它们有一个公约数）

经过一些实验，我得出了以下哈希函数，它旨在使低位具有最大熵（这样可以使用 2 的幂表大小）（这是Wakkerbot中使用的）：

unsigned hash_mem(void *dat, size_t len)
{
unsigned char *str = (unsigned char*) dat;
unsigned val=0;
size_t idx;

for(idx=0; idx < len; idx++ )   {
        val ^= (val >> 2) ^ (val << 5) ^ (val << 13) ^ str[idx] ^ 0x80001801;
        }
return val;
}

0x80001801 的额外干扰并不是严格需要的，但如果散列项具有较长的公共前缀，则会有所帮助。如果这些前缀由 0x0 值组成，也会有所帮助。

于 2012-05-08T11:39:40.440 回答
2

很难用哈希来谈论“正确”，因为任何确定性的结果都可以被认为是正确的。也许散列分布不会那么好，但无论如何这个散列似乎并不是最强的。

通过您建议的更改，您将获得的数字仍然是 32 位数字，并且高 16 位不会为零。

最简单的做法是什么都不做，并将结果转换为unsigned short.

于 2012-05-08T10:51:23.930 回答