c - 我应该使用什么哈希从一组字符串中生成随机值

Question

我在哈希桶中有一组指纹。我想插入存储桶并搜索它，而不是从条目 0 到条目 n。

我想做的是，当我将条目添加到存储桶中时，我使用指纹作为输入来计算哈希值，我可以使用该哈希值来确定要添加到哪个存储桶中。这并不困难，但是当我尝试使用相同的算法对指纹进行哈希处理以识别将指纹添加到存储桶中的哪个插槽时，我发现它会产生很多冲突。

这是我用来将指纹散列到存储桶中的代码。我尝试使用具有更多字符的相同代码，但它仍然给我带来更高的碰撞。

he.fingerprint is 33 characters wide

number of buckets is 1024

number of entries per bucket is 2048

    char hph[32];
int bk,en;
unsigned long h = 0, g,i=0;
int j=0;
strncpy(hph,(const char*)(he).fing_print,32);

while ( j<32 ) 
{
    h  =h + hph[j]++;
     g = h & 0xFFf00000;
    h ^= g >> 24;
    h &= ~g;
    j++;
}
bk=h%buckets;
en=h%entries_per_bk;

Answer 1

您的哈希函数中有一些多余的东西。

char hph[32];
int bk,en;
unsigned long h = 0, g,i=0;
int j=0;
strncpy(hph,(const char*)(he).fing_print,32);

while ( j<32 ) 
{
    h = h + hph[j]++;

这实际上是 h += hph[j];。索引 j 处的字符递增，但由于它再也不会被使用，因此根本不会影响散列。也许你的意思是预先增加它？但这不会有太大变化。

    g = h & 0xFFf00000;

指纹(或至少您使用的指纹的一部分)最多为 32 个字符。这些字符中的每一个都小于 256，因此总和小于 32*256 = 8192 = 0x2000，因此 h & 0xFFF00000 为 0。因此以下两行完全不对 h 做任何事情。

    h ^= g >> 24;
    h &= ~g;
    j++;
}
bk=h%buckets;
en=h%entries_per_bk;

实际上，您的哈希值是指纹前 32 个字符的总和。这不能很好地传播您的哈希值，相似的字符串会生成相似的哈希值。您可以通过将到目前为止的哈希值乘以一个较大的素数来获得更好的哈希值，

h = 0;
for(j = 0; j < 32; ++j)
    h = prime*h + hph[j];

因此任何索引处的小差异(最后一个索引除外，但您也可以再次乘以传播它们)会产生哈希值的大差异。