Хеш-функция для предварительной обработки SAT

Question

Во время предварительной обработки экземпляра SAT, состоящего из базы данных предложений, каждой переменной должно быть присвоено слово. Хэш-функция возвращает для каждой переменной 32-битное слово, состоящее только из 0, за исключением одного бита среди 16 старших значащих битов (MSB) и одного бита среди 16 младших значащих бит (LSB), которые установлены в 1 в зависимости от переменная. Сигнатура предложения - это побитовое ИЛИ значений хеш-функций всех его переменных.

Как мне реализовать эту хэш-функцию?

Answer 1

Ну, каждое слово имеет 16 возможностей;1 может быть в 16 местах.Это дает 16x16 = 256 возможных «хэшей».Для переменной count> 256 у вас обязательно будут коллизии.Что вы можете сделать, это передать v % 256 перед передачей его хэш-функции.Это одна из возможных таких хеш-функций:

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