Можно ли предположить, что GUID всегда будет уникальным?

Question

Можно ли предположить, что GUID всегда будет уникальным?

Я знаю, что есть минутная возможность столкновения, но если я сгенерировал партию из 1000 GUID (например), было бы безопасно предположить, что все они уникальны, чтобы сохранить тестирование каждого из них?

дополнительный вопрос

оптимальный способ проверить GUID на уникальность? Блум фильтр может быть?

613 6

math probability unique guid collision

6 ответов:

Comments

Ничего не найдено.

Antal Spector-Zabusky · Accepted Answer · 2017-05-23 14:33:26

да, можно. Поскольку GUID имеют длину 128 бит, существует, по общему признанию, минутная возможность столкновения, но слово "минута" нигде не достаточно сильно. Есть так много GUID что если создать несколько триллионов из них случайно, вы все еще более вероятно, чтобы попасть под метеорит, чем иметь даже одно столкновение (от Википедия). И если вы не генерируете их случайным образом, но например использование Алгоритм MAC-адреса и отметки времени, то они также будут уникальными, так как MAC-адреса уникальны среди компьютеров и метки времени уникальны на код компьютер.

Edit 1: чтобы ответить на ваш бонусный вопрос, оптимальный способ проверить набор GUID на уникальность-просто предположить, что все они уникальны. Зачем? Потому что, учитывая количество GUID, которые вы генерируете, вероятность столкновения GUID меньше, чем вероятность перелистывания космического луча немного в памяти вашего компьютера и испортить ответ, данный любым "точным" алгоритмом, который вы хотели бы запустить. (См.этот ответ StackOverflow для математика.)

есть огромный количество GUID там. Цитируя Дугласа Адамса Автостопом по Галактике:

"пространство", он говорит, "это большая. Действительно большой. Вы просто не поверите, насколько он невероятно умопомрачительно велик. Я имею в виду, вы можете подумать, что это долгий путь вниз по дороге к химику, но это всего лишь орешки в космос, слушай..."

и около 7×10²² звезды во Вселенной, и чуть меньше 2¹²⁸ GUIDs, то есть примерно 4,86×10¹⁵-почти пять квадриллионов-GUID для каждой звезды. Если бы у каждой из этих звезд был мир с процветающим населением, как у нас, то вокруг каждой звезды, каждый человек или иностранец, который когда-либо жил будет иметь право на более чем сорок пять тысяч GUID. Для каждого человека в истории на каждой звезде во Вселенной. Пространство GUID находится на том же уровне огромности, что и размер всей Вселенной. Вы делаете не нужно беспокоиться.

(Edit 2: размышляя об этом: Вау. Я и не догадывался сам что это значит. Идентификатор GUID пространства непостижимо огромным. Я в благоговейном страхе перед ним.)

Mechanical snail · Accepted Answer · 2017-05-23 15:26:42

короткий ответ: для практических целей, да.

однако, вы должны рассмотреть парадокс дня рождения!

я вычислил несколько репрезентативных вероятностей столкновения. С 122-битными UUIDs, как указано в Википедия вероятность столкновения равна 1/2, если вы генерируете не менее 2.71492e18 UUIDs. С 10^19 UUIDs, вероятность 0.999918. С 10^17 UUIDs, 0.000939953.

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

Если вы генерируете 1 миллиард UUIDs в секунду,it займет около 36 лет чтобы получить вероятность столкновения 10%.

В конце концов, вероятно, произойдет столкновение между множеством UUID, генерируемых в течение человеческой истории. Тем не менее, вероятность того, что столкнувшиеся UUIDs будут использоваться для той же цели, исчезающе мала, поэтому на практике нет никаких проблем.

Mark Ransom · Accepted Answer · 2010-06-05 00:17:54

анализ возможности столкновения доступен в Википедии:http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

Как указано в ссылке, это будет зависеть от свойств генератора случайных чисел.

существует также возможность ошибки в коде генератора GUID; в то время как шансы низки, они, вероятно, выше, чем шансы столкновения на основе математики.

Цветение фильтр может быть подходящим; он может быстро сказать вам, является ли GUID уникальным, но есть вероятность ложного указания на столкновение. Альтернативный метод, если вы тестируете пакет в то время, чтобы отсортировать пакет и сравнить каждый последующий элемент.

Haacked · Accepted Answer · 2010-06-05 00:20:23

В общем, да можно смело предположить.

Если ваш генератор GUID действительно случайный, возможности столкновения в пределах 1000 GUID чрезвычайно малы.

конечно, это предполагает хороший генератор GUID. Итак, вопрос действительно в том, насколько Вы доверяете инструменту, который вы используете для создания GUID, и есть ли у него свои собственные тесты?

VeeArr · Accepted Answer · 2017-05-23 15:18:34

хотя столкновение возможно, это крайне маловероятно. (Математика здесь.) Можно с уверенностью предположить, что они на самом деле различны.

Brad · Accepted Answer · 2017-05-23 14:47:36

обычно это довольно безопасное предположение.

http://en.wikipedia.org/wiki/Globally_Unique_Identifier

- это идентификатор GUID, уникальный 100% времени?