16ビットの回転ハッシュ

Question

This siteは、次のように回転ハッシュの説明を与えます。

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

Answer 1

それはのように、大きなハッシュを維持し、かつ唯一のリターンに切り捨てることが最善である：彼らは公約数を持っているので：

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の値で構成される場合に役立ちます。

Answer 2

決定的な結果が正しいと考えることができるので、ハッシュで「正しい」と話すのは難しいです。おそらく、ハッシュ分布はそれほど良いものではないでしょうが、このハッシュはとにかく最強のようには見えません。

あなたが提案した変更でも、取得できる数値は32ビットの数値になり、上位16ビットはゼロになりません。

最も簡単なことは何も変更しないで、結果をunsigned shortにキャストすることです。