Чаще, чем просто один раз, я вижу вопросы вроде таких:
У меня есть процедура, которая создаёт строки динамически. И мне нужна формула, которая берёт строку и делает небольшой уникальный идентификатор для этой строки (хэш-код), так что две одинаковые строки имели бы одинаковый идентификатор, а две различные строки - различный. Я пытался использовать String.GetHashCode, но у неё есть случайные совпадения. Какой есть способ, чтобы создать уникальный хэш?
Если вы можете как-то ограничить набор допустимых строк, то вы можете суметь выдавить из этого ограничения уникальность. К примеру, если предметная область допускает только ограниченное количество строк, то вы можете разработать так называемый "perfect hash" - функцию, которая гарантирует отсутствие коллизий для заданной предметной области.
В общем случае, когда вы не знаете, какие строки у вас могут быть, это невозможно. Предположим, ваш хэш-значение - это 32-х битное значение. Это означает, что у вас есть 232 возможных хэш-значений. Но возможных строк-то у вас всяко больше, чем 232. Поэтому, согласно принципу Дирихле, у вас обязательно найдутся хотя бы две строки, с одинаковым хэш-кодом.
Это всё в теории. А на практике какой-нибудь SHA или MD5 гарантирует неравенство хеш-кода для любых разных строк. Те случаи, когда это не так, 99.999999% пользователей могут смело игнорировать.
ОтветитьУдалитьВзаимоисключающие параграфы: "гарантирует неравенство" и "те случаи, когда это не так".
ОтветитьУдалить