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 に答える