hash - SAT 前処理用のハッシュ関数

Question

句データベースで構成される SAT インスタンスの前処理中に、すべての変数に単語を割り当てる必要があります。ハッシュ関数は、変数ごとに 16 の最上位ビット (MSB) の 1 ビットと 16 の最下位ビット (LSB) の 1 ビットを除いて 0 のみで構成される 32 ビット ワードを返します。変数。句の署名は、すべての変数のハッシュ関数値のビットごとの OR です。

このハッシュ関数を実装するにはどうすればよいですか?

Answer 1

各ハーフワードには 16 の可能性があります。1 は 16 の場所にあります。これにより、16x16=256 の可能な「ハッシュ」が得られます。変数カウント > 256 の場合、確実に衝突が発生します。できることはv % 256、ハッシュ関数に渡す前に渡すことです。これはそのようなハッシュ関数の 1 つです。

unsigned int hash_variable(int v)
{
  v = v % 256

  assert(v < 256);

  unsigned char lower_nibble = v & 0x0f;
  unsigned char upper_nibble = (v & 0xf0) >> 4;

  assert(lower_nibble < 16);
  assert(upper_nibble < 16);

  unsigned int result = 0;

  result |= (1 << upper_nibble);
  result |= (1 << (lower_nibble + 16));
  return result;
}