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

There are some superfluous things in your hashing function.

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

This is, effectively, h += hph[j];. The character at index j is incremented, but since it is never used again, that doesn't influence the hash at all. Perhaps you mean to preincrement it? But that wouldn't change much.

    g = h & 0xFFf00000;

The fingerprint (or at least the part of it you use) is 32 characters long at most. Each of those characters is less than 256, so the total sum is less than 32*256 = 8192 = 0x2000, hence h & 0xFFF00000 is 0. Thus the following two lines do exactly nothing to h. 

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

So effectively, your hash is the sum of the first 32 characters of the fingerprint. That doesn't spread your hashes well, similar strings generate similar hashes. You would obtain a better hash by multiplying the hash so far by a largish prime,

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

so that small differences at any index (except the last, but you could multiply once more to spread those too) can create large differences of the hash.

于 2012-03-07T17:37:32.157 に答える