Как стать автором
Обновить

Комментарии 25

Это не Рихтер рекомендует, а МСДН. Рихтер писал, почему это плохо.

В данном случае плохо тем, что если а == b, то хеш-код у всех таких объектов будет 0.

Рекоменуется теперь использовать какой-то такой алгоритм (на память не помню, каждый раз гуглю его заново):

int A = простое число;
int B = другое просто число;
int hash = A;
unchecked
{
hash = hash * B + field;
}
Я уточню. В целях общего познания следует понимать, что строки (как, впрочем, и любые другие упорядоченные структуры данных) очень хорошо получается и рекомендуется хэшировать следующим образом.
Если строка — S, то хэш должен получаться так. Фиксируем число R, число M и итерируемся по всем элементам строки S:
hash -> (hash * R + S[i]) % M.
(Если мы хэшируем строку не из чисел, а из более сложных элементов, то S[i] нужно заменить на S[i].GetHashCode())
Иными словами, мы рассматриваем значение многочлена P(x) = S[0] * R^(n — 1) + S[1] * R^(n — 2) +… + S[n — 2] * R + S[n — 1] в точке R.
Чем это хорошо? Тем, что если взять M большим, а R — таким числом, что его порядок по модулю M — велик, то это даст очень хороший расброс степений R^i по модулю R, соответственно хэш будет очень «случайный». Подробнее об этом можно почитать, например, в Кнуте.
Ну и напоследок — хорошо себя зарекомендовал также полиномиальный хэш по модулю 2^32 (2^64) в точке, равной какому-нибудь большому простому числу — он работает немного быстрее, потому что можно забить на взятие по модулю и просто работать с переполнениями типа Int32 (Int64).
Нет, так не очень хорошо. Получается, что если у нас есть, например, бинарное дерево (каждый элемент T(a,b) содержит два элемента того же типа), то хэш-коды для деревьев T(T(a,b),T(c,d)) и T(T(a,c),T(b,d)) будут всегда одинаковы. Коммутативность проклятая… Я с этим намучился, когда строил хэш-коды для квадратиков в HashLife.
Ключевые слова в моём посте: упорядоченные структуры данных. То есть именно в таком виде полиномиальный хэш применим к массивам (векторам), спискам, строкам и т. п.
А деревья хэшируются обычно так: в вашем случае, когда ровно два сына у каждой вершины — выпишем элементы дерева в ЛКП-обходе (левый сын-корень-правый сын) и захэшируем как массив.
Это, естественно, в случае, если мы различаем левого и правого сына. Если мы не различаем правого и левого сына, то делаем что-то похожее на полиномиальный хэш: hash[v] = S(hash[v->l], hash[v->r]) * R^d, где d — глубина вершины, а S(a, b) — симметричная нетривиальная функция от a, b. Например, подойдёт какой-нибудь (a + b)^2 + a^3 + b^3.
То есть, для вычисления хэш-кода только что сформированного дерева из двух поддеревьев, хэш-коды которых известны, вам придется лишний раз обойти левое поддерево, чтобы хотя бы пересчитать его элементы? Сложно будет, особенно, если многие поддеревья в дереве дублируются, и общее число элементов превышает 2^64… Но тоже лечится, если специально предусмотреть.
Нет, зачем? Видимо, если мы формируем хэш из деревьев l и r, и получаем дерево v, то hash[v] = hash[l] * R^[r->size() + 1] + v->value() * R^[r->size()] + hash[r], если степени числа R мы предподсчитали, то переход вышел за O(1).
А про деревья, в которых 2^64 элементов. Научите такие целиком хранить с четырьмя гигабайтами оперативки? :-)
Легко:
Tree tr=new Tree(null,null,1);
for(int i=0;i<128;i++) tr=new Tree(tr,tr,0);

Получите дерево с 2^128 листьев. Правда, во всех записано число 1, но если вы не собираетесь модифицировать деревья, а только строите новые, то оно работать будет. Например, может использоваться, как дерево какой-нибудь игры (каждый узел — своя ситуация, а ситуации, полученные в разных партиях, могут совпадать). И там качественная хэш-функция не помешает.
Да. Только не забудьте напомнить, что size() вам придется хранить в самом дереве, чтобы не вычислять. Да и предпосчитать степени непросто, тут даже 2^64 элементов не нужно. Но за log(size) работать будет.
А еще вместе с hash-функцией можно хранить R^size() — и тогда действительно все решится за O(1). Но кто так в реальности делает?
А, понял что вы имели в виду под такими гигантскими деревьями :-)
Да, вы правы, проще всего хранить R^size(), оно пересчитывается за O(1).
Кто так делает в реальности? Не могу сказать, не знаю. Могу лишь сказать, что методика, по-видимому, очень эффективная. Могу сказать что в алгоритмическом программировании, например, в олимпиадном — это часто употребимая методика.
Это Bernstein Hash — простой в реализации, очень быстрый и дает хорошее распределение, правда мы у себя используем его модифицированную версию (описан там же, чуть ниже по ссылке).
Решарпер умеет генерировать Equality members, за что ему большое спасибо. Нужно всего лишь отметить поля/свойства, которые вы хотите задействовать. Остается только не забыть обновить реализацию этих методов при добавлении новых полей.
Точно-точно. Хотел об этом написать. Возможно, добавлю в качестве апдейта.
Небольшое дополнение про IEquatable.
При вызове виртуального метода у типа-значения происходит его боксинг, а при вызове интерфейсного метода — нет. Интерфейс IEquatable был введен именно для возможности сравнения без лишних боксингов.
Стоит отметить, что без четкого понимания для чего, и на что это повлияет, лучше не переопределять Equals и GetHashCode — можете добавить пару часов дебага тем, кто ваш класс будет использовать.

ИМХО, лучшее руководство по GetHashCode:
Сорри ссылку забыл: здесь.
НЛО прилетело и опубликовало эту надпись здесь
Он может и применяться для проверки равенства в случае, если явное сравнение — дорогая операция, а взятие хэша — дешёвая. И только в случае положительно срабатывания мы в явную сравниваем элементы. Это часто употребимая методика — использовать в качестве компаратора (a.GetHashCode() == b.GetHashCode() && a == b)
(Я же правильно считаю, что в C#второй операнд коньюнкции не будет вычисляться, если первый false?)
1. часто неизвестно кто и как будет использовать ваш класс, а меняя GetHashCode вы меняете поведение стандартных коллекций (HashSet, Dictionary), которые будут хранить инстансы этого класса — кого-то ждет сюрприз.

2. GetHashCode в .Net'е заведен только чтобы поддержать хэш таблицы, поэтому использовать его не по назначению ИМХО не очень правильно.

3. Если говорить об оптимизации сравнения: я б тогда уж завел отдельный метод что-то типа if(a.EqualsOptimized(b))
Так я о чём и говорю. Ваш третий пункт я предлагаю реализовать как я указал выше — проверяя сначала равенство хэшей, а потом и самих объектов.
А насчёт первых двух. То, что в стандартных библиотеках метод GetHashCode() используется только для хэш-таблиц (в чём я, кстати, не уверен, но спорить не буду), не значит, что его нельзя ни для чего использовать. От хэша что в хэш-таблице, что в целях сравнения объектов требуется редкость коллизий и «случайность» распределения. Если мы гарантируем эти два свойства, то от перегрузки GetHashCode() не пострадают ни стандартный хэш-таблицы, они также будут нормально работать с нашими инстансами, ни предлагаемые мною плюшки от использования хэшей, например, в компараторах.
НЛО прилетело и опубликовало эту надпись здесь
Ещё раз. От хэш-функции никто не требует, чтобы разные объекты имели разные хэши. Более того, коллизии гарантированно будут, если пространство объектов имеет размер больше чем 2^32.
С другой стороны, если a.GetHashCode() != b.GetHashCode(), то a гарантированно не равно b. И это избавляет нас от необходимости делать дорогую проверку a == b, которую мы обязательно будем делать, но только в случае совпадания хэшей.

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

Можно поподробнее про это?
НЛО прилетело и опубликовало эту надпись здесь
ой-ой-ой. Промазал ответом.
Знаете, вы меня заинтересовали. Надо бы поразбираться, что там в MSDN'е про хэши вообще пишут. Второй и третий пункты мы не затрагиваем — я предлагаю лишь использовать первый пункт в качестве промежуточной проверки при сравнении. И честно — я не понимаю, почему они рекомендуют не использовать хэши ни для чего другого. Тем более, если мы их руками реализуем и гарантируем хорошее распределение — то есть сохраняем работоспособность хэш-таблицы. Да и взятие хэша действительно дешёвая операция, что до перегрузки, что после.

А насчёт смены алгоритмов высчитывания хэшей — тут я согласен, никак нельзя опираться на какие-то знания, о том как устроен неперегруженный хэш внутри фреймворка не стоит.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории