2011-09-16 7 views
0

したがって、長さnのchar *とintの2つの異なるフィールド型があります。私はキーとして両方を使用してハッシュ値を生成したい。私はint変数の最後の16ビットを追加し、合計整数xをコールし、次にcollat​​e:hashを使用してchar *のハッシュ値を生成します。これは整数yと呼ばれます。次に、x + yを加算し、合計でハッシュを使用してハッシュ値を生成します。私は[1,4]の範囲にハッシュ値を制限したいと言うことができます。私はちょうど私が欲しいものを得るために%4をハッシュ値できますか?また、2つのキーからハッシュ値を生成するより良い方法がある場合は、私に教えてください。ハッシュ関数とその仕組み

答えて

0

[1,4]の範囲については、hashvalue%4に1を加えなければなりません。ただし、4のハッシュは非常に小さいハッシュです。これにより、多くの衝突が発生し、ハッシュの有効性が制限されます(つまり、とは異なるフィールドの値がになります)。

サイズを追加することをお勧めします。ハッシュに、おそらく64K(16ビットハッシュ)。それは衝突を少なくします。また、すでにハッシュテーブルを実装しているstd::unordered_mapを使用しないでください。

最後に、ハッシュ関数ごとに、各フィールドの意味に依存します。たとえば、インプリメンテーションで整数の下位16ビットのみがカウントされる場合、ハッシュはそれらのビットのみに基づいている必要があります。文字列と整数には一般的なハッシュ関数があるので、それらの関数を使うことができます。最後に、両方のフィールドのハッシュ値を結合するには、それらを合計(またはxoring)するのが一般的な方法です。生成されたハッシュ値が可能な限り範囲内に均等に分散されていることを確認してください。だから、あなたは多くの言葉で説明すると書かれている

0

struct noname { 
    int ifield; 
    char[N] cfield; 
}; 

int hash(const noname &n) { 
    int x = n.ifield; 
    int y = ???(n.cfield); 
    return x + y; 
    // return (x + y) & 3; 
} 

このハッシュ関数が良いかどうかは、データに依存します。たとえば、ifieldが常に4の倍数である場合、それは明らかに悪いです。フィールドの値がほぼ均等に分散されていれば、すべて問題ありません。

ハッシュ範囲を[1;4]に制限するという要件を除いて、まず、[0;3]は計算が簡単です。次に、ハッシュコードが生成される2つまたは3つの異なるものしか持たない場合、そのような小さな範囲が適切です。範囲は、予想される異なる要素の数の少なくとも2倍にする必要があります。

関連する問題