Есть ли стандартный способ генерировать идентификационные номера один за другим, чтобы:
- Вы можете гарантировать или почти гарантировать, что вы избежите столкновений. (Под «почти гарантией» я подразумеваю, например, если вы сгенерировали совершенно случайные 24-значные числа, а вы «только» сгенерировали 1 миллион из них, то даже с учетом парадокса дня рождения вероятность столкновения будет небольшой.)
- Вы хотите, чтобы идентификационные номера были короткими, а не громоздкими — в частности, вы не хотите полагаться на длину идентификационного номера (и выбор случайных значений), чтобы избежать коллизий, как описано в предыдущем пункте. Вы должны сделать это как-то по-другому.
- Вы не хотите избегать коллизий каждый раз, когда создаете новое значение, просматривая все ранее существовавшие значения, чтобы увидеть, не использовалось ли оно уже. Это будет только поиск log(n) каждый раз в отсортированном списке, но предположим, что я все равно хочу этого избежать.
- Вы не хотите, чтобы идентификационный номер раскрывал какую-либо информацию о том, когда он был сгенерирован, или о том, сколько идентификационных номеров было сгенерировано между идентификационным номером X и идентификационным номером Y. Без этого условия проблема тривиальна; вы можете просто использовать время по часам (плюс некоторое случайное значение, достаточно большое, чтобы избежать коллизий между числами, сгенерированными в одном и том же значении времени по часам), или вы можете просто использовать последовательные целые числа (за исключением того, что теперь злоумышленник знает, что если кто-то сгенерирует значение идентификатора 5000 на 1 марта и значение ID 6000 1 апреля, между ними было сгенерировано 1000 других значений).
Я пытался найти тривиальный ответ, но ни один из тех, что я пробовал, не работал. Вы можете просто взять хэш SHA-256 чисел 1, 2, 3 и т. д. (плюс некоторый секретный ключ), но это та же проблема, что и выбор случайных чисел из доступного пространства — если вы полагаетесь на длина хэша (например, SHA-256), чтобы избежать коллизий, результирующие идентификационные номера будут длинными и громоздкими, и если вы сделаете хеш короче, вы увеличите вероятность коллизий.
Или вы можете генерировать новые идентификаторы, каждый раз увеличивая их на случайное значение от 1 до n вместо того, чтобы всегда увеличивать их на 1. возможность генерировать два идентификатора последовательно и делать это неоднократно, они могли бы вычислить n, или, если бы у них была возможность проверить, какие идентификаторы действительны, они могли бы проверить каждое число в некотором небольшом диапазоне, чтобы увидеть, насколько плотно упакованы действительные ID есть, из того и вычисляйте.
Единственное решение, которое я смог найти, заключается в следующем: во-первых, заранее проведите некоторую подготовительную работу. Для любого количества значений ID, которые вы ожидаете сгенерировать (скажем, 1 миллион), возьмите все целые числа от 1 до 1 миллиона и по порядку начните вычислять хэш каждого целого числа плюс секретный ключ. Обрежьте хеш до любого значения, которое вы считаете достаточно коротким. Но при достаточно коротком усечении вы ожидаете увидеть коллизии. Таким образом, каждый раз, когда вы генерируете новый усеченный хэш для заданного целого числа, проверяйте его на соответствие ранее сгенерированным значениям и, если есть коллизия, добавляйте это целое число в список L целых чисел, где хэш этого целого числа сталкивается с хэшем меньшего целого числа. (На самом деле, если вы планируете сгенерировать 1 миллион идентификаторов, во время его подготовительной работы вам придется пройтись немного последним 1 миллионом целых чисел, чтобы компенсировать те, которые вы пропустили.)
Затем во время выполнения, когда вы генерируете свои идентификаторы, вы просто начинаете с целочисленного счетчика. Каждый раз, когда вы создаете новый идентификатор, вы увеличиваете целое число и проверяете, есть ли оно в вашем списке L, и если да, вы пропускаете и переходите к следующему целому числу. (Это включает в себя «поиск в журнале n», что, по-видимому, нарушает одно из моих заявленных правил, но что я действительно хотел сделать, так это избежать необходимости сверять каждое новое значение идентификатора с каждым сгенерированным до сих пор значением; проверка L должна быть намного быстрее.) И вы можете настроить это для компромиссов (чем длиннее вы делаете усеченные хэши, тем короче будет L и, следовательно, тем короче будет проверка каждый раз, когда вы создаете новый идентификатор; но более длинные значения идентификатора могут быть нежелательными).
Но это похоже на взлом. Есть стандартный способ? Если нет, можете ли вы придумать лучший способ?
