Минимальное идеальное хеширование целых чисел в диапазоне двух оснований

Question

Я ищу простую хеш-функцию, которая бы принимала целое число в диапазоне от двух базовых и (случайным образом) хеш-функцию к другому целому числу в этом диапазоне без коллизий. Это будет использоваться для построения перестановки и предпочтительно из начального значения. Так что просто смещение целого числа и модуляция не будут работать. Кто-нибудь знает хороший вариант, написанный на C?

Спасибо джош

Answer 1

Я нашел хорошее решение в статье Эндрю Кенслера " Коррелированная многократная выборка ". Здесь перестановка строится с использованием функции смешения, состоящей только из обратимых операторов. Это гарантирует, что не будет никаких столкновений в степени два диапазона.

Функция была найдена итеративно с помощью программы восхождения на гору, которая оценивает каждого кандидата в соответствии с его свойством avalaunch. Кроме того, Кенслер обобщает хэш, чтобы учесть диапазоны, которые не являются степенью двойки, используя технику, называемую циклическая ходьба.

Благодаря этому, качеству результата, а также способности легко перемешать перестановку, предложенная функция является хорошим решением исходного вопроса. См. Статью Брета Малви о хеш-функциях здесь для получения дополнительной информации об обратимых операторах и генерации качественных функций смешивания.

Answer 2

Это может помочь (см. Нижнюю часть для более общего подхода): мультипликативные циклические группы позволяют вам выбрать k "начальное" значение, а n "максимальное" значение и перестановка натуральных чисел от нуля до n-1 очень эффективным способом (k может быть в Z, но предпочтительно оба натуральных числа). Единственное, что нужно, если вы хотите перестановку, это то, что n должно быть простым числом, и я не уверен, что все перестановки равномерно распределены по начальному пространству (некоторые знания по криптографии здесь очень помогли бы).

Тогда основная операция будет выглядеть примерно так в псевдокоде:

for i in range(0, n){ i:= (i*k)(mod n);}

а вот рабочая игрушка-программа на C:

#include <stdio.h>

int main(void)
{
  // take a prime number (from https://primes.utm.edu/lists/2small/0bit.html)
  //int n = (int)pow(2,13)-1;
  // for the sake of test, let's take a little one:
  int n = 23;
  // take a random integer seed:
  int k = 1234;
  printf("permutation of numbers from 0 below %d with seed %d:\n", n, k);
  for (int i=0; i<n; i++){
    printf("%d ", ((i*k)%n));
  }
  printf("\n");
  return 0;
}

который возвращает:

permutation of numbers from 0 below 23 with seed 1234:
0 15 7 22 14 6 21 13 5 20 12 4 19 11 3 18 10 2 17 9 1 16 8 

Это не совсем то, что вы хотите, но с некоторыми настройками это может работать нормально... если мы не говорим о высококлассных средствах безопасности. Вероятно, наиболее простым решением было бы выбрать простые числа, близкие к степени двух, и выполнить некоторые настройки? https://primes.utm.edu/lists/2small/

Дайте мне знать, если это поможет!

РЕДАКТИРОВАТЬ Я не мог помочь напрямую протестировать его на моем Emacs, так что вот функция для потомков:

(defun permute (n seed)
  "prints a permutation of the set of numbers between 0 and n-1, 
   provided n is prime"
  (let ((permuted (loop for i below n collect (% (* i seed) n))))
    (print permuted)
    ;(print (sort permuted '<)) ; debug print
    ))

(test 23  1234) ; returns (0 15 7 22 14 6 21 13 5 20 12 4 19 11 3 18 10 2 17 9 1 16 8)

РЕДАКТИРОВАТЬ 2 На самом деле, было бы достаточно, чтобы k а также n взаимно просты, как указано в теореме Безу. Технически, вы могли бы иметь произвольные натуральные значения для n если ты это обеспечишь. Простым, но ограниченным способом будет случайный выбор k из списка простых чисел. Возможно, лучшим решением будет рассчитать для каждого данного n его относительные простые числа, и выберите оттуда (обозначение: ни 8, ни 9 не являются простыми числами, но они взаимно просты, потому что 9(mod 8)= 1). Это не становится намного более "полным", чем это, но я все еще не знаю, как перестановки распределяются с этим подходом.