Является ли хеш GUID уникальным?

Question

Я создаю GUID (в виде строки) и получаю его хэш. Могу ли я считать этот хеш уникальным?

Answer 1

Не такой надежный, как сам GUID, нет.

Просто для расширения вы уменьшаете свою уникальность в 4 раза, увеличивая число возможных комбинаций с 16 до 4 байтов.

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

Answer 2

Нет.

Смотрите здесь, если вы хотите мини GUID: http://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

Answer 3

Одним словом, нет.

Предположим, что в вашем хэше меньше битов, чем в GUID, по принципу «дырчатого голубя» должно существовать более одного сопоставления некоторого GUID -> хэша просто потому, что хешей меньше, чем в GUIDS.

Если мы предположим, что хеш имеет большее количество бит, чем GUID, существует очень малая, но конечная вероятность возникновения коллизии, при условии, что вы используете хорошую хеш-функцию.

Answer 4

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

Хорошие алгоритмы хеширования сводят к минимуму вероятность этого, и, как правило, чем больше битов в хэше, тем меньше вероятность столкновения.

Answer 5

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

fyi Для хорошего описания того, как работают хеш-таблицы, прочитайте принятый ответ на Что такое хеш-таблицы и хеш-карты и их типичные варианты использования?

Answer 6

Это не гарантировано , поскольку коллизии хешей . Сам GUID почти гарантированно будет.

По практическим причинам вы, вероятно, можете предположить, что хеш уникален, но почему бы не использовать сам GUID?

Answer 7

Я хотел бы хэшировать GUID в размере X с осознанием того, что иногда у меня есть 10 или меньше GUIDS в наборе, чтобы я мог избежать короткого хэша без коллизий, чем если бы у меня было 10 000 000 GUID в наборе. Я просто хотел бы иметь возможность указать размер хеша при вызове функции.

Answer 8

Если вы используете криптографический хеш (MD5, SHA1, RIPEMD160), хеш будет уникальным (коллизии по модулю, которые очень маловероятны - SHA1 используется, например, для цифровых подписей, а MD5 также устойчив к коллизиям при random входы ). Хотя зачем вам хешировать GUID?