1

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

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

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

he.fingerprint 是 33 个字符宽

桶数为 1024

每个桶的条目数是 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;
4

1 回答 1

3

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

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];. indexj处的字符会递增，但由于它不再使用，因此根本不会影响散列。也许你的意思是预先增加它？但这不会有太大变化。

    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];

因此，任何索引处的微小差异（除了最后一个，但您也可以再次相乘以传播这些差异）可以创建散列的大差异。

于 2012-03-07T17:37:32.157 回答