7

Linux カーネル モジュールを作成していますが、入力に 2 つの整数を使用するハッシュ関数を考え出す必要があります。コードはカーネル空間で実行されるため、利用できる標準ライブラリはありません。

基本的に、次のようなハッシュ関数が必要です。

hash(a, b) = c
hash(b, a) = c

a と b の受け入れ可能な入力は、符号なし 32 ビット整数です。ハッシュ関数は、符号なし 64 ビット整数を返す必要があります。これらの値は二分探索木で使用されるため、衝突 (つまり、hash(a, b) = c および hash(d, f) = c も同様) は望ましくありません。検索の結果は、可能な結果のリンクされたリストであり、a と b が実際に比較される場所で反復されます。したがって、ある程度の衝突は許容されますが、衝突が少ないほど、必要な反復が少なくなり、実行が速くなります。

パフォーマンスも非常に重要です。このルックアップは、ファイアウォール アプリケーションを作成しているため、システムで受信したすべてのパケットに使用されます (整数は、実際にはパケットの送信元と送信先のアドレスです)。この関数は、既存のネットワーク セッションを検索するために使用されます。

お時間をいただきありがとうございます。

4

5 に答える 5

6

それを行う方法の疑似コード:

if a>b
  return (a << 32) | b;
else 
  return (b << 32) | a;

これは hash(a,b) == hash(b,a) を満たし、完全な 64 ビット空間を利用し、衝突があってはなりません ...私は :)

32 ビット変数を直接シフトしないように注意してください。代わりに、中間の 64 ビット バッファーまたはインライン キャストを使用します。

uint64_t myhash(uint32_t a, uint32_t b)
{
    uint64 a64 = (uint64_t) a;
    uint64 b64 = (uint64_t) b;
    return (a > b) ? ((a64 << 32) | b64) : ((b64 << 32) | a64);
}
于 2012-08-02T22:34:02.077 に答える
3
((a | b) << 32) + (a & b)

可換であり、最小数の衝突につながるはずです。もっと考えなきゃいけないのに…。

于 2012-08-02T22:30:54.653 に答える
3
#define MYHASH(a,b) ( (((UINT64) max(a,b)) << 32) | ((UINT64) min(a,b)) )
于 2012-08-02T22:37:07.743 に答える
1

どう((uint64_t)max(a, b) << UINT64_C(32)) | (uint64_t)min(a, b))ですか?入力間にオーバーラップの可能性がないため、これにより衝突が完全に回避されます。ただし、入力値に依存するため、分布について話すことはできません。

于 2012-08-02T22:40:02.447 に答える
1

(a ^ b) | ((a ^ ~b) <<32);

于 2012-08-02T22:40:57.260 に答える