Поиск функции хеширования/заказанных Int/to/Shuffled Int/

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

Генерация перетасованного диапазона с использованием PRNG, а не перетасовка erikkallen Линейные регистры сдвига обратной связи выглядят как правильные вещи. Я просто попробовал, но он производит повторы и дыры.

Отношения Дэвид Аллан Финч

Ответы

Ответ 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, смешанные с умножениями, чтобы сделать отображение нелинейным.

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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

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

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

Ответ 5

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