В .NET GetHashCode метод используется во многих местах в библиотеках базовых классов .NET. Его правильная реализация особенно важна для быстрого поиска элементов в коллекции или при определении равенства.
Есть ли стандартный алгоритм или передовой опыт реализации GetHashCode для моих пользовательских классов, чтобы я не снижал производительность?
«или определить равенство»: нет! Два объекта с одинаковым хэш-кодом не обязательно равны.
@ThomasLevesque Вы правы, два объекта с одинаковым хеш-кодом не обязательно равны. Но все же GetHashCode() используется во многих реализациях Equals(). Вот что я имел в виду в этом заявлении. GetHashCode() внутри Equals() часто используется как ярлык для определения неравенство, потому что, если два объекта имеют хэш-код разные, они должны быть объектами, которые не равны, и остальная часть проверки равенства не должна выполняться.
@bitbonk Обычно и GetHashCode(), и Equals() должны просматривать все поля обоих объектов (Equals должен это сделать, если хэш-коды совпадают или не проверены). Из-за этого вызов GetHashCode() внутри Equals() часто является избыточным и может снизить производительность. Equals() также может иметь возможность короткого замыкания, что делает его намного быстрее - однако в некоторых случаях хэш-коды могут быть кэшированы, что делает проверку GetHashCode() более быстрой и полезной. Подробнее см. этот вопрос.
ОБНОВЛЕНИЕ ЯНВАРЯ 2020: Блог Эрика Липперта, расположенный по адресу: docs.microsoft.com/en-us/archive/blogs/ericlippert/…
ОБНОВЛЕНИЕ МАРТ 2020 ГОДА: ссылка с @RickDavin верна, но статья на docs.microsoft.com имеет плохой формат. Вот такая же статья в блоге Эрика. ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashc ode
Теперь вы можете просто использовать HashCode.Combine (field1, field2, ...)





Я обычно использую что-то вроде реализации, данной в книге Джоша Блоха поразительнйЭффективная Java. Это быстро и создает довольно хороший хеш, который вряд ли вызовет коллизии. Выберите два разных простых числа, например 17 и 23, и сделайте:
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = 17;
// Suitable nullity checks etc, of course :)
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
hash = hash * 23 + field3.GetHashCode();
return hash;
}
}
Как отмечалось в комментариях, вы можете обнаружить, что для умножения лучше выбрать большое простое число. По-видимому, 486187739 - это хорошо ... и хотя в большинстве примеров, которые я видел с небольшими числами, как правило, используются простые числа, есть, по крайней мере, похожие алгоритмы, в которых часто используются непростые числа. В приведенном ниже примере не совсем FNV, например, я использовал числа, которые, по-видимому, работают хорошо, но начальное значение не является простым. (Хотя константа умножения является простая. Я не знаю, насколько это важно.)
Это лучше, чем обычная практика хэш-кодов XOR по двум основным причинам. Предположим, у нас есть тип с двумя полями int:
XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y
Кстати, более ранний алгоритм - это тот, который в настоящее время используется компилятором C# для анонимных типов.
Эта страница дает довольно много вариантов. Я думаю, что для большинства случаев вышеизложенное «достаточно хорошо», и его невероятно легко запомнить и исправить. Альтернатива FNV также проста, но использует другие константы и XOR вместо ADD в качестве операции объединения. Он выглядит как что-нибудь, как приведенный ниже код, но обычный алгоритм FNV работает с отдельными байтами, поэтому для этого потребуется изменение для выполнения одной итерации для каждого байта, а не для 32-битного значения хеш-функции. FNV также разработан для данных переменной длины, тогда как мы используем его здесь всегда для одного и того же количества значений поля. Комментарии к этому ответу предполагают, что приведенный здесь код на самом деле не работает (в протестированном примере), как описанный выше подход добавления.
// Note: Not quite FNV!
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = (int) 2166136261;
// Suitable nullity checks etc, of course :)
hash = (hash * 16777619) ^ field1.GetHashCode();
hash = (hash * 16777619) ^ field2.GetHashCode();
hash = (hash * 16777619) ^ field3.GetHashCode();
return hash;
}
}
Обратите внимание, что нужно знать одну вещь: в идеале вы должны предотвратить изменение состояния, чувствительного к равенству (и, следовательно, чувствительного к хэш-коду), после добавления его в коллекцию, которая зависит от хэш-кода.
Согласно документация:
You can override GetHashCode for immutable reference types. In general, for mutable reference types, you should override GetHashCode only if:
- You can compute the hash code from fields that are not mutable; or
- You can ensure that the hash code of a mutable object does not change while the object is contained in a collection that relies on its hash code.
Ссылка на статью FNV не работает, но вот копия в Интернет-архиве: Вечно запутанный - Искусство хеширования
Алгоритм, описанный в упомянутой вами книге, на самом деле немного более подробен, он, в частности, описывает, что делать с различными типами данных в полях. Например: для полей типа long используйте (int) (field ^ f >>> 32) вместо простого вызова GetHashcode. Реализован ли таким образом long.GetHashCodes?
Ага, Int64.GetHashCode делает именно это. В Java, конечно, потребуется бокс. Это напоминает мне - пора добавить ссылку на книгу ...
23 - не лучший выбор, поскольку (начиная с .net 3.5 SP1) Dictionary<TKey,TValue> предполагает хорошее распределение по модулю определенных простых чисел. И 23 - один из них. Итак, если у вас есть словарь с емкостью 23, только последний вклад в GetHashCode влияет на составной хэш-код. Так что я бы предпочел использовать 29 вместо 23.
@Ani: ваша реализация разместила в куче несколько новых объектов, поэтому производительность может быть ниже, чем при ручной реализации. Приемлемо ли это, зависит от вашего типа и использования. Проверьте некоторые другие ответы для помощников, использующих универсальные шаблоны, которые позволяют избежать этой проблемы.
@CodeInChaos: только последний вклад влияет на ведро, поэтому в худшем случае ему придется просматривать записи все 23 в словаре. Он по-прежнему будет проверять фактический хэш-код каждой записи, что будет дешево. Если у вас есть такой маленький словарь, вряд ли это будет иметь большое значение.
@Jon: Я должен спросить, несмотря на то, что уже открыл мой собственный вопрос по этой теме, но какая хорошая версия для VB, поскольку в VB отсутствуют ключевые слова checked и unchecked? Я попытался сделать tmpHash Int64 и выполнить операцию AND с младшими 8 битами (в соответствии с принятый ответ на мой вопрос), но на достаточно большом наборе полей это каким-то образом привело к тому, что вычисление обернулось до 0 для оставшейся части цикла.
@Kumba: Боюсь, я не знаю, как бы это сделать в VB. Проверяется ли арифметика всегда в VB? Могли бы вы иметь отдельную библиотеку классов, которой вы могли бы делегировать арифметику, написанную на C# или с отключенной проверенной арифметикой для всего проекта?
@Jon: VB явно проверяет много вещей. У него есть фетиш требовать, чтобы числа без знака преобразовывались в числа со знаком, прежде чем вы сможете их сдвинуть влево или вправо. Что заставляет меня взбираться по стене и по потолку. Я пытаюсь реализовать хеш Jenkins, чтобы обойти отсутствие отмеченных / непроверенных (вращающийся хеш также помогает, но меня беспокоят конфликты хешей с вводом). Я бы хотел избежать использования отдельной библиотеки C#, потому что она, по сути, допускает поражение. Если я дойду до этого, мне нужно будет просто переписать весь проект на C#.
Разве «непроверенный» ненужный b / c CLR по умолчанию будет счастливо переполняться?
@pomeroy: Это зависит от настроек проекта. По сути, вы даете сборке контекст по умолчанию, отмеченный или не отмеченный.
@pomeroy: VB не такой детализированный, как C#. Поскольку в нем отсутствуют два вышеупомянутых ключевых слова, ваш единственный вариант - удалить целое число переполнений для всего проекта или нет. Я предполагаю, что если ваш проект завершен и в целом хорошо протестирован, удаление проверок переполнения является безопасным делом. Однако при его создании и отладке эти проверки хороши, потому что они выделяют ошибки, которые нужно исправить. Я открыл Connect Ticket # 636564 с Microsoft, чтобы порекомендовать включить поддержку ключевых слов checked / unchecked в следующий выпуск .NET. Однако не уверен, что они сделают это.
Я добавлю, что мне придется использовать алгоритм ротации хешей, связанный с ответом Джона выше. Он не переполняется, даже в Int32, не (пока) не переносится в 0 на большом количестве полей в вычислении, и выполняется просто и довольно быстро. Хеш Jenkins не сработал ... Даже это переполняется случайным образом, в зависимости от ввода. Кроме того, принудительный сдвиг битов в знаковой математике мешает многим вещам. Я мог бы открыть еще одну ошибку, если это не предполагалось каким-то образом.
Разве вам не нужен override в объявлении вашего метода? Также было бы хорошо поставить нулевые проверки, поскольку это такой хорошо используемый пример.
@Rory: Я добавил переопределение, спасибо - я не собираюсь вводить нулевые проверки, так как я чувствую, что это заслонит важные моменты. ИМО комментария хватает.
Зачем начинать с простого, а не с нуля? есть ли у int hash = 17; какие-либо теоретически поддерживаемые преимущества?
@FredOverflow: я не знаю точных деталей всех причин, стоящих за этим, но начало с 0 означало бы, что хеш останется равным нулю, если отдельные хэши полей будут равны нулю ... и это, вероятно, не редкость (например, целое число нулевого значения, вероятно, будет хеширован до нуля). Просто предположение, но я подозреваю, что наличие константы, которая распространяется с каждым полем, полезно. На самом деле это просто скопировано из Effective Java :)
@JonSkeet Насколько безопасным будет этот алгоритм для сложного графа объектов, состоящего, скажем, из 500 объектов, каждый из которых имеет 10 свойств. Связанный вопрос: stackoverflow.com/questions/5308057/…
@bitbonk: Вероятность столкновения при любом отдельном изменении будет довольно низкой ... но в вопросе, о котором вы говорите, я бы, вероятно, использовал вместо этого криптографический хеш.
Тогда возникает вопрос: как мне создать криптографический хеш для объектной модели?
@bitbonk: Я бы настоятельно рекомендовал использовать «нормальный» криптографический хеш для результата двоичной сериализации формы.
Этот алгоритм в основном представляет собой алгоритм хеширования строк DJB2, для которого рекомендуются константы 5381 и 33 (cse.yorku.ca/~oz/hash.html). Честно говоря, я не уверен, что константа имеет большое значение, но множитель важен.
@JonSkeet Я понимаю, что воскрешаю здесь мертвых, но реализация хэшей для меня в новинку. Какие поля я включаю в хеш в вашей реализации? Только неизменяемые, или какие-то поля хороши?
@KChaloux: Это полностью зависит от того, что вы хотите, чтобы равенство значило. Однако обычно включать изменяемые данные - плохая идея.
Как бы вы справились с недействительностью? Если просто игнорировать это поле, то для A = null, B = "ss" и для A = "ss", B = null у нас будут коллизии. Не лучше ли умножать каждое поле на разные простые числа?
@Vajda: я обычно использую 0 в качестве эффективного хеш-кода для null - это не то же самое, что игнорирование поля.
@ jnm2: Честно говоря, я не понимаю твоих аргументов. В частности, я только что попробовал это эффективное хеширование 10 полей - и, изменив значение только, первое поле все равно изменило хеш, что противоречит вашему утверждению о том, что «каждый бит первых хеш-кодов будет потерян».
Вы можете довольно просто продемонстрировать, что это дает плохое распределение. Возьмите этот вариант FNV и примените его к строкам (используйте небезопасные манипуляции с указателями, чтобы получать целые числа за раз, чтобы дать ему шанс). Используйте его для добавления строк в хеш-таблицу, основанную на степени двойки. С тем, над которым я сейчас работаю, если я сгенерирую «1», «2», ... «999999» и добавлю их, это займет около 34 секунд. Теперь возьмем тот же метод хеширования и повторно хешируем результат с хорошо распределенным хешем. С хорошим хешем это может только усугубить ситуацию (тратится больше времени, и мы можем вводить новые коллизии, но никогда их не удалять). С ...
... та же хеш-таблица, над которой я работаю, тот же код для генерации "1" ... "999999" и их добавление занимает 1 секунду. Эффект менее выражен с хешами на основе простых чисел, поэтому в этом случае дополнительное время, потраченное на повторное хеширование (и, возможно, сокращение возможных результатов, хотя это маловероятно), ничего не дает, но низкая производительность при мощности -два таблицы демонстрируют плохое распределение в целом.
@JonHanna: Спасибо за это. Не уверен, что вы имеете в виду, говоря «получать целые числа за раз», но я постараюсь взглянуть повнимательнее. Мне все еще нравится это в первом приближении для хеша, но если у вас есть другой хеш, который так же просто запомнить и исправить, но с лучшим распределением, я был бы очень рад изменить свою практику :)
Я имел в виду, что использовал fixed(char* ptr = str){int* iPtr = (int*)ptr;..., но я также пытался просто сделать foreach(char c in str) и преобразовать каждый char в int, и то же самое применимо. Относительная слабость стала очевидной для меня, когда у меня была причина использовать таблицы степени двух и я получал плохие результаты (я сам использовал почти то же, что и выше). Решение, к которому я наконец пришел, - это забыть о том, что его легко запомнить, и один раз создать трудно запоминающийся метод, а затем упростить его использование и поместить его код в nuget.org/packages/SpookilySharp Я добавлю полный ответ здесь на обеденный перерыв.
@JonSkeet и теперь ответил.
@JonHanna: Спасибо за это. Придется посмотреть поподробнее, когда будет куча времени :)
Я думаю, важно отметить, что мы должны быть осторожны с изменением хеш-кода во время выполнения. У нас была ошибка в моем проекте, потому что предыдущий разработчик реализовал алгоритм GetHashCode, основанный на этом ответе. Но в его реализации у него был список объектов, он использовал хэш каждого элемента в коллекции для генерации хеш-кода объекта. Поэтому при изменении коллекции изменился и хэш-код. Это вызывало проблемы с привязкой в WPF. И если бы у вас был объект, например, в словаре, вы бы тоже получили ошибки.
@Dzyann: Да, изменять ключ таким образом, чтобы это влияло на равенство - и, следовательно, на хэш-код - это всегда плохая идея. Добавлю примечание.
@JonSkeet, вы правы, и это может привести к очень сложному отслеживанию ошибок. Как в этом случае с привязками WPF. Потребовались годы, прежде чем один из моих коллег нашел причину и решил ее. Поскольку это был не наш код, это было очень сложно.
Я бы посоветовал вам заменить 17 и 23 константами здесь. (Спасибо за ссылку.) Благодаря этому простой поиск по словарю стал намного эффективнее, в моем случае на ~ 60% лучше.
@ jnm2: Это не тот алгоритм для начала - он использует XOR, а не ADD. Я буду придерживаться этих констант для этого ответа, но, может быть, вам стоит добавить свой собственный ответ?
Фактически, я собирался предположить, что xoring вместо добавления не уменьшит простоту хеш-алгоритма перехода. Что вы думаете?
В моем случае XOR ускоряет GetHashCode () на 12%.
@ jnm2: Ну, это не уменьшило бы эту простоту - но это не то, чем я занимался последние несколько лет. Я добавлю FNV в качестве альтернативы.
int hash = 2166136261; Не хватает ли гипса? Компилятор говорит, что 2166136261 - это uint ... Я поменял его на int hash = (int)2166136261;Я попытался реализовать этот подход для ValueUtils, но в моем тестировании этот вариант FNV вызвал значительные коллизии (24%) в некоторых симметричных наборах данных. И, возможно, это потому, что это НЕ хеш FNV? Традиционные хэши FNV на октет (байт), а не на 32-битное слово. Это дает этому варианту меньше возможностей смешивать эти биты ...
@EamonNerbonne: Что вы имеете в виду под «этим подходом»? Теперь ответ содержит две разные версии ...
Я имею в виду этот вариант FNV - это не совсем FNV, и я почти уверен, что это только усугубляет ситуацию. Я, кстати, тоже пробовал рецепт h=prime; repeat h=h*prime + ?; это, кажется, меняется; он вполне подходит для больших простых чисел, особенно если ваш промежуточный разряд имеет ширину 64 бита.
@Eamon: Боюсь, я недостаточно знаю теорию, чтобы комментировать дальше :(
Да, теория, лежащая в основе этого, для меня совсем не очевидна. Однако этот ответ предполагает, что эта реализация является FNV, хорошо известным хорошим хешем. Но это не совсем так, поскольку это нет FNV. Кроме того, FNV - это алгоритм хеширования строк, который должен удовлетворять гораздо более сложным требованиям, поскольку он должен работать с потенциально длинными строками переменной длины. Но опять же, алгоритм, представленный в настоящее время в ответе, не является FNV - он гораздо хуже смешивает биты.
@EamonNerbonne: Хорошо. Я отредактирую, чтобы указать, что это модификация, и что она не работает, по крайней мере, в некоторых случаях.
@EamonNerbonne: Какие лучшие коэффициенты вам известны?
@ jnm2 В моих экспериментах смещение мало что значит, и тенденция такова, что большие простые числа работают лучше, с оговоркой, что все это сложно проверить, потому что это медленно (очень медленно), чтобы быть тщательным, и это зависит от способа, которым ваш набор данных "испорчен". Если ваши поля имеют совершенно случайно распределенные хэш-коды - все это не имеет значения, но, конечно, в реальном мире эти хэш-коды не случайны, и поля коррелированы. Есть довольно веская причина, по которой большие простые числа тоже будут лучше - они лучше смешивают биты, особенно если ваши данные в основном состоят из небольших чисел.
@ jnm2, поэтому я бы выбрал большое число (скажем, порядка 2 ^ 16) и настроился на реализацию словаря .NET, который НЕ используется Dictionary <,>: linksource.microsoft.com/#mscorlib/system/collections/…
@ jnm2 Я столкнулся с этими двумя вопросами, продолжая изучать эту проблему: stackoverflow.com/questions/1835976/… и stackoverflow.com/questions/1145217/…, и оба пришли к выводу: используйте любое старое большое простое число. В принятом ответе на первый вопрос упоминаются два, выбранных принципиальным образом, но вряд ли этот принцип действительно относится к реальному миру, поэтому он все же рекомендует основную идею: выберите большое простое число, а НЕ 23 или 31.
Кстати: обратите внимание, что смещение (насколько я могу судить) совершенно бессмысленно. Распределительные законы также действуют по модулю, а это означает, что это просто идентичное смещение, которое будут разделять все объекты, - это, безусловно, не влияет на какую-либо хеш-таблицу, которую я знаю.
@EamonNerbonne: Думаю, это правда, если все объекты одного типа. Если у вас есть словарь, в котором некоторые ключи являются подклассами других ключей, это может иметь значение ... хотя в любом случае только тогда, когда значения дополнительных полей равны 0. Опять же, для меня это в основном привычка :(
@JonSkeet Да, если у вас есть объекты разного типа и вы используете разные смещения, у вас будет некоторое преимущество. Хотя, думаю, нет причин быть первоклассным ... В любом случае, дополнение настолько дешево, что нет особых причин избегать его.
Я использовал этот алгоритм для псевдослучайного генератора, и он ведет себя немного странно: stackoverflow.com/questions/26847262/…
Если вы получили номер 486187739 от stackoverflow.com/a/2816747/21499 - я действительно намеревался рекомендовать 92821.
Поскольку каждый экземпляр класса «объект» имеет уникальный хэш-код, мне пришла в голову идея, что было бы хорошо, если бы мы использовали base.GetHashCode () в качестве начального числа или чего-то еще для создания нашего хэш-кода для объекта.
@AhmadSiavosh: Нет, это идея плохой, потому что вы хотите, чтобы разные, но равные объекты имели один и тот же хэш-код. (Я не думаю, что object.GetHashCode также гарантированно уникален. Вполне возможно, что "очень маловероятно столкновение", но это не одно и то же.)
Если fieldL - это List<obj>, он будет работать, просто выполнив hash = ... ^ fieldL.GetHashCode(), или я должен пройти через такие пункты, как foreach(){hash = ... ^ item.GetHashCode()} ???
@Jaider: Это тоже не годится. List<T> не отменяет Equals или GetHashCode. #
Я пробовал этот код для 3 дублей и получил огромное количество коллизий. Мне нужно получить хэш-коды для 4194304 кортежей. Есть ли способ лучше? Использование некоторых более крупных простых чисел немного помогло, но я все еще получаю коллизии.
@ user984444: Что ж, вы должны ожидать довольно много столкновений с таким количеством записей. Сколько вы получаете?
@JonSkeet Трудно сказать. Я использую это для кэширования вывода некоторого шума Перлина, а индикатором столкновения является некоторый "интересный" вывод в моем изображении; Он выглядит как ... когда вы выигрываете пасьянс. Это смягчается (и шаблон меняется) с большими простыми числами. Я знаю, это бесполезно. Я изменил свою структуру (кортеж двойников в качестве ключа) на класс, чтобы сеть заботилась о хэш-коде за меня и больше не имела коллизий.
@ user984444: Гм, в этом случае одинаковые ключи не будут равными, если только вы не переопределите GetHashCode в своем классе, и в этом случае у вас такая же проблема. Может, стоит задать новый вопрос со всеми подробностями ...
@JonSkeet: Неправда; реализация GetHashCode по умолчанию работает отлично (в противном случае это было бы невероятно очевидно в моем конечном результате). Он также работает для структуры, но работает НАЧАЛО МЕДЛЕННО. Я хотел использовать структуры, но использование класса, похоже, отлично подходит для моего варианта использования.
@ user984444: Если вы не переопределите GetHashCode и Equals самостоятельно или не унаследуете от другого класса, который это делает, вы получите ссылочное равенство. Это нет, что даст вам структура. Похоже, нам нужен новый пост с подробностями.
@JonSkeet: Я считаю, что моя конкретная проблема решена, потому что я получаю желаемый результат, но если у меня будет возможность, я опубликую вопрос с подробностями, чтобы вы могли видеть, что происходит.
будучи очень разборчивым, настройки StyleCop по умолчанию генерируют предупреждение для этого кода (SA1407), поскольку вы не использовали круглые скобки для определения приоритета арифметических операторов, даже если он понятен любому разработчику, читающему код, и компилятору, как мы все знаем правило БОДМЫ.
@MikeW: Я не думаю, что BODMAS включает XOR :) Я думаю, что заключительный фрагмент кода будет более понятным с круглыми скобками - добавлю их сейчас. Я согласен, что для версии с умножением и сложением они не нужны.
@JonSkeet есть идеи, как это сделать в t-sql? Мне нужен хеш C# серии guid для соответствия хешу t-sql серии uniqueidentifier. но afaik в t-sql невозможно обернуть результаты целочисленной арифметики.
@BaltoStar: я ничего не знаю о хешировании в T-SQL. Если он уже обеспечивает четко определенное хеширование для значений GUID, я бы, вероятно, попытался имитировать это на C#, а не наоборот.
@JonSkeet в C#, почему бы просто не хешировать MD5 для упорядоченной конкатенации идентификаторов GUID?
@JamesKo: Я добавлю ссылку на HashCode.Combine, когда .NET Core 2.1 действительно будет выпущен, и я могу ссылаться на документы. Не думаю, что до того времени многим он будет полезен.
@JonSkeet Конечно.
Я не уверен, как здесь обрабатывать нули. Кажется, что ни один из ответов не затрагивает эту тему, если предположить, что все мы эксперты в этой теме. @JonSkeet В этих комментариях упоминается: «Я обычно использую 0 в качестве эффективного хэш-кода для null - это не то же самое, что игнорировать поле». Однако как это на самом деле реализовано, у меня есть вопросы. Похоже, вы говорите, что свойство null должно обнулить текущее значение хеш-функции, но это кажется странным поведением. Некоторым может быть очевидно, что делать, но я был бы признателен за пример, показывающий, как обрабатывать нули, или лучшее объяснение.
Прочитав несколько других вопросов и ответов по этой теме, я понял, что не очень хорошо понимаю, о чем говорит @JonSkeet. Я неправильно понял, что он говорит, что я должен заменить 0 как константу хеширования, когда свойство имеет значение null. Увидев пример здесь, я понимаю, что он просто заявлял, что я должен заменить 0 в качестве хэш-кода свойства, что сейчас кажется таким очевидным ... учитывая, что это именно то, что он сказал.
Действительно ли нужно использовать простые числа вроде 17 или 23, если хэш моего объекта зависит только от одного свойства int32? Могу я просто вернуть MyProperty.GetHashCode()?
@ stt106: Для одного свойства я бы просто вернул хэш-код этого свойства, да.
К вашему сведению, Visual Studio 2017 может генерировать GetHashCode() без ReSharper. docs.microsoft.com/en-us/visualstudio/ide/reference/…
Зачем умножать хеш на каждой строке? Почему: int hash = 17; hash = hash * 23 + ...? Почему бы просто не использовать продукт явно, как, например, hash = 391 + field1.GetHashCode();? Поскольку порядок операций в любом случае будет сначала выполнять умножение?
@ emery.noel: Это не будет иметь никакого значения после первой строки (вам все равно нужно умножить, чтобы включить предыдущий хеш), и IMO имеет большое преимущество в том, чтобы сделать каждую строку согласованной.
Важному моменту уделялось не так много внимания. Важно, чтобы возвращаемый хэш-код НЕ МЕНЯЛСЯ, если объект является изменяемым и объект изменяется. Это связано с тем, что хэш-код используется (например) для размещения объектов в словарях. Если изменяемый объект изменяется после вставки в словарь, то объект не найден, когда вы идете искать его. Приведенное выше должно кэшировать хэш при первом вычислении и всегда возвращать исходное значение. Иначе будут странные баги.
@Tb .: Или вы документируете это в соответствии с документами: «Если вы решите переопределить GetHashCode () для изменяемого ссылочного типа, в вашей документации должно быть четко указано, что пользователи вашего типа не должны изменять значения объекта, пока объект хранится в хеш-таблице ". Часто это бывает полезно, поскольку вы можете создать объект, но не изменять его впоследствии. Это не «до блеска», но может быть совершенно практичным.
Ссылка на статью FNV битая, но я нашел ее в архиве: archive.vn/KJeJy
Большая часть моей работы выполняется с подключением к базе данных, что означает, что все мои классы имеют уникальный идентификатор из базы данных. Я всегда использую идентификатор из базы данных для генерации хэш-кода.
// Unique ID from database
private int _id;
...
{
return _id.GetHashCode();
}
Это означает, что если у вас есть объекты Person и Account, и у них обоих есть ID = 1, они будут иметь одинаковый хэш-код. А это не нормально.
На самом деле комментарий выше неверен. Всегда будет возможность коллизии хэш-кода (хеш-код определяет местонахождение только корзины, а не отдельного объекта). Таким образом, такая реализация - для хэш-кода, содержащего смешанные объекты - привела бы к множеству коллизий, что нежелательно, но было бы абсолютно нормально, если бы у вас когда-либо были объекты только одного типа в ваших хэш-таблицах. Кроме того, он не распределяется равномерно, однако базовая реализация на system.object тоже не работает, поэтому я бы не стал слишком беспокоиться об этом ...
Хэш-код может быть просто идентификатором, поскольку идентификатор является целым числом. Нет необходимости вызывать GetHashCode для целого числа (это функция идентификации)
@DarrelLee, но его _id может быть гидом. _id.GetHashCode - хорошая практика кодирования, поскольку цель ясна.
@DarrelLee, это не лучший вариант, потому что последовательные идентификаторы из базы данных не обеспечивают хорошего распределения
@ 1224, в зависимости от шаблонов использования, это может быть ужасно по той причине, которую вы указываете, но также может быть и великолепно; если у вас есть последовательность таких чисел без дырок, то у вас идеальный хеш, лучший, чем может произвести любой алгоритм. Если вы знаете, что это так, вы даже можете рассчитывать на это и пропустить проверку на равенство.
У меня есть класс хеширования в библиотеке Helper, который я использую для этой цели.
/// <summary>
/// This is a simple hashing function from Robert Sedgwicks Hashing in C book.
/// Also, some simple optimizations to the algorithm in order to speed up
/// its hashing process have been added. from: www.partow.net
/// </summary>
/// <param name = "input">array of objects, parameters combination that you need
/// to get a unique hash code for them</param>
/// <returns>Hash code</returns>
public static int RSHash(params object[] input)
{
const int b = 378551;
int a = 63689;
int hash = 0;
// If it overflows then just wrap around
unchecked
{
for (int i = 0; i < input.Length; i++)
{
if (input[i] != null)
{
hash = hash * a + input[i].GetHashCode();
a = a * b;
}
}
}
return hash;
}
Затем вы можете просто использовать его как:
public override int GetHashCode()
{
return Hashing.RSHash(_field1, _field2, _field3);
}
Я не оценивал его производительность, поэтому любые отзывы приветствуются.
Что ж, это вызовет бокс, если поля являются типами значений.
«может быть улучшено позже путем перехвата OverflowException». Вся суть unchecked состоит в том, чтобы избежать исключений при переполнении, которое желательно для GetHashCode. Так что это не неправильно, если значение выходит за пределы int, и это совсем не повредит.
Одна из проблем этого алгоритма заключается в том, что любой массив, заполненный нулями, всегда будет возвращать 0, независимо от его длины.
Этот вспомогательный метод также выделяет новый объект []
Как упоминает @NathanAdams, тот факт, что null полностью пропускается, может дать вам неожиданные результаты. Вместо того, чтобы пропускать их, вы должны просто использовать какое-то постоянное значение вместо input[i].GetHashCode(), когда input[i] равен нулю.
В большинстве случаев, когда Equals () сравнивает несколько полей, на самом деле не имеет значения, хеширует ваш GetHash () в одном поле или во многих. Вам просто нужно убедиться, что вычисление хэша действительно дешево (Нет распределения, пожалуйста) и быстро (Никаких тяжелых вычислений и, конечно, без подключений к базе данных) и обеспечивает хорошее распределение.
Подъем тяжестей должен быть частью метода Equals (); хэш должен быть очень дешевой операцией, чтобы можно было вызывать Equals () для как можно меньшего числа элементов.
И последний совет: Не полагайтесь на стабильность GetHashCode () при выполнении нескольких приложений.. Многие типы .Net не гарантируют, что их хэш-коды останутся неизменными после перезапуска, поэтому вам следует использовать значение GetHashCode () только для структур данных в памяти.
«В большинстве случаев, когда Equals () сравнивает несколько полей, на самом деле не имеет значения, хеширует ваш GetHash () в одном поле или во многих». Это опасный совет, потому что для объектов, которые отличаются только нехешированными полями, вы получите коллизии хешей. Если это происходит часто, производительность коллекций на основе хешей (HashMap, HashSet и т. д.) Будет снижаться (до O (n) в худшем случае).
На самом деле это произошло в Java: в ранних версиях JDK String.hashCode () рассматривал только начало строки; это привело к проблемам с производительностью, если вы использовали строки в качестве ключей в HashMaps, которые различались только в конце (что является обычным, например, для URL-адресов). Поэтому алгоритм был изменен (я полагаю, в JDK 1.2 или 1.3).
Если это одно поле «обеспечивает хорошее распределение» (последняя часть моего ответа), тогда одного поля достаточно .. Если это не обеспечивает хорошее распространение, тогда (и только тогда) вам понадобится другое вычисление. (Например, просто используйте другое поле, которое делает обеспечивает хорошее распределение, или используйте несколько полей)
Я не думаю, что есть проблема с тем, что GetHashCode выполняет выделение памяти, при условии, что это происходит только при первом использовании (с последующими вызовами, просто возвращающими кешированный результат). Важно не то, что нужно делать все возможное, чтобы избежать столкновений, а то, что нужно избегать «системных» столкновений. Если у типа есть два поля intoldX и newX, которые часто отличаются на единицу, хеш-значение oldX^newX будет назначать 90% таких записей хеш-значений 1, 2, 4 или 8. Использование oldX+newX [непроверенная арифметика] может привести к большему количеству коллизий. ...
... чем более сложная функция, но набор из 1 000 000 вещей, которые имеют 500 000 различных значений хеш-функции, будет очень хорошо, если каждое значение хеш-функции имеет две связанные вещи, и очень плохо, если одно значение хеш-функции имеет 500 001 вещь, а другие - по одной.
Вот мой помощник по хэш-коду. Преимущество заключается в том, что он использует аргументы универсального типа и поэтому не вызывает бокса:
public static class HashHelper
{
public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
{
unchecked
{
return 31 * arg1.GetHashCode() + arg2.GetHashCode();
}
}
public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
{
unchecked
{
int hash = arg1.GetHashCode();
hash = 31 * hash + arg2.GetHashCode();
return 31 * hash + arg3.GetHashCode();
}
}
public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3,
T4 arg4)
{
unchecked
{
int hash = arg1.GetHashCode();
hash = 31 * hash + arg2.GetHashCode();
hash = 31 * hash + arg3.GetHashCode();
return 31 * hash + arg4.GetHashCode();
}
}
public static int GetHashCode<T>(T[] list)
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
public static int GetHashCode<T>(IEnumerable<T> list)
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
/// <summary>
/// Gets a hashcode for a collection for that the order of items
/// does not matter.
/// So {1, 2, 3} and {3, 2, 1} will get same hash code.
/// </summary>
public static int GetHashCodeForOrderNoMatterCollection<T>(
IEnumerable<T> list)
{
unchecked
{
int hash = 0;
int count = 0;
foreach (var item in list)
{
hash += item.GetHashCode();
count++;
}
return 31 * hash + count.GetHashCode();
}
}
/// <summary>
/// Alternative way to get a hashcode is to use a fluent
/// interface like this:<br />
/// return 0.CombineHashCode(field1).CombineHashCode(field2).
/// CombineHashCode(field3);
/// </summary>
public static int CombineHashCode<T>(this int hashCode, T arg)
{
unchecked
{
return 31 * hashCode + arg.GetHashCode();
}
}
Также у него есть метод расширения для обеспечения плавного интерфейса, поэтому вы можете использовать его следующим образом:
public override int GetHashCode()
{
return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}
или вот так:
public override int GetHashCode()
{
return 0.CombineHashCode(Manufacturer)
.CombineHashCode(PartN)
.CombineHashCode(Quantity);
}
Отдельно T[] не нужен, так как это уже IEnumerable<T>
Вы можете провести рефакторинг этих методов и ограничить основную логику одной функцией.
Между прочим, 31 - это сдвиг и вычитание на ЦП, что очень быстро.
Метод расширения в int - это неприятное загрязнение пространства имен - ответ ниже @ safak-gur прекрасно помогает решить эту проблему.
@nightcoder, вы можете использовать параметры.
@ChuiTey Это то, что есть у всех Простые числа Мерсенна.
не должна ли переменная hash начинаться с нуля? stackoverflow.com/a/113600/9638388
Просто потому, что это круто, вы также можете сделать это с помощью однострочника: source?.Aggregate(0, (current, item) => unchecked(current * 31 + (item?.GetHashCode() ?? 0))) ?? 0;
@ANeves Я предлагаю вам не использовать params, если он предназначен для более широкого использования (например, публичная библиотека). params включает распределение массива (плюс затраты O (n) на заполнение массива), что плохо для ситуаций, чувствительных к производительности. params object[] вдвойне плох теперь, когда вы вводите стоимость упаковки также для типов значений.
Это хороший:
/// <summary>
/// Helper class for generating hash codes suitable
/// for use in hashing algorithms and data structures like a hash table.
/// </summary>
public static class HashCodeHelper
{
private static int GetHashCodeInternal(int key1, int key2)
{
unchecked
{
var num = 0x7e53a269;
num = (-1521134295 * num) + key1;
num += (num << 10);
num ^= (num >> 6);
num = ((-1521134295 * num) + key2);
num += (num << 10);
num ^= (num >> 6);
return num;
}
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name = "arr">An array of objects used for generating the
/// hash code.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and data
/// structures like a hash table.
/// </returns>
public static int GetHashCode(params object[] arr)
{
int hash = 0;
foreach (var item in arr)
hash = GetHashCodeInternal(hash, item.GetHashCode());
return hash;
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name = "obj1">The first object.</param>
/// <param name = "obj2">The second object.</param>
/// <param name = "obj3">The third object.</param>
/// <param name = "obj4">The fourth object.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and
/// data structures like a hash table.
/// </returns>
public static int GetHashCode<T1, T2, T3, T4>(T1 obj1, T2 obj2, T3 obj3,
T4 obj4)
{
return GetHashCode(obj1, GetHashCode(obj2, obj3, obj4));
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name = "obj1">The first object.</param>
/// <param name = "obj2">The second object.</param>
/// <param name = "obj3">The third object.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and data
/// structures like a hash table.
/// </returns>
public static int GetHashCode<T1, T2, T3>(T1 obj1, T2 obj2, T3 obj3)
{
return GetHashCode(obj1, GetHashCode(obj2, obj3));
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name = "obj1">The first object.</param>
/// <param name = "obj2">The second object.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and data
/// structures like a hash table.
/// </returns>
public static int GetHashCode<T1, T2>(T1 obj1, T2 obj2)
{
return GetHashCodeInternal(obj1.GetHashCode(), obj2.GetHashCode());
}
}
А вот как им пользоваться:
private struct Key
{
private Type _type;
private string _field;
public Type Type { get { return _type; } }
public string Field { get { return _field; } }
public Key(Type type, string field)
{
_type = type;
_field = field;
}
public override int GetHashCode()
{
return HashCodeHelper.GetHashCode(_field, _type);
}
public override bool Equals(object obj)
{
if (!(obj is Key))
return false;
var tf = (Key)obj;
return tf._field.Equals(_field) && tf._type.Equals(_type);
}
}
Как определяются ключи? GetHashCode () не принимает никаких параметров, поэтому ему необходимо вызвать его с двумя ключами, которые нужно как-то определить. Извините, без дополнительных объяснений это только выглядит умно, но не так хорошо.
А зачем вам общие перегрузки? Тип не важен (и не используется в вашем коде), поскольку объекты все имеют метод GetHashCode(), поэтому вы всегда можете использовать метод с параметром массива params. Или мне что-то здесь не хватает?
Речь идет о производительности, избегайте цикла для меньших <= 4 полей. Но я думаю, что дженерики можно пропустить и вместо этого просто использовать объект.
Когда вы используете объект вместо дженериков, вы получаете боксы и выделения памяти, которые вам не нужны в GetHashCode. Так что дженерики - это то, что нужно.
Завершающие шаги shift / xor (h += (h << 10); h ^= (h >> 6); h += (h << 3); h ^= (h >> 11); h += (h << 15); имеют кодовый запах: они не зависят от какого-либо ввода и кажутся мне ужасно избыточными.
@nawfal какие у вас соображения по скорости?
@Magnus ничего особенного, кроме общего правила, что хеширование должно быть быстрым. Это не может быть так быстро, как мне бы хотелось. Но, как я уже сказал, это дает лучшее распределение значений, которое может быть подходящим для некоторых случаев.
@nawfal Выполнение этого 100 миллионов раз занимает около 390 мс. Выполнение решения, предложенного Джоном Скитом, 100 миллионов раз занимает около 320 мс, так что это не большая разница.
@Magnus да ладно, я удалю свой исходный комментарий. Небольшое замечание, что это может быть не так быстро, как некоторые другие решения здесь, но, как вы говорите, не должно иметь значения. Распределение отличное, лучше, чем у большинства решений здесь, так что +1 от меня! :)
Как это соотносится по качеству (распределению) и производительности с простым использованием промежуточного звена long с умножением каждого ввода на большое число? Например. для двух значений, что-то вроде этого one liner: return ((long)v1 * 805306457 + (long)v2 * 189783887).GetHashCode(); [Простые числа выбраны, чтобы избежать числового переполнения long в проверяемой среде и иметь тенденцию устанавливать разные биты.]
Как @cactuaroid упоминает в комментариях, можно использовать кортеж значений. Это экономит несколько нажатий клавиш и, что более важно, выполняется исключительно в стеке (без мусора):
(PropA, PropB, PropC, PropD).GetHashCode();
(Примечание: оригинальный метод с использованием анонимных типов, похоже, создает объект в куче, то есть мусор, поскольку анонимные типы реализованы как классы, хотя это может быть оптимизировано компилятором. Было бы интересно протестировать эти параметры, но вариант кортежа должен быть выше.)
Microsoft уже предоставляет хороший общий генератор HashCode: просто скопируйте значения свойств / полей в анонимный тип и хешируйте его:
new { PropA, PropB, PropC, PropD }.GetHashCode();
Это будет работать для любого количества свойств. Он не использует бокс. Он просто использует алгоритм, уже реализованный во фреймворке для анонимных типов.
Да, анонимная реализация GetHashCode очень эффективна (кстати, она такая же, как в ответе Джона Скита), но единственная проблема с этим решением заключается в том, что вы генерируете новый экземпляр при любом вызове GetHashCode. Это может быть немного накладным, особенно в случае интенсивного доступа к большим хешированным коллекциям ...
Это работает в VB с .NET 4.0, но, просматривая IL, он использует вызовы box, поскольку тип использует обобщенные типы. Распаковки нет, но из того, что я здесь читаю, простое присутствие бокса предполагает, что это может быть немного неэффективно. Кажется, это единственный выбор для VB, поскольку эквивалента checked / `unchecked 'нет.
@digEmAll Хороший момент, я не думал о накладных расходах на создание нового объекта. Ответ Джона Скита наиболее эффективен и не использует бокс. (@Kumba Чтобы решить непроверенный в VB, просто используйте Int64 (длинный) и усеките его после вычислений.)
В VB.Net: New With {PropA, PropB, PropC, PropD}.GetHashCode()
VB.NET должен использовать ключ при создании анонимного типа: New With {Key PropA}.GetHashCode() В противном случае GetHashCode не вернет один и тот же хэш-код для разных объектов с одинаковыми «идентифицирующими» свойствами.
Не забудьте перечислить свои IEnumerables, иначе случится что-то плохое. new { PropA, PropB, C = PropC.ToList() }.GetHashCode()
@Keith в этом случае я бы подумал о сохранении IEnumerable в качестве значения списка вместо того, чтобы перечислять его каждый раз при вычислении хэш-кода. Caclating ToList каждый раз внутри GetHashCode может снизить производительность во многих ситуациях.
И не забывайте, что приватное свойство / поля в этом случае не нужны;).
@Keith: свойства все объекта не должны влиять на хэш-код. Хэш-код просто должен дать достаточно хорошо распределение ваших объектов. И для вычисления должно быть быстрый. Оставьте перечислимое. И если у вас есть список, не включайте весь список. Используйте Count и, возможно, первый элемент (используйте ноль, если элементов нет). если у вашего класса нет других вариантов, кроме списка; в этом случае, как предлагает Рик, лучше всего кэшировать хэш списка. Напомним, что по определению хэш объекта всегда должен быть одинаковым. Если коллекция изменяется, НЕ включайте ее в hash calc.
Для тех, кому это нравится, (PropA, PropB, PropC, PropD).GetHashCode() теперь доступен на C# 7 без проблем с давлением сборщика мусора @digEmAll. Быстрые и простые комбинации хеш-кодов
@cactuaroid Отлично! Итак, используя кортеж (который является структурой) вместо анонимного типа (класса). Использует ли он тот же расчет за кулисами для Tuple GetHashcode ()?
@RickLove Я не уверен в математике. Tuple.GetHashCode () и ValueTuple.GetHashCode () выглядят одинаково. ValueTuple.GetHashCode () вызывает HashHelper. Tuple.GetHashCode () вызывает Tuple.CombineHashCodes. Для анонимного типа Как Equals и GetHashCode реализованы для анонимных типов?
@cactuaroid: действительно, это отличное решение!
Прошу прощения, что @Timo уже писал о ValueTuple.GetHashCode () ниже.
Вот мой упрощенный подход. Для этого я использую классический шаблон строителя. Он безопасен по типу (без упаковки / распаковки), а также совместим с .NET 2.0 (без методов расширения и т. д.).
Он используется так:
public override int GetHashCode()
{
HashBuilder b = new HashBuilder();
b.AddItems(this.member1, this.member2, this.member3);
return b.Result;
}
А вот и класс фактического строителя:
internal class HashBuilder
{
private const int Prime1 = 17;
private const int Prime2 = 23;
private int result = Prime1;
public HashBuilder()
{
}
public HashBuilder(int startHash)
{
this.result = startHash;
}
public int Result
{
get
{
return this.result;
}
}
public void AddItem<T>(T item)
{
unchecked
{
this.result = this.result * Prime2 + item.GetHashCode();
}
}
public void AddItems<T1, T2>(T1 item1, T2 item2)
{
this.AddItem(item1);
this.AddItem(item2);
}
public void AddItems<T1, T2, T3>(T1 item1, T2 item2, T3 item3)
{
this.AddItem(item1);
this.AddItem(item2);
this.AddItem(item3);
}
public void AddItems<T1, T2, T3, T4>(T1 item1, T2 item2, T3 item3,
T4 item4)
{
this.AddItem(item1);
this.AddItem(item2);
this.AddItem(item3);
this.AddItem(item4);
}
public void AddItems<T1, T2, T3, T4, T5>(T1 item1, T2 item2, T3 item3,
T4 item4, T5 item5)
{
this.AddItem(item1);
this.AddItem(item2);
this.AddItem(item3);
this.AddItem(item4);
this.AddItem(item5);
}
public void AddItems<T>(params T[] items)
{
foreach (T item in items)
{
this.AddItem(item);
}
}
}
вы можете избежать создания объекта внутри функции gethashcode, как в ответе Мангуса. Просто вызовите чертовы статические хеш-функции (кого волнует стартовый хеш). Кроме того, вы можете чаще использовать метод AddItems<T>(params T[] items) во вспомогательном классе (чем каждый раз вызывать AddItem(T)).
И какую пользу вы получаете от this.result * Prime2 * item.GetHashCode(), когда часто используется this.result * Prime2 + item.GetHashCode()?
Я не могу использовать AddItems<T>(params T[] items) чаще, потому что typeof(T1) != typeof(T2) и т. д.
Microsoft является лидером в разработке нескольких способов хеширования ...
//for classes that contain a single int value
return this.value;
//for classes that contain multiple int value
return x ^ y;
//for classes that contain single number bigger than int
return ((int)value ^ (int)(value >> 32));
//for classes that contain class instance fields which inherit from object
return obj1.GetHashCode();
//for classes that contain multiple class instance fields which inherit from object
return obj1.GetHashCode() ^ obj2.GetHashCode() ^ obj3.GetHashCode();
Я могу догадаться, что для нескольких больших int вы можете использовать это:
int a=((int)value1 ^ (int)(value1 >> 32));
int b=((int)value2 ^ (int)(value2 >> 32));
int c=((int)value3 ^ (int)(value3 >> 32));
return a ^ b ^ c;
То же самое и для мульти-типа: все сначала конвертируются в int с помощью GetHashCode()
тогда значения int будут xor'ed, и результатом будет ваш хеш.
Для тех, кто использует хеш в качестве идентификатора (я имею в виду уникальное значение), хеш, естественно, ограничен числом цифр, я думаю, это было 5 байтов для алгоритма хеширования, по крайней мере, MD5.
Вы можете преобразовать несколько значений в хешированное значение, и некоторые из них будут одинаковыми, поэтому не используйте его в качестве идентификатора. (может быть, когда-нибудь я воспользуюсь вашим компонентом)
Иксоринг целых чисел для создания хэш-кода - хорошо известный антипаттерн, который имеет тенденцию приводить к особенно большому количеству конфликтов с реальными значениями.
Все здесь используют целые числа, и никогда не было никакой гарантии того, что хеш будет таким же, он просто попытался быть настолько разнообразным, насколько мало может произойти коллизий.
Да, но ваши второй и пятый не пытаются избежать столкновений.
Не уверен, что это за поток ... но он сделал то же самое, msdn.microsoft.com/en-us/library/…
Да, этот антипаттерн довольно распространен.
вот почему я полагаюсь на это, но спасибо за облегчение ... другое дело в том, что у другого шаблона меньше времени на расчет? ну знаешь, вроде, материя collision vs calculation time тоже есть
Необходимо достичь баланса. Используйте действительно хороший хэш-код, такой как Spookyhash, и вы получите намного, намного лучшее предотвращение столкновений, но у него будет гораздо больше времени на вычисление, чем у любого из них (но когда дело доходит до хеширования очень больших объемов данных, Spookyhash очень быстр). Простой сдвиг одного из значений перед xoring - это лишь незначительные дополнительные затраты для хорошего снижения коллизии. Умножение простых чисел снова увеличивает время и качество. Следовательно, вопрос о том, что лучше между shift или mult, спорный. Обычный xor, хотя очень часто имеет много конфликтов с реальными данными, и его лучше избегать
Вот мой вспомогательный класс, использующий Реализация Джона Скита.
public static class HashCode
{
public const int Start = 17;
public static int Hash<T>(this int hash, T obj)
{
var h = EqualityComparer<T>.Default.GetHashCode(obj);
return unchecked((hash * 31) + h);
}
}
Использование:
public override int GetHashCode()
{
return HashCode.Start
.Hash(_field1)
.Hash(_field2)
.Hash(_field3);
}
Если вы не хотите писать метод расширения для System.Int32:
public readonly struct HashCode
{
private readonly int _value;
public HashCode(int value) => _value = value;
public static HashCode Start { get; } = new HashCode(17);
public static implicit operator int(HashCode hash) => hash._value;
public HashCode Hash<T>(T obj)
{
var h = EqualityComparer<T>.Default.GetHashCode(obj);
return unchecked(new HashCode((_value * 31) + h));
}
public override int GetHashCode() => _value;
}
Он по-прежнему позволяет избежать выделения кучи и используется точно так же:
public override int GetHashCode()
{
// This time `HashCode.Start` is not an `Int32`, it's a `HashCode` instance.
// And the result is implicitly converted to `Int32`.
return HashCode.Start
.Hash(_field1)
.Hash(_field2)
.Hash(_field3);
}
Изменить (май 2018 г.): Геттер EqualityComparer<T>.Default теперь является встроенным в JIT - пул реквест упоминается Стивеном Тубом в это сообщение в блоге.
Я бы изменил строку с третичным оператором на: var h = Equals(obj, default(T)) ? 0 : obj.GetHashCode();
Я считаю, что тернарный оператор с obj != null будет компилироваться в инструкцию box, которая будет выделять память, если T является типом значения. Вместо этого вы можете использовать obj.Equals(null), который будет компилироваться в виртуальный вызов метода Equals.
Поскольку this.hashCode != h. Это не вернет то же значение.
Извините, мне удалось удалить мой комментарий вместо его редактирования. Более выгодно создать новую структуру, а затем изменить hashCode на non-readonly и сделать: «unchecked {this.hashCode ^ = h * 397;} return this;» Например?
Неизменяемость имеет свои преимущества (Почему изменчивые структуры - зло?). Что касается производительности, то, что я делаю, довольно дешево, поскольку оно не выделяет места в куче.
Нет бокса, если вы называете его как Hash (1), а не как Hash <MyInterface> (myStruct). stackoverflow.com/questions/8823239
Вот еще одна свободная реализация алгоритм, опубликованный выше Джоном Скитом, но которая не включает выделения или операции упаковки:
public static class Hash
{
public const int Base = 17;
public static int HashObject(this int hash, object obj)
{
unchecked { return hash * 23 + (obj == null ? 0 : obj.GetHashCode()); }
}
public static int HashValue<T>(this int hash, T value)
where T : struct
{
unchecked { return hash * 23 + value.GetHashCode(); }
}
}
Использование:
public class MyType<T>
{
public string Name { get; set; }
public string Description { get; set; }
public int Value { get; set; }
public IEnumerable<T> Children { get; set; }
public override int GetHashCode()
{
return Hash.Base
.HashObject(this.Name)
.HashObject(this.Description)
.HashValue(this.Value)
.HashObject(this.Children);
}
}
Компилятор гарантирует, что HashValue не вызывается с классом из-за ограничения универсального типа. Но компилятор не поддерживает HashObject, поскольку добавление универсального аргумента также добавляет операцию упаковки.
У меня возникла проблема с числами с плавающей запятой и десятичными числами, используя реализацию, выбранную в качестве ответа выше.
Этот тест не проходит (плавает; хэш тот же, хотя я переключил 2 значения на отрицательные):
var obj1 = new { A = 100m, B = 100m, C = 100m, D = 100m};
var obj2 = new { A = 100m, B = 100m, C = -100m, D = -100m};
var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different hash1:{0} hash2:{1}",hash1,hash2));
Но этот тест проходит (с целыми числами):
var obj1 = new { A = 100m, B = 100m, C = 100, D = 100};
var obj2 = new { A = 100m, B = 100m, C = -100, D = -100};
var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different hash1:{0} hash2:{1}",hash1,hash2));
Я изменил свою реализацию, чтобы не использовать GetHashCode для примитивных типов, и, похоже, он работает лучше
private static int InternalComputeHash(params object[] obj)
{
unchecked
{
var result = (int)SEED_VALUE_PRIME;
for (uint i = 0; i < obj.Length; i++)
{
var currval = result;
var nextval = DetermineNextValue(obj[i]);
result = (result * MULTIPLIER_VALUE_PRIME) + nextval;
}
return result;
}
}
private static int DetermineNextValue(object value)
{
unchecked
{
int hashCode;
if (value is short
|| value is int
|| value is byte
|| value is sbyte
|| value is uint
|| value is ushort
|| value is ulong
|| value is long
|| value is float
|| value is double
|| value is decimal)
{
return Convert.ToInt32(value);
}
else
{
return value != null ? value.GetHashCode() : 0;
}
}
}
Если вы задумали иначе, unchecked НЕ влияет на Convert.ToInt32: uint, long, float, double и decimal могут здесь переполниться.
Очень похоже на решение nightcoder, за исключением того, что при желании проще поднимать простые числа.
PS: Это один из тех случаев, когда вас немного рвет во рту, зная, что это можно преобразовать в один метод с 9 стандартными методами, но он будет медленнее, поэтому вы просто закрываете глаза и пытаетесь забыть об этом.
/// <summary>
/// Try not to look at the source code. It works. Just rely on it.
/// </summary>
public static class HashHelper
{
private const int PrimeOne = 17;
private const int PrimeTwo = 23;
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9, T10 arg10)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
hash = hash * PrimeTwo + arg8.GetHashCode();
hash = hash * PrimeTwo + arg9.GetHashCode();
hash = hash * PrimeTwo + arg10.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
hash = hash * PrimeTwo + arg8.GetHashCode();
hash = hash * PrimeTwo + arg9.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
hash = hash * PrimeTwo + arg8.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, T4 arg4)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
return hash;
}
}
}
Не обрабатывает нули.
Пользователи ReSharper могут генерировать GetHashCode, Equals и другие с помощью ReSharper -> Edit -> Generate Code -> Equality Members.
// ReSharper's GetHashCode looks like this
public override int GetHashCode() {
unchecked {
int hashCode = Id;
hashCode = (hashCode * 397) ^ IntMember;
hashCode = (hashCode * 397) ^ OtherIntMember;
hashCode = (hashCode * 397) ^ (RefMember != null ? RefMember.GetHashCode() : 0);
// ...
return hashCode;
}
}
Что касается https://github.com/dotnet/coreclr/pull/14863, появился новый способ генерации хэш-кодов, который очень прост! Просто пиши
public override int GetHashCode()
=> HashCode.Combine(field1, field2, field3);
Это сгенерирует качественный хэш-код, и вам не придется беспокоиться о деталях реализации.
Похоже, это приятное дополнение ... Есть ли способ узнать, какая версия .NET Core будет поставляться?
@DanJ Какое счастливое совпадение, изменения HashCode для corefx были объединены всего за пару часов до вашего комментария :) Этот тип планируется выпустить в .NET Core 2.1.
Это потрясающе - и довольно много времени на обработку. Проголосовали. :)
@DanJ Еще лучшие новости - он должен быть доступен прямо сейчас в ночных сборках CoreFX, размещенных в ленте MyGet ядра dotnet.
Милый - это не помогает мне в работе, так как мы не совсем передовые который, но это полезно знать. Ваше здоровье!
Вот вставляемый пакет polyfill, который можно использовать для всего .NET 4.0+ (включая System.HashCode): nuget.org/packages/Gapotchenko.FX
Если у нас не более 8 объектов (надеюсь), есть еще одна альтернатива.
ValueTuple - это структура, которая, похоже, имеет надежную реализацию GetHashCode.
Это означает, что мы могли бы просто сделать это:
// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();
Давайте посмотрим на текущую реализацию .NET Core для ValueTupleGetHashCode.
internal static int CombineHashCodes(int h1, int h2)
{
return HashHelpers.Combine(HashHelpers.Combine(HashHelpers.RandomSeed, h1), h2);
}
internal static int CombineHashCodes(int h1, int h2, int h3)
{
return HashHelpers.Combine(CombineHashCodes(h1, h2), h3);
}
public static readonly int RandomSeed = Guid.NewGuid().GetHashCode();
public static int Combine(int h1, int h2)
{
unchecked
{
// RyuJIT optimizes this to use the ROL instruction
// Related GitHub pull request: dotnet/coreclr#1830
uint rol5 = ((uint)h1 << 5) | ((uint)h1 >> 27);
return ((int)rol5 + h1) ^ h2;
}
}
На английском:
Было бы неплохо узнать больше о свойствах этого алгоритма хэш-кода ROL-5.
К сожалению, переход на ValueTuple для нашего собственного GetHashCode может оказаться не таким быстрым, как нам хотелось бы и ожидать. Этот комментарий в соответствующем обсуждении показывает, что прямой вызов HashHelpers.Combine более эффективен. С другой стороны, этот внутренний, поэтому нам пришлось бы скопировать код, пожертвовав многим из того, что мы здесь получили. Кроме того, мы будем нести ответственность за запоминание первого Combine со случайным семенем. Я не знаю, каковы будут последствия, если мы пропустим этот шаг.
Предполагая, что h1 >> 27 равен 0, чтобы игнорировать его, h1 << 5 равен h1 * 32, поэтому он такой же, как h1 * 33 ^ h2. Согласно эта страница, он называется «Модифицированный Бернштейн».
Это статический вспомогательный класс, реализующий реализацию Джоша Блоха; и предоставляет явные перегрузки для «предотвращения» упаковки, а также для реализации хеширования специально для длинных примитивов.
Вы можете передать сравнение строк, которое соответствует вашей реализации equals.
Поскольку вывод Hash всегда является int, вы можете просто связать вызовы Hash.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using System.Runtime.CompilerServices;
namespace Sc.Util.System
{
/// <summary>
/// Static methods that allow easy implementation of hashCode. Example usage:
/// <code>
/// public override int GetHashCode()
/// => HashCodeHelper.Seed
/// .Hash(primitiveField)
/// .Hsh(objectField)
/// .Hash(iEnumerableField);
/// </code>
/// </summary>
public static class HashCodeHelper
{
/// <summary>
/// An initial value for a hashCode, to which is added contributions from fields.
/// Using a non-zero value decreases collisions of hashCode values.
/// </summary>
public const int Seed = 23;
private const int oddPrimeNumber = 37;
/// <summary>
/// Rotates the seed against a prime number.
/// </summary>
/// <param name = "aSeed">The hash's first term.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int rotateFirstTerm(int aSeed)
{
unchecked {
return HashCodeHelper.oddPrimeNumber * aSeed;
}
}
/// <summary>
/// Contributes a boolean to the developing HashCode seed.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aBoolean">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, bool aBoolean)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ (aBoolean
? 1
: 0);
}
}
/// <summary>
/// Contributes a char to the developing HashCode seed.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aChar">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, char aChar)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ aChar;
}
}
/// <summary>
/// Contributes an int to the developing HashCode seed.
/// Note that byte and short are handled by this method, through implicit conversion.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aInt">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, int aInt)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ aInt;
}
}
/// <summary>
/// Contributes a long to the developing HashCode seed.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aLong">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, long aLong)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ (int)(aLong ^ (aLong >> 32));
}
}
/// <summary>
/// Contributes a float to the developing HashCode seed.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aFloat">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, float aFloat)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ Convert.ToInt32(aFloat);
}
}
/// <summary>
/// Contributes a double to the developing HashCode seed.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aDouble">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, double aDouble)
=> aSeed.Hash(Convert.ToInt64(aDouble));
/// <summary>
/// Contributes a string to the developing HashCode seed.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aString">The value to contribute.</param>
/// <param name = "stringComparison">Optional comparison that creates the hash.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(
this int aSeed,
string aString,
StringComparison stringComparison = StringComparison.Ordinal)
{
if (aString == null)
return aSeed.Hash(0);
switch (stringComparison) {
case StringComparison.CurrentCulture :
return StringComparer.CurrentCulture.GetHashCode(aString);
case StringComparison.CurrentCultureIgnoreCase :
return StringComparer.CurrentCultureIgnoreCase.GetHashCode(aString);
case StringComparison.InvariantCulture :
return StringComparer.InvariantCulture.GetHashCode(aString);
case StringComparison.InvariantCultureIgnoreCase :
return StringComparer.InvariantCultureIgnoreCase.GetHashCode(aString);
case StringComparison.OrdinalIgnoreCase :
return StringComparer.OrdinalIgnoreCase.GetHashCode(aString);
default :
return StringComparer.Ordinal.GetHashCode(aString);
}
}
/// <summary>
/// Contributes a possibly-null array to the developing HashCode seed.
/// Each element may be a primitive, a reference, or a possibly-null array.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aArray">CAN be null.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, IEnumerable aArray)
{
if (aArray == null)
return aSeed.Hash(0);
int countPlusOne = 1; // So it differs from null
foreach (object item in aArray) {
++countPlusOne;
if (item is IEnumerable arrayItem) {
if (!object.ReferenceEquals(aArray, arrayItem))
aSeed = aSeed.Hash(arrayItem); // recursive call!
} else
aSeed = aSeed.Hash(item);
}
return aSeed.Hash(countPlusOne);
}
/// <summary>
/// Contributes a possibly-null array to the developing HashCode seed.
/// You must provide the hash function for each element.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aArray">CAN be null.</param>
/// <param name = "hashElement">Required: yields the hash for each element
/// in <paramref name = "aArray"/>.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash<T>(this int aSeed, IEnumerable<T> aArray, Func<T, int> hashElement)
{
if (aArray == null)
return aSeed.Hash(0);
int countPlusOne = 1; // So it differs from null
foreach (T item in aArray) {
++countPlusOne;
aSeed = aSeed.Hash(hashElement(item));
}
return aSeed.Hash(countPlusOne);
}
/// <summary>
/// Contributes a possibly-null object to the developing HashCode seed.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "aObject">CAN be null.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, object aObject)
{
switch (aObject) {
case null :
return aSeed.Hash(0);
case bool b :
return aSeed.Hash(b);
case char c :
return aSeed.Hash(c);
case int i :
return aSeed.Hash(i);
case long l :
return aSeed.Hash(l);
case float f :
return aSeed.Hash(f);
case double d :
return aSeed.Hash(d);
case string s :
return aSeed.Hash(s);
case IEnumerable iEnumerable :
return aSeed.Hash(iEnumerable);
}
return aSeed.Hash(aObject.GetHashCode());
}
/// <summary>
/// This utility method uses reflection to iterate all specified properties that are readable
/// on the given object, excluding any property names given in the params arguments, and
/// generates a hashcode.
/// </summary>
/// <param name = "aSeed">The developing hash code, or the seed: if you have no seed, use
/// the <see cref = "Seed"/>.</param>
/// <param name = "aObject">CAN be null.</param>
/// <param name = "propertySelector"><see cref = "BindingFlags"/> to select the properties to hash.</param>
/// <param name = "ignorePropertyNames">Optional.</param>
/// <returns>A hash from the properties contributed to <c>aSeed</c>.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int HashAllProperties(
this int aSeed,
object aObject,
BindingFlags propertySelector
= BindingFlags.Instance
| BindingFlags.Public
| BindingFlags.GetProperty,
params string[] ignorePropertyNames)
{
if (aObject == null)
return aSeed.Hash(0);
if ((ignorePropertyNames != null)
&& (ignorePropertyNames.Length != 0)) {
foreach (PropertyInfo propertyInfo in aObject.GetType()
.GetProperties(propertySelector)) {
if (!propertyInfo.CanRead
|| (Array.IndexOf(ignorePropertyNames, propertyInfo.Name) >= 0))
continue;
aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
}
} else {
foreach (PropertyInfo propertyInfo in aObject.GetType()
.GetProperties(propertySelector)) {
if (propertyInfo.CanRead)
aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
}
}
return aSeed;
}
/// <summary>
/// NOTICE: this method is provided to contribute a <see cref = "KeyValuePair{TKey,TValue}"/> to
/// the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
/// this method has a different name since it will not be automatically invoked by
/// <see cref = "Hash(int,object)"/>, <see cref = "Hash(int,IEnumerable)"/>,
/// or <see cref = "HashAllProperties"/> --- you MUST NOT mix this method with those unless
/// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
/// the generated hash code will not be consistent. This method itself ALSO will not invoke
/// this method on the Key or Value here if that itself is a KeyValuePair.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "keyValuePair">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int HashKeyAndValue<TKey, TValue>(this int aSeed, KeyValuePair<TKey, TValue> keyValuePair)
=> aSeed.Hash(keyValuePair.Key)
.Hash(keyValuePair.Value);
/// <summary>
/// NOTICE: this method is provided to contribute a collection of <see cref = "KeyValuePair{TKey,TValue}"/>
/// to the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
/// this method has a different name since it will not be automatically invoked by
/// <see cref = "Hash(int,object)"/>, <see cref = "Hash(int,IEnumerable)"/>,
/// or <see cref = "HashAllProperties"/> --- you MUST NOT mix this method with those unless
/// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
/// the generated hash code will not be consistent. This method itself ALSO will not invoke
/// this method on a Key or Value here if that itself is a KeyValuePair or an Enumerable of
/// KeyValuePair.
/// </summary>
/// <param name = "aSeed">The developing HashCode value or seed.</param>
/// <param name = "keyValuePairs">The values to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int HashKeysAndValues<TKey, TValue>(
this int aSeed,
IEnumerable<KeyValuePair<TKey, TValue>> keyValuePairs)
{
if (keyValuePairs == null)
return aSeed.Hash(null);
foreach (KeyValuePair<TKey, TValue> keyValuePair in keyValuePairs) {
aSeed = aSeed.HashKeyAndValue(keyValuePair);
}
return aSeed;
}
}
}
Ура: Я нашел ошибку! Исправлен метод HashKeysAndValues: он вызывает HashKeyAndValue.
Если вы используете .NET Standard 2.1 или выше, вы можете использовать структуру System.HashCode. Есть два способа его использования:
Метод Combine можно использовать для создания хэш-кода, содержащего до восьми объектов.
public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);
Метод Add помогает работать с коллекциями:
public override int GetHashCode()
{
var hashCode = new HashCode();
hashCode.Add(this.object1);
foreach (var item in this.collection)
{
hashCode.Add(item);
}
return hashCode.ToHashCode();
}
Вы можете прочитать полную запись в блоге «GetHashCode - это просто» для получения более подробной информации и комментариев.
public class SuperHero
{
public int Age { get; set; }
public string Name { get; set; }
public List<string> Powers { get; set; }
public override int GetHashCode() =>
HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers);
}
public struct HashCode : IEquatable<HashCode>
{
private const int EmptyCollectionPrimeNumber = 19;
private readonly int value;
private HashCode(int value) => this.value = value;
public static implicit operator int(HashCode hashCode) => hashCode.value;
public static bool operator ==(HashCode left, HashCode right) => left.Equals(right);
public static bool operator !=(HashCode left, HashCode right) => !(left == right);
public static HashCode Of<T>(T item) => new HashCode(GetHashCode(item));
public static HashCode OfEach<T>(IEnumerable<T> items) =>
items == null ? new HashCode(0) : new HashCode(GetHashCode(items, 0));
public HashCode And<T>(T item) =>
new HashCode(CombineHashCodes(this.value, GetHashCode(item)));
public HashCode AndEach<T>(IEnumerable<T> items)
{
if (items == null)
{
return new HashCode(this.value);
}
return new HashCode(GetHashCode(items, this.value));
}
public bool Equals(HashCode other) => this.value.Equals(other.value);
public override bool Equals(object obj)
{
if (obj is HashCode)
{
return this.Equals((HashCode)obj);
}
return false;
}
public override int GetHashCode() => this.value.GetHashCode();
private static int CombineHashCodes(int h1, int h2)
{
unchecked
{
// Code copied from System.Tuple a good way to combine hashes.
return ((h1 << 5) + h1) ^ h2;
}
}
private static int GetHashCode<T>(T item) => item?.GetHashCode() ?? 0;
private static int GetHashCode<T>(IEnumerable<T> items, int startHashCode)
{
var temp = startHashCode;
var enumerator = items.GetEnumerator();
if (enumerator.MoveNext())
{
temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
while (enumerator.MoveNext())
{
temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
}
}
else
{
temp = CombineHashCodes(temp, EmptyCollectionPrimeNumber);
}
return temp;
}
}
Алгоритм, вычисляющий хэш-код, должен быть быстрым. Простой алгоритм обычно оказывается более быстрым. Тот, который не выделяет дополнительную память, также снизит потребность в сборке мусора, что, в свою очередь, также повысит производительность.
Алгоритм хеширования должен быть детерминированный, т.е. при одном и том же вводе он всегда должен выдавать один и тот же вывод.
Алгоритм, вычисляющий хэш-код, должен поддерживать минимальное значение хеш-коллизии. Конфликт хеширования - это ситуация, которая возникает, когда два вызова GetHashCode на двух разных объектах производят идентичные хэш-коды. Обратите внимание, что столкновения разрешены (некоторые ошибочно полагают, что это не так), но их следует свести к минимуму.
Хорошая хеш-функция должна отображать ожидаемые входные данные как можно более равномерно по выходному диапазону. Он должен иметь единообразие.
В .NET Core каждый раз, когда вы перезапускаете приложение, вы будете получать разные хэш-коды. Это функция безопасности для предотвращения атак типа «отказ в обслуживании» (DoS). Для .NET Framework вы должен активируете эту функцию, добавив следующий файл App.config:
<?xml version = "1.0"?>
<configuration>
<runtime>
<UseRandomizedStringHashAlgorithm enabled = "1" />
</runtime>
</configuration>
Из-за этой функции хэш-коды никогда не должны использоваться за пределами домена приложения, в котором они были созданы, они никогда не должны использоваться в качестве ключевых полей в коллекции, и они никогда не должны сохраняться.
Подробнее об этом здесь.
Алгоритм не обязательно должен быть Криптографическая хеш-функция. Это означает, что он не должен удовлетворять следующим условиям:
Это очень хороший ответ. В качестве дополнения вы можете рассмотреть возможность изменения «скорости» на «производительность» и добавления свойства отсутствия выделения памяти. Встроенный тип HashCode этому тоже удовлетворяет.
Как это соотносится с ответом ValueTuple.GetHashCode(), недавно обновленным @ricklove выше?
HashCode.Combine - это статический метод, который ничего не выделяет, в то время как ValueTuple начинает с выделения в стеке.
HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers) - красивый синтаксис :)
Если вы хотите полифилить HashCode из netstandard2.1
public static class HashCode
{
public static int Combine(params object[] instances)
{
int hash = 17;
foreach (var i in instances)
{
hash = unchecked((hash * 31) + (i?.GetHashCode() ?? 0));
}
return hash;
}
}
Примечание: если используется с struct, он будет выделять память из-за бокса.
Можно попробовать перенять подход из библиотек C++ Boost. Что-то вроде этого:
class HashUtil
{
public static int HashCombine(int seed, int other)
{
unchecked
{
return other + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
}
}
а потом:
class MyClass
{
private string _field1;
private int _field2;
private AnotherClass _field3;
private YetAnotherClass _field4;
public override int GetHashCode()
{
int result = HashUtil.HashCombine(_field1.GetHashCode(), _field2);
result = HashUtil.HashCombine(result, _field3.GetHashCode());
return HashUtil.HashCombine(result, _field4.GetHashCode());
}
}
Я хочу добавить свои последние открытия в эту ветку, к которой я так часто возвращался.
Моя текущая настройка визуальной студии / проекта обеспечивает функциональность для автоматического преобразования кортежей в структуры. Это сгенерирует такую функцию GetHashCode:
public override int GetHashCode()
{
int hashCode = -2088324004;
hashCode = hashCode * -1521134295 + AuftragGesperrt.GetHashCode();
hashCode = hashCode * -1521134295 + Auftrag_gesperrt_von.GetHashCode();
hashCode = hashCode * -1521134295 + Auftrag_gesperrt_am.GetHashCode();
return hashCode;
}
Прочитав этот вопрос и статью ниже, я смог реализовать переопределение
GetHashCode. Я надеюсь, что это будет полезно для других. Рекомендации и правила для GetHashCode, написанные Эриком Липпертом