Правила и рекомендации по переопределению GetHashCode
«Кодекс – это скорее рекомендации, нежели настоящие правила» – и это святая правда. При написании кода очень важно понимать, что является смутными «рекомендациям», которым стоит следовать, но можно нарушать или игнорировать, а что является жесткими «правилами» с серьезными негативными последствиями для корректности или надежности. Меня часто спрашивают о правилах и рекомендациях по переопределению метода GetHashCode, так что я решил рассказать здесь об этом.
Для чего используется метод GetHashCode ?
По определению этот метод полезен только для одного: для сохранения объекта в хеш-таблицу. Потому он так и называется.
А почему, вообще, этот метод определен в классе Object ?
Кажется абсолютно разумным, что каждый объект в системе типов должен содержать метод GetType; возможность данных описать самих себя является ключевой возможностью системы типов CLR. Разумно, чтобы каждый объект содержал метод ToString, чтобы можно было получить его строковое представление, например, для отладки. Вероятно, каждый объект должен иметь возможность сравнить себя с другими объектами на предмет равенства. Но почему каждый объект должен обладать возможностью получения его хеш-кода для вставки в хеш-таблицу? Кажется весьма странным требовать этого от каждого объекта.
Я думаю, если бы мы сейчас перепроектировали систему типов с нуля, хеширование было бы сделано по-другому, возможно с помощью интерфейса IHashable. Но при проектировании системы типов CLR не было обобщений и, таким образом, хеш-таблица общего назначения должна была иметь возможность сохранять любой объект.
Как хеш-таблицы и аналогичные структуры данных используют метод GetHashCode ?
Давайте рассмотрим абстрактный тип данных “set” (множество). Хотя существует много операций, которые мы бы хотели выполнить над множеством, есть две базовые операции: вставить новый элемент в множество и проверить существование определенного элемента в множестве. Мы хотим, чтобы эти операции выполнялись быстро даже для множеств большого размера. Давайте в качестве примера рассмотрим использование списка для реализации множества:
class Set<T>
{
private List<T> list = new List<T>();
public void Insert(T item)
{
if (!Contains(t))
list.Add(item);
}
public bool Contains(T item)
{
foreach(T member in list)
if (member.Equals(item))
return true;
return false;
}
}
(Из этой статьи я убрал весь код проверки ошибок; мы, вероятно, хотели бы, чтобы вставляемый элемент не равнялся null. Кроме того, вероятно, мы хотели бы реализовать некоторые интерфейсы и т.п. Я стараюсь сделать код как можно проще, чтобы сосредоточиться на части, связанной с хешированием.)
Проверка существования элемента осуществляется линейно; если список содержит десять тысяч элементов, тогда нам придется просмотреть все десять тысяч элементов для проверки того, находится объект в списке или нет. Этот подход плохо масштабируется.
Хитрость заключается в том, чтобы в обмен на небольшой дополнительный объем памяти получить значительную прибавку производительности. Идея заключается в создании множества более коротких списков, которые называются «сегментами» (buckets) и нахождении хитрого способа быстрого нахождения нужного сегмента:
class Set<T>
{
private List<T>[] buckets = new List<T>[100];
public void Insert(T item)
{
int bucket = GetBucket(item.GetHashCode());
if (Contains(item, bucket))
return;
if (buckets[bucket] == null)
buckets[bucket] = new List<T>();
buckets[bucket].Add(item);
}
public bool Contains(T item)
{
return Contains(item, GetBucket(item.GetHashCode());
}
private int GetBucket(int hashcode)
{
unchecked
{
// Хэш-значение может быть отрицательным и остаток от деления, соответственно, тоже.
// Выполняем вычисления над беззнаковыми целыми, чтобы гарантировать положительные значения.
return (int)((uint)hashcode % (uint)buckets.Length);
}
}
private bool Contains(T item, int bucket)
{
if (buckets[bucket] != null)
foreach(T member in buckets[bucket])
if (member.Equals(item))
return true;
return false;
}
}
Теперь, при наличии в множестве тысячи элементов, нам придется искать в одном из ста сегментов, каждый примерно со ста элементами; операция Contains стала в сто раз дешевле.
В среднем.
Мы надеемся.
Мы можем поступить еще умнее; как и List<T> увеличивает свой размер при заполнении, набор сегментов множества также может увеличивать свой размер, чтобы гарантировать небольшой средний размер сегмента. Кроме того, по техническим причинам обычно весьма разумно, чтобы размер сегмента был простым числом, большим 100. В эту реализацию мы можем внести множество улучшений. Но этот набросок реализации хеш-таблицы пока нам вполне достаточен. Я хочу, чтобы реализация оставалась простой.
Отталкиваясь от предположения, что этот код работающий, мы можем вывести правила и рекомендации, которым должен следовать метод GetHashCode:
Правило: одинаковые элементы должны иметь одинаковый хеш-код
Два одинаковых объекта должны иметь одинаковый хеш-код; или, соответственно, если два объекта имеют разный хеш-код, то они должны быть неравными.
Причина очень простая. Предположим, два одинаковых объекта имеют разный хеш-код. При добавлении первого объекта в множество, он будет добавлен в сегмент №12. Затем, когда вы спросите, находится ли второй объект в множестве, то, возможно, поиск будет осуществлен в сегменте №67 и этот элемент не будет найден.
Обратите внимание, что следующее высказывание правилом НЕ ЯВЛЯЕТСЯ: два объекта с одинаковыми хеш-кодами должны быть равными. Существует только 4 миллиарда возможных хеш-значений, однако возможных объектов явно может быть больше. Количество десятисимвольных строк значительно больше 4-х миллиардов. Таким образом, согласно принципу Дирихле существует как минимум два разных объекта с одинаковым хеш-значением. (*)
Рекомендация: значение, возвращаемое функцией GetHashCode никогда не должно изменяться
В идеале, хеш-код изменяемого объекта должен вычисляться только на основе неизменяемых полей, таким образом, хеш-значение объекта должно оставаться неизменным на протяжении всего времени жизни объекта.
Однако, эта рекомендация только для идеальных ситуаций, настоящее правило следующее:
Правило: значение, возвращаемое функцией GetHashCode , никогда не должно изменяться пока объект находится в структуре данных, рассчитывающей на неизменяемое значение хеш-кода
Так что вполне возможно, хотя и опасно, создавать объект, хеш-значение которого может изменяться при изменении полей объекта. Если у вас есть такой объект и вы поместили его в хеш-таблицу, тогда коду, изменяющему этот объект и коду, работающему с хеш-таблицей, требуется некоторый протокол, гарантирующий, что объект будет оставаться неизменным пока он находится в хеш-таблице. А что это будет за протокол – это уже зависит полностью от вас.
Если хеш-код объекта может изменяться, пока объект находится в хеш-таблице, тогда, очевидно, метод Contains перестает нормально работать. Вы добавляете объект в сегмент 5, изменяете его, а когда спрашиваете у множества, содержит ли оно измененный объект, оно ищет в сегменте 74 и не находит его.
Помните, объекты могут сохраняться в хеш-таблицах в неожиданных местах. Множество LINQ-операторов внутри используют хеш-таблицы. Не изменяйте объекты, возвращаемые в результате выполнения LINQ-запроса в процессе их перебора!
Правило: пользователи метода GetHashCode не могут рассчитывать на неизменность значения с течением времени, а также на идентичность значений в разных доменах
Предположим у нас есть объект класса Customer, который содержит ряд полей, таких как Name, Address и т.д. Если вы создаете два таких объекта с совершенно одинаковыми данными в разных процессах, они не обязаны возвращать один и тот же хеш-код. Если вы создали такой объект во вторник в одном процессе, закрыли его, и запустили программу снова в среду, хеш-код может быть другим.
Это приводило к проблемам в прошлом. В документации к методу System.String.GetHashCode явно сказано, что две одинаковые строки могут возвращать разные хеш-коды в разных версиях CLR, и на самом деле, так и происходит. Не сохраняйте хеш-коды в базе данных и не рассчитывайте, что они будут такими же всегда, это не так.
Правило: метод GetHashCode не должен генерировать исключение и должен завершаться
Получение хеш-кода – это простое вычисление целочисленного значения; так что нет причины, почему бы этот метод завершался неудачно. Реализация GetHashCode должны справляться с любым корректным состоянием объекта.
Мне иногда отвечают: «но для гарантии того, чтобы мой объект не помещался в хеш-таблицу, я хочу генерировать NotImpelemntedException из моего метода GetHashCode; я не хочу, чтобы этот объект располагали в хеш-таблице». Ну, хорошо, но в этом случае применимо последнее высказывание предыдущего правила; это означает, что ваш объект не может быть результатом множества LINQ-запросов, которые внутри для повышения быстродействия используют хеш-таблицы.
Но если этот метод не генерирует исключение, он, в конце концов, должен завершиться. Реализация метода GetHashCode, с бесконечным циклом не является разумной и не является корректной.
Это особенно важно, когда объекты содержат циклические ссылки. Если при определении хеш-кода объекта Alpha используется хеш-код объекта Beta, а хеш-код объект Beta использует хеш-код объекта Alpha, тогда мы будет выполнять этот код бесконечно (если ваша архитектура умеет оптимизировать хвостовую рекурсию) или получим переполнение стека и завершим процесс аварийно.
Рекомендация: реализация метода GetHashCode должна быть чрезвычайно быстрой
Основная идея метода GetHashCode заключается в оптимизации операций поиска; если вызов метода GetHashCode выполняется дольше сравнения всех десяти тысяч элементов, тогда вы не получите прироста производительности.
Я рассматриваю это, как «рекомендацию», а не «правило», поскольку оно слишком туманно. Когда медленно – это слишком медленно? Это вам решать.
Рекомендация: распределение хеш-кодов должно быть «случайным»
Под «случайным распределением» я подразумеваю следующее: если есть некоторая общность между хешируемыми объектами, тогда этой общности быть не должно в хеш-кодах этих объектов. Предположим в качестве примера мы вычисляем хеш-код объекта, который представляет собой широту и долготу точки. Набор этих точек весьма вероятно будет сгруппирован; весьма вероятно, что ваши точки будут представлять собой местоположения домов в одном городе или клапаны в одном нефтяном месторождении или что-то еще. Если сгруппированные данные приводят к сгруппированным значениям, то это может уменьшить количество сегментов и привести к проблемам производительности при увеличении размеров этих сегментов.
Я снова рассматриваю это как рекомендацию, а не правило, поскольку оно не совсем четкое, а не потому что не важное. Это очень важно. Но поскольку хорошее распределение и высокая скорость могут противоречить друг другу, очень важно найти правильный баланс между ними.
Я знаю это из своего глубокого, личного и очень болезненного опыта. Более десяти лет назад я написал алгоритм хеширования строк для хеш-таблицы, используемой серверами msn.com. Я думал, что распределение значений является достаточно случайным, но я допустил ошибку, и это оказалось не так. Выяснилось, что все сто тысяч строк длиной 5 и содержащие только цифры, всегда помещались в один из пяти сегментов вместо шестиста доступных. Ребята из msn.com использовали мою хеш-таблицу для быстрого поиска среди десяти тысяч почтовых индексов, каждый из которых был строкой из пяти цифр. Эта проблема, а также ошибка, связанная с многопоточностью, полностью накрыла производительность важной страницы сайта msn.com; было очень стыдно и это стоило кучу денег. Данные иногда могут быть сильно сгруппированными и хороший алгоритм хеширования должен принимать это во внимание.
В особенности будьте осторожными с исключающим ИЛИ (XOR). Очень распространенной техникой является объединение хеш-кодов с помощью «исключающего ИЛИ», но это не обязательно хороший подход. Предположим у вас есть структура данных, которая содержит строки с адресом доставки и домашним адресом. Даже если алгоритм хеширования каждой строки очень хорош, если эти две строки часто будут одинаковыми, тогда результатом объединение хеш-кодов с помощью исключающего или очень часто будет 0. При наличии избыточности в структуре данных, “ XOR ” может осложнить проблему распределения.
Проблема безопасности: если хешированная структура данных будет выбрана для атаки, тогда у вас будут серьезные проблемы
Когда я поломал ту страницу msn.com, это было случайностью, что выбранные данные плохо работали с моим алгоритмом. Но предположим, что страница собирала данные от пользователя и сохраняла в хеш-таблице для анализа на стороне сервера. Если пользователь является злоумышленником и может умышленно сгенерировать огромный объем данных, которые будут располагаться в одном и том же сегменте, тогда это может привести к атаке типа отказ в обслуживании, поскольку сервер будет тратить свое время для поиска данных в несбалансированной хеш-таблице. Если вы попали в такую ситуацию – проконсультируйтесь с экспертом. Существует возможность реализации метода GetHashCode, устойчивой к подобным атакам, но для этого потребуется эксперт в этой области.
Проблема безопасности: используйте GetHashCode по назначению
Метод GetHashCode предназначен только для одной вещи: балансировки хеш-таблицы. Не используйте его ни для чего другого. В особенности для следующего:
* Он не обеспечивает уникальный ключ для объекта; вероятность коллизии чрезвычайно высока.
* Он не обеспечивает криптографической стойкости, так что не используйте его, как часть цифровой подписи или проверки равенства паролей
* Он не обязательно обладает свойствами определения ошибок, необходимые для контрольных сумм.
И т.д.
Выполнять все эти правила невероятно сложно.
(*) Если у вас есть десять голубей, которые живут в девяти гнездах, то, как минимум в одном гнезде будет более одного голубя.
Comments
Anonymous
March 22, 2011
А если использовать готовые ф-ии из system.security.cryptography ? (к примеру md5)Anonymous
September 13, 2013
Автору большое спасибо за труды! Очень сложно иногда найти ответ, даже на самый простой вопрос.