Действительно ли безопасно предположить, что GUID всегда будет уникален?
Я знаю, что существует мелкая возможность столкновения, но если бы я генерировал пакет 1 000 GUID (например), то было бы безопасно предположить, что они все уникальны для сохранения тестирования каждого?
Вопрос о премии
Оптимальный способ протестировать GUID на уникальность? Фильтр цветка, возможно?
5 ответов
Да, можно. Поскольку идентификаторы GUID имеют длину 128 бит, вероятность конфликта очень мала, но слово «минута» далеко не достаточно сильное. Идентификаторов GUID так много , что если вы сгенерируете несколько триллионов из них случайным образом, вероятность попадания метеорита будет выше, чем хотя бы одно столкновение (из Википедия ). И если вы не генерируете их случайным образом, а например. с использованием алгоритма MAC-адреса и отметки времени, тогда они также будут уникальными, поскольку MAC-адреса уникальны среди компьютеров, а отметки времени уникальны на вашем компьютере.
Редактировать 1: Чтобы ответить на ваш бонусный вопрос, оптимальный способ проверить набор GUID на уникальность - просто предположить, что все они уникальны. Почему? Потому что, учитывая количество GUID, которые вы генерируете, вероятность столкновения GUID меньше, чем вероятность того, что космический луч немного перевернется в памяти вашего компьютера и испортит ответ, данный любым «точным» алгоритмом, который вам небезразличен. бежать. (См. этот ответ StackOverflow для математических расчетов.)
Существует огромное количество GUID. Цитируя Дугласа Адамса Автостопом по Галактике :
«Космос, - говорится в нем, - большой. Действительно большой. Вы просто не поверите, насколько он невероятно велик. Я имею в виду вас. может подумать, что до химика еще далеко, но это всего лишь копейки в космос, послушайте… »
И поскольку во Вселенной около 7 × 10 22 звезд ] и чуть менее 2 128 GUID, то есть приблизительно 4,86 × 10 15 - почти пять квадриллионов - GUID для каждой отдельной звезды. Если бы у каждой из этих звезд был мир с таким процветающим населением, как наш, то вокруг каждой звезды каждый человек или инопланетянин, который когда-либо жил , имел бы право на более сорока пяти тысяч GUID. Для каждого человека в истории на каждой звезде во Вселенной. Пространство GUID находится на том же уровне огромности, что и размер всей вселенной. Вам не не беспокоиться.
( Редактировать 2: Размышляя над этим: вау. Я сам не осознавал, что это значит. Пространство GUID непостижимо огромно. Я как бы трепещу перед нем.)
Анализ возможности столкновения доступен в Википедии: http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates
Как указано в ссылке, на это будут влиять свойства генератора случайных чисел.
Существует также возможность ошибки в коде генератора GUID; хотя вероятность этого мала, она, вероятно, выше, чем вероятность столкновения, основанная на математике.
Может подойти фильтр Блума; он может быстро определить, является ли GUID уникальным, но есть вероятность ложного указания на столкновение. Альтернативный метод, если вы тестируете партию за раз, заключается в сортировке партии и сравнении каждого последующего элемента.
В целом, да, можно предположить.
Если ваш генератор GUID действительно случаен, вероятность столкновения в пределах 1000 GUID чрезвычайно мала.
Конечно, это предполагает хороший генератор GUID. Поэтому вопрос заключается в том, насколько вы доверяете инструменту, который используете для генерации GUID, и есть ли у него собственные тесты?
.Обычно это довольно безопасное предположение.
Хотя столкновение возможно, оно крайне маловероятно. (Math здесь .) Можно с уверенностью предположить, что они на самом деле различны.