Функция для «равномерного распределения» последовательного числа в пространстве возможных значений

Question

Мне нужно сохранить кучу сущностей в Google AppEngine (или вы можете думать о любой другой хеш-таблице) под ключами, которые мне нужно создать из последовательный ввод.

В качестве примера предположим, что я использую только ключи с длиной десятичной цифры. Затем мне нужно сохранить один объект для ключа «0», один для ключа «1», один для ключа «2» и т. Д.

Проблема в том, что если я просто использую эту увеличивающуюся последовательность непосредственно в качестве ключей, это приведет к физическому хранению всех объектов, очень близких друг к другу, что может вызвать серьезные проблемы с производительностью. Details here. Для общей хеш-таблицы вы можете думать о том, что все записи не равномерно распределены по всем ковши, а вместо этого кластерируются всего в несколько ковшей, что также приводит к ухудшению производительности для поиска и т. Д.

Итак, я «Я ищу какую-то функцию для« повторного распределения »моих значений более равномерно по всему пространству доступных значений.

Чтобы остаться на примере одноразрядных ключей, я мог бы просто создать таблицу, содержащую случайную перестановку всех возможных значений, например [5,9,2,4,1,8,0,6, 3,7] и указатель на это. Затем, когда я храню записи 0, 1 и 2, которые будут расположены рядом друг с другом, я вместо этого назначу ключи 5, 9 и 2, которые будут более распространены по серверам или хэш-ведрам.

Но мне нужно найти способ сделать это для 156-битных чисел, и в этом случае таблица со случайной перестановкой всех значений невозможна.

У меня есть два требования:

• Всевозможные 156-битное число должно быть отображено на точно один значение (до 160-бит OK). Нет столкновения не допускаются
• Это должно быть вычислительно дешевым

Я нашел один способ сделать это: просто «шифровать» мое значение с SHACAL-1 или каким-либо другим 160bit шифра. Но это похоже на слишком много вычислительных усилий для того, чего я пытаюсь достичь. Может быть, какая-то псевдослучайная функция, которую я могу использовать с моим значением в качестве семени? Гарантировали ли они коллизии бесплатно?

Answer 1

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

ИЛИ

, если вам не нужно дополнительное пространство, вы можете сохранить пару <value-originalindex> и поместить их полностью в случайном порядке (используя некоторую функцию PRNG), повторяя в случае столкновения (или принимая во внимание уже используемые места). Теперь пары распределяются равномерно. Извлечение i-го элемента принимает O (N), где N - количество мест. Это цена для этого алгоритма.

ИЛИ

принимают только несколько случайных битов из ваших 156-битных значений и использовать их для формирования, давайте скажем, без знака индекса 12bit. Используйте этот индекс для выбора k-го ведра из вашего конечного пространства (ваше пространство разделено на 2^12 ковшей). Значения будут иметь тенденцию к агрегации только в том случае, если они используют одни и те же 12-битные случайные биты, что очень маловероятно, если вы их тщательно подберете ...Используйте оставшиеся 156-12 = 143 бит для смещения внутри ведер.

ИЛИ

создать фиксированную случайную перестановку из ваших 156 бит.