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

Question

我在散列桶中有一个指纹数组。我想插入到桶中，并在它上搜索，从条目0到条目n。

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

这是我用来将指纹散列到桶中的代码。我尝试使用相同的代码和更多的字符，但它仍然会给我带来更高的冲突。

he.fingerprint是33个字符宽的

桶数为1024

每个bucket的条目数为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];

因此，任何索引上的微小差异（除了最后一个，但您也可以再次相乘来扩展这些差异）都会产生哈希的巨大差异。