Ищем хеш-функцию / Упорядоченный Int / to / Shuffled Int /

Question

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

Создание перетасованного диапазона с использованием PRNG вместо перетасовки ответ erikkallen регистров сдвига с линейной обратной связью выглядит как нечто правильное. Я только что попробовал, но он производит повторы и дыры.

С уважением Дэвид Аллан Финч

Answer 1

Вопрос теперь в том, нужно ли вам действительно случайное отображение или просто «слабая» перестановка. Предполагая последнее, если вы оперируете 32-разрядными целыми числами без знака (скажем) в арифметике дополнения 2, умножение на любое нечетное число является биективным и обратимым отображением. Конечно, то же самое относится и к XOR, поэтому вы можете попытаться использовать простой шаблон, например:

unsigned int hash(int x) {
   return (((x ^ 0xf7f7f7f7) * 0x8364abf7) ^ 0xf00bf00b) * 0xf81bc437;
}

В числах нет ничего волшебного. Таким образом, вы можете изменить их, и они могут быть даже рандомизированы. Единственное, что мультипликаторы должны быть нечетными. И вы, должно быть, рассчитываете с помощью Rollaround (игнорируя переполнения). Это может быть перевернуто. Чтобы сделать инверсию, вы должны быть в состоянии вычислить правильные дополнительные мультипликаторы A и B, после чего инверсия равна

unsigned int rhash(int h) {
    return (((x * B) ^ 0xf00bf00b) * A) ^ 0xf7f7f7f7;
}

Вы можете вычислить A и B математически, но вам проще всего запустить цикл и найти их (то есть в автономном режиме).

В уравнении используются XOR, смешанные с умножениями, чтобы сделать отображение нелинейным.

Answer 2

Вы можете попробовать построить подходящую сеть Фейстеля . Обычно они используются для криптографии (например, DES), но не менее чем с 64 битами, поэтому вам может потребоваться создать такую, которая соответствует вашим потребностям. Они обратимы по конструкции.

Answer 3

Предполагая, что ваша цель - распределить сгруппированные значения по всему диапазону,
похоже, что перетасовка битов в некотором предопределенном порядке может помочь.
то есть, учитывая 8 битов ABCDEFGH, расположите их как EGDBHCFA или какой-то подобный шаблон.

Код будет простой последовательностью масок, сдвигов и добавлений.

Answer 4

Для набора ограничений действительно нет решения. Попытка хэширования 32-битного без знака в 32-битный без знака приведет к коллизиям, если вы не сделаете что-то простое, например, отображение 1: 1. Каждое число имеет свой собственный хэш.

Answer 5

Ммм ... в зависимости от того, много ли у вас чисел, вы можете использовать обычный список stl и упорядочить его по «случайным» критериям

bool
nonsort(int i, int j)
{
    return  random() & 31 >16 ? true : false;
}

std::list<int> li;
// insert elements
li.sort(nonsort);

Затем вы можете получить все целые числа с помощью обычного итератора. Не забудьте инициализировать случайное значение с помощью srand () со временем или любым другим псевдослучайным значением.