Уникальный код в стиле Тинюрля: потенциальный алгоритм предотвращения столкновений
У меня есть система, которая требует уникальный 6-значный код для представления объекта, и я пытаюсь придумать хороший алгоритм для их генерации. Вот предварительные требования:
- Я использую систему base-20 (без заглавных букв, цифр, гласных или l, чтобы избежать путаницы и шуток)
- База-20 позволяет 64 миллиона комбинаций
- Я буду вставлять потенциально 5-10 тысяч записей одновременно, поэтому теоретически я бы использовал массовые вставки, что означает, что использование уникального ключа, вероятно, не будет эффективным или привлекательным (особенно если будет много коллизий)
- Не исключено, что можно заполнить 10% комбинаций, так что существует большой потенциал для большого количества столкновений.
- Я хочу убедиться, что коды не являются последовательными
У меня была идея, которая звучала так, как будто она будет работать, но я не достаточно хорош в математике, чтобы понять, как ее реализовать: если я начну с 0 и увеличу на N, то преобразую в base-20, похоже, что быть некоторым значением для N, которое позволяет мне считать каждое значение от 0 до 63 999 999, прежде чем повторять любое.
Например, переходя от 0 до 9, используя N=3 (т. Е. 10 mod 3): 0, 3, 6, 9, 2, 5, 8, 1, 4, 7.
Существует ли какой-то магический математический метод для определения значений N для некоторого большего числа, который может пересчитывать весь диапазон без повторения? В идеале номер, который я выбрал, должен был прыгать вокруг набора таким образом, чтобы не было очевидно, что был шаблон, но я не уверен, насколько это возможно.
Альтернативно, алгоритм хеширования, который гарантировал бы уникальность для значений 0-64 миллионов, сработал бы, но я слишком туп, чтобы знать, возможно ли это.
6 ответов
Все, что вам нужно, это число, которое не имеет общих факторов с вашим ключевым пространством. Самое простое значение - использовать простое число. Вы можете Google для больших простых чисел, или использовать http://primes.utm.edu/lists/small/10000.txt
Любое простое число, которое не является фактором длины последовательности, должно быть в состоянии охватить последовательность без повторения. Для 64000000 это означает, что вы не должны использовать 2 или 5. Конечно, если вы не хотите, чтобы они генерировались последовательно, генерирование их на расстоянии 2 или 5, вероятно, также не очень хорошо. Мне лично нравится номер 73973!
Есть другой способ получить аналогичный результат (перепрыгивая через весь набор значений без повторения, не последовательно), без использования простых чисел - с помощью последовательностей максимальной длины, которые вы можете генерировать с помощью специально созданных регистров сдвига.
@ Ник Льюис:
Ну, только если простое число не делит 64 миллиона. Таким образом, для целей опрашивающего числа, такие как 2 или 5, вероятно, не рекомендуется.
Моя математика немного ржавая, но я думаю, что вам просто нужно убедиться, что GCF с N и 64 миллионами равен 1. Я бы выбрал простое число (которое не делится равномерно на 64 миллиона) на всякий случай.
Не изобретайте велосипед: http://en.wikipedia.org/wiki/Universally_Unique_Identifier