среда, 3 ноября 2010 г.

Понимание хэш-кодов

Это перевод Understanding hash codes. Автор: Реймонд Чен.

Чаще, чем просто один раз, я вижу вопросы вроде таких:
У меня есть процедура, которая создаёт строки динамически. И мне нужна формула, которая берёт строку и делает небольшой уникальный идентификатор для этой строки (хэш-код), так что две одинаковые строки имели бы одинаковый идентификатор, а две различные строки - различный. Я пытался использовать String.GetHashCode, но у неё есть случайные совпадения. Какой есть способ, чтобы создать уникальный хэш?

Если вы можете как-то ограничить набор допустимых строк, то вы можете суметь выдавить из этого ограничения уникальность. К примеру, если предметная область допускает только ограниченное количество строк, то вы можете разработать так называемый "perfect hash" - функцию, которая гарантирует отсутствие коллизий для заданной предметной области.

В общем случае, когда вы не знаете, какие строки у вас могут быть, это невозможно. Предположим, ваш хэш-значение - это 32-х битное значение. Это означает, что у вас есть 232 возможных хэш-значений. Но возможных строк-то у вас всяко больше, чем 232. Поэтому, согласно принципу Дирихле, у вас обязательно найдутся хотя бы две строки, с одинаковым хэш-кодом.

2 комментария:

  1. Это всё в теории. А на практике какой-нибудь SHA или MD5 гарантирует неравенство хеш-кода для любых разных строк. Те случаи, когда это не так, 99.999999% пользователей могут смело игнорировать.

    ОтветитьУдалить
  2. Взаимоисключающие параграфы: "гарантирует неравенство" и "те случаи, когда это не так".

    ОтветитьУдалить

Можно использовать некоторые HTML-теги, например:

<b>Жирный</b>
<i>Курсив</i>
<a href="http://www.example.com/">Ссылка</a>

Вам необязательно регистрироваться для комментирования - для этого просто выберите из списка "Анонимный" (для анонимного комментария) или "Имя/URL" (для указания вашего имени и ссылки на сайт). Все прочие варианты потребуют от вас входа в вашу учётку (поддерживается OpenID).

Пожалуйста, по возможности используйте "Имя/URL" вместо "Анонимный". URL можно просто не указывать.

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