c - C での 2 つの整数の高速双方向ハッシュ

Question

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

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

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

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

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

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

Answer 1

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

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);
}

Answer 2

((a | b) << 32) + (a & b)

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

Answer 3

#define MYHASH(a,b) ( (((UINT64) max(a,b)) << 32) | ((UINT64) min(a,b)) )

Answer 4

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

Answer 5

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