Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 25
Это не Рихтер рекомендует, а МСДН. Рихтер писал, почему это плохо.
В данном случае плохо тем, что если а == b, то хеш-код у всех таких объектов будет 0.
Рекоменуется теперь использовать какой-то такой алгоритм (на память не помню, каждый раз гуглю его заново):
int A = простое число;
int B = другое просто число;
int hash = A;
unchecked
{
hash = hash * B + field;
}
В данном случае плохо тем, что если а == 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).
Если строка — 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 элементов. Научите такие целиком хранить с четырьмя гигабайтами оперативки? :-)
А про деревья, в которых 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, но если вы не собираетесь модифицировать деревья, а только строите новые, то оно работать будет. Например, может использоваться, как дерево какой-нибудь игры (каждый узел — своя ситуация, а ситуации, полученные в разных партиях, могут совпадать). И там качественная хэш-функция не помешает.
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). Но кто так в реальности делает?
А еще вместе с hash-функцией можно хранить R^size() — и тогда действительно все решится за O(1). Но кто так в реальности делает?
А, понял что вы имели в виду под такими гигантскими деревьями :-)
Да, вы правы, проще всего хранить R^size(), оно пересчитывается за O(1).
Кто так делает в реальности? Не могу сказать, не знаю. Могу лишь сказать, что методика, по-видимому, очень эффективная. Могу сказать что в алгоритмическом программировании, например, в олимпиадном — это часто употребимая методика.
Да, вы правы, проще всего хранить R^size(), оно пересчитывается за O(1).
Кто так делает в реальности? Не могу сказать, не знаю. Могу лишь сказать, что методика, по-видимому, очень эффективная. Могу сказать что в алгоритмическом программировании, например, в олимпиадном — это часто употребимая методика.
Это Bernstein Hash — простой в реализации, очень быстрый и дает хорошее распределение, правда мы у себя используем его модифицированную версию (описан там же, чуть ниже по ссылке).
Решарпер умеет генерировать Equality members, за что ему большое спасибо. Нужно всего лишь отметить поля/свойства, которые вы хотите задействовать. Остается только не забыть обновить реализацию этих методов при добавлении новых полей.
Небольшое дополнение про IEquatable.
При вызове виртуального метода у типа-значения происходит его боксинг, а при вызове интерфейсного метода — нет. Интерфейс IEquatable был введен именно для возможности сравнения без лишних боксингов.
При вызове виртуального метода у типа-значения происходит его боксинг, а при вызове интерфейсного метода — нет. Интерфейс IEquatable был введен именно для возможности сравнения без лишних боксингов.
Стоит отметить, что без четкого понимания для чего, и на что это повлияет, лучше не переопределять Equals и GetHashCode — можете добавить пару часов дебага тем, кто ваш класс будет использовать.
ИМХО, лучшее руководство по GetHashCode:
ИМХО, лучшее руководство по GetHashCode:
Сорри ссылку забыл: здесь.
Он может и применяться для проверки равенства в случае, если явное сравнение — дорогая операция, а взятие хэша — дешёвая. И только в случае положительно срабатывания мы в явную сравниваем элементы. Это часто употребимая методика — использовать в качестве компаратора (a.GetHashCode() == b.GetHashCode() && a == b)
(Я же правильно считаю, что в C#второй операнд коньюнкции не будет вычисляться, если первый false?)
(Я же правильно считаю, что в C#второй операнд коньюнкции не будет вычисляться, если первый false?)
1. часто неизвестно кто и как будет использовать ваш класс, а меняя GetHashCode вы меняете поведение стандартных коллекций (HashSet, Dictionary), которые будут хранить инстансы этого класса — кого-то ждет сюрприз.
2. GetHashCode в .Net'е заведен только чтобы поддержать хэш таблицы, поэтому использовать его не по назначению ИМХО не очень правильно.
3. Если говорить об оптимизации сравнения: я б тогда уж завел отдельный метод что-то типа if(a.EqualsOptimized(b))
2. GetHashCode в .Net'е заведен только чтобы поддержать хэш таблицы, поэтому использовать его не по назначению ИМХО не очень правильно.
3. Если говорить об оптимизации сравнения: я б тогда уж завел отдельный метод что-то типа if(a.EqualsOptimized(b))
Так я о чём и говорю. Ваш третий пункт я предлагаю реализовать как я указал выше — проверяя сначала равенство хэшей, а потом и самих объектов.
А насчёт первых двух. То, что в стандартных библиотеках метод GetHashCode() используется только для хэш-таблиц (в чём я, кстати, не уверен, но спорить не буду), не значит, что его нельзя ни для чего использовать. От хэша что в хэш-таблице, что в целях сравнения объектов требуется редкость коллизий и «случайность» распределения. Если мы гарантируем эти два свойства, то от перегрузки GetHashCode() не пострадают ни стандартный хэш-таблицы, они также будут нормально работать с нашими инстансами, ни предлагаемые мною плюшки от использования хэшей, например, в компараторах.
А насчёт первых двух. То, что в стандартных библиотеках метод GetHashCode() используется только для хэш-таблиц (в чём я, кстати, не уверен, но спорить не буду), не значит, что его нельзя ни для чего использовать. От хэша что в хэш-таблице, что в целях сравнения объектов требуется редкость коллизий и «случайность» распределения. Если мы гарантируем эти два свойства, то от перегрузки GetHashCode() не пострадают ни стандартный хэш-таблицы, они также будут нормально работать с нашими инстансами, ни предлагаемые мною плюшки от использования хэшей, например, в компараторах.
Ещё раз. От хэш-функции никто не требует, чтобы разные объекты имели разные хэши. Более того, коллизии гарантированно будут, если пространство объектов имеет размер больше чем 2^32.
С другой стороны, если a.GetHashCode() != b.GetHashCode(), то a гарантированно не равно b. И это избавляет нас от необходимости делать дорогую проверку a == b, которую мы обязательно будем делать, но только в случае совпадания хэшей.
Можно поподробнее про это?
С другой стороны, если a.GetHashCode() != b.GetHashCode(), то a гарантированно не равно b. И это избавляет нас от необходимости делать дорогую проверку a == b, которую мы обязательно будем делать, но только в случае совпадания хэшей.
Кстати, внутренние версии дотнетовских библиотек специально меняют алгоритм генерирования хешей при каждой компиляции, чтобы удостовериться, что хеш обьектов не используется при сравнении.
Можно поподробнее про это?
ой-ой-ой. Промазал ответом.
Знаете, вы меня заинтересовали. Надо бы поразбираться, что там в MSDN'е про хэши вообще пишут. Второй и третий пункты мы не затрагиваем — я предлагаю лишь использовать первый пункт в качестве промежуточной проверки при сравнении. И честно — я не понимаю, почему они рекомендуют не использовать хэши ни для чего другого. Тем более, если мы их руками реализуем и гарантируем хорошее распределение — то есть сохраняем работоспособность хэш-таблицы. Да и взятие хэша действительно дешёвая операция, что до перегрузки, что после.
А насчёт смены алгоритмов высчитывания хэшей — тут я согласен, никак нельзя опираться на какие-то знания, о том как устроен неперегруженный хэш внутри фреймворка не стоит.
А насчёт смены алгоритмов высчитывания хэшей — тут я согласен, никак нельзя опираться на какие-то знания, о том как устроен неперегруженный хэш внутри фреймворка не стоит.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сравнение объектов в C#.NET