Каков наилучший алгоритм переопределения GetHashCode?

В .NET GetHashCode метод используется во многих местах в библиотеках базовых классов .NET. Его правильная реализация особенно важна для быстрого поиска элементов в коллекции или при определении равенства.

Есть ли стандартный алгоритм или передовой опыт реализации GetHashCode для моих пользовательских классов, чтобы я не снижал производительность?

Прочитав этот вопрос и статью ниже, я смог реализовать переопределение GetHashCode. Я надеюсь, что это будет полезно для других. Рекомендации и правила для GetHashCode, написанные Эриком Липпертом

rene 23.03.2012 01:59

«или определить равенство»: нет! Два объекта с одинаковым хэш-кодом не обязательно равны.

Thomas Levesque 03.09.2015 01:03

@ThomasLevesque Вы правы, два объекта с одинаковым хеш-кодом не обязательно равны. Но все же GetHashCode() используется во многих реализациях Equals(). Вот что я имел в виду в этом заявлении. GetHashCode() внутри Equals() часто используется как ярлык для определения неравенство, потому что, если два объекта имеют хэш-код разные, они должны быть объектами, которые не равны, и остальная часть проверки равенства не должна выполняться.

bitbonk 03.09.2015 01:27

@bitbonk Обычно и GetHashCode(), и Equals() должны просматривать все поля обоих объектов (Equals должен это сделать, если хэш-коды совпадают или не проверены). Из-за этого вызов GetHashCode() внутри Equals() часто является избыточным и может снизить производительность. Equals() также может иметь возможность короткого замыкания, что делает его намного быстрее - однако в некоторых случаях хэш-коды могут быть кэшированы, что делает проверку GetHashCode() более быстрой и полезной. Подробнее см. этот вопрос.

NotEnoughData 02.04.2017 06:52

ОБНОВЛЕНИЕ ЯНВАРЯ 2020: Блог Эрика Липперта, расположенный по адресу: docs.microsoft.com/en-us/archive/blogs/ericlippert/…

Rick Davin 15.01.2020 17:06

ОБНОВЛЕНИЕ МАРТ 2020 ГОДА: ссылка с @RickDavin верна, но статья на docs.microsoft.com имеет плохой формат. Вот такая же статья в блоге Эрика. ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashc‌ ode

zumalifeguard 19.03.2020 13:29

Теперь вы можете просто использовать HashCode.Combine (field1, field2, ...)

Ε Г И І И О 23.04.2020 18:23
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1 522
7
232 809
21
Перейти к ответу Данный вопрос помечен как решенный

Ответы 21

Ответ принят как подходящий

Я обычно использую что-то вроде реализации, данной в книге Джоша Блоха поразительнйЭффективная 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?

bitbonk 05.11.2008 00:44

Ага, Int64.GetHashCode делает именно это. В Java, конечно, потребуется бокс. Это напоминает мне - пора добавить ссылку на книгу ...

Jon Skeet 05.11.2008 00:51

23 - не лучший выбор, поскольку (начиная с .net 3.5 SP1) Dictionary<TKey,TValue> предполагает хорошее распределение по модулю определенных простых чисел. И 23 - один из них. Итак, если у вас есть словарь с емкостью 23, только последний вклад в GetHashCode влияет на составной хэш-код. Так что я бы предпочел использовать 29 вместо 23.

CodesInChaos 22.11.2010 01:41

@Ani: ваша реализация разместила в куче несколько новых объектов, поэтому производительность может быть ниже, чем при ручной реализации. Приемлемо ли это, зависит от вашего типа и использования. Проверьте некоторые другие ответы для помощников, использующих универсальные шаблоны, которые позволяют избежать этой проблемы.

CodesInChaos 22.11.2010 01:43

@CodeInChaos: только последний вклад влияет на ведро, поэтому в худшем случае ему придется просматривать записи все 23 в словаре. Он по-прежнему будет проверять фактический хэш-код каждой записи, что будет дешево. Если у вас есть такой маленький словарь, вряд ли это будет иметь большое значение.

Jon Skeet 22.11.2010 02:14

@Jon: Я должен спросить, несмотря на то, что уже открыл мой собственный вопрос по этой теме, но какая хорошая версия для VB, поскольку в VB отсутствуют ключевые слова checked и unchecked? Я попытался сделать tmpHash Int64 и выполнить операцию AND с младшими 8 битами (в соответствии с принятый ответ на мой вопрос), но на достаточно большом наборе полей это каким-то образом привело к тому, что вычисление обернулось до 0 для оставшейся части цикла.

Kumba 18.01.2011 08:05

@Kumba: Боюсь, я не знаю, как бы это сделать в VB. Проверяется ли арифметика всегда в VB? Могли бы вы иметь отдельную библиотеку классов, которой вы могли бы делегировать арифметику, написанную на C# или с отключенной проверенной арифметикой для всего проекта?

Jon Skeet 18.01.2011 10:08

@Jon: VB явно проверяет много вещей. У него есть фетиш требовать, чтобы числа без знака преобразовывались в числа со знаком, прежде чем вы сможете их сдвинуть влево или вправо. Что заставляет меня взбираться по стене и по потолку. Я пытаюсь реализовать хеш Jenkins, чтобы обойти отсутствие отмеченных / непроверенных (вращающийся хеш также помогает, но меня беспокоят конфликты хешей с вводом). Я бы хотел избежать использования отдельной библиотеки C#, потому что она, по сути, допускает поражение. Если я дойду до этого, мне нужно будет просто переписать весь проект на C#.

Kumba 18.01.2011 10:28

Разве «непроверенный» ненужный b / c CLR по умолчанию будет счастливо переполняться?

pomeroy 18.01.2011 18:22

@pomeroy: Это зависит от настроек проекта. По сути, вы даете сборке контекст по умолчанию, отмеченный или не отмеченный.

Jon Skeet 18.01.2011 18:47

@pomeroy: VB не такой детализированный, как C#. Поскольку в нем отсутствуют два вышеупомянутых ключевых слова, ваш единственный вариант - удалить целое число переполнений для всего проекта или нет. Я предполагаю, что если ваш проект завершен и в целом хорошо протестирован, удаление проверок переполнения является безопасным делом. Однако при его создании и отладке эти проверки хороши, потому что они выделяют ошибки, которые нужно исправить. Я открыл Connect Ticket # 636564 с Microsoft, чтобы порекомендовать включить поддержку ключевых слов checked / unchecked в следующий выпуск .NET. Однако не уверен, что они сделают это.

Kumba 18.01.2011 23:38

Я добавлю, что мне придется использовать алгоритм ротации хешей, связанный с ответом Джона выше. Он не переполняется, даже в Int32, не (пока) не переносится в 0 на большом количестве полей в вычислении, и выполняется просто и довольно быстро. Хеш Jenkins не сработал ... Даже это переполняется случайным образом, в зависимости от ввода. Кроме того, принудительный сдвиг битов в знаковой математике мешает многим вещам. Я мог бы открыть еще одну ошибку, если это не предполагалось каким-то образом.

Kumba 18.01.2011 23:41

Разве вам не нужен override в объявлении вашего метода? Также было бы хорошо поставить нулевые проверки, поскольку это такой хорошо используемый пример.

Rory 05.02.2011 13:16

@Rory: Я добавил переопределение, спасибо - я не собираюсь вводить нулевые проверки, так как я чувствую, что это заслонит важные моменты. ИМО комментария хватает.

Jon Skeet 05.02.2011 13:23

Зачем начинать с простого, а не с нуля? есть ли у int hash = 17; какие-либо теоретически поддерживаемые преимущества?

fredoverflow 06.02.2011 17:41

@FredOverflow: я не знаю точных деталей всех причин, стоящих за этим, но начало с 0 означало бы, что хеш останется равным нулю, если отдельные хэши полей будут равны нулю ... и это, вероятно, не редкость (например, целое число нулевого значения, вероятно, будет хеширован до нуля). Просто предположение, но я подозреваю, что наличие константы, которая распространяется с каждым полем, полезно. На самом деле это просто скопировано из Effective Java :)

Jon Skeet 06.02.2011 19:59

@JonSkeet Насколько безопасным будет этот алгоритм для сложного графа объектов, состоящего, скажем, из 500 объектов, каждый из которых имеет 10 свойств. Связанный вопрос: stackoverflow.com/questions/5308057/…

bitbonk 15.03.2011 17:04

@bitbonk: Вероятность столкновения при любом отдельном изменении будет довольно низкой ... но в вопросе, о котором вы говорите, я бы, вероятно, использовал вместо этого криптографический хеш.

Jon Skeet 15.03.2011 17:09

Тогда возникает вопрос: как мне создать криптографический хеш для объектной модели?

bitbonk 15.03.2011 19:51

@bitbonk: Я бы настоятельно рекомендовал использовать «нормальный» криптографический хеш для результата двоичной сериализации формы.

Jon Skeet 15.03.2011 20:55

Этот алгоритм в основном представляет собой алгоритм хеширования строк DJB2, для которого рекомендуются константы 5381 и 33 (cse.yorku.ca/~oz/hash.html). Честно говоря, я не уверен, что константа имеет большое значение, но множитель важен.

yoyo 16.12.2011 22:56

@JonSkeet Я понимаю, что воскрешаю здесь мертвых, но реализация хэшей для меня в новинку. Какие поля я включаю в хеш в вашей реализации? Только неизменяемые, или какие-то поля хороши?

KChaloux 26.10.2012 02:06

@KChaloux: Это полностью зависит от того, что вы хотите, чтобы равенство значило. Однако обычно включать изменяемые данные - плохая идея.

Jon Skeet 26.10.2012 02:08

Как бы вы справились с недействительностью? Если просто игнорировать это поле, то для A = null, B = "ss" и для A = "ss", B = null у нас будут коллизии. Не лучше ли умножать каждое поле на разные простые числа?

Vajda 22.01.2013 20:33

@Vajda: я обычно использую 0 в качестве эффективного хеш-кода для null - это не то же самое, что игнорирование поля.

Jon Skeet 22.01.2013 20:49

@ jnm2: Честно говоря, я не понимаю твоих аргументов. В частности, я только что попробовал это эффективное хеширование 10 полей - и, изменив значение только, первое поле все равно изменило хеш, что противоречит вашему утверждению о том, что «каждый бит первых хеш-кодов будет потерян».

Jon Skeet 20.11.2013 18:50

Вы можете довольно просто продемонстрировать, что это дает плохое распределение. Возьмите этот вариант FNV и примените его к строкам (используйте небезопасные манипуляции с указателями, чтобы получать целые числа за раз, чтобы дать ему шанс). Используйте его для добавления строк в хеш-таблицу, основанную на степени двойки. С тем, над которым я сейчас работаю, если я сгенерирую «1», «2», ... «999999» и добавлю их, это займет около 34 секунд. Теперь возьмем тот же метод хеширования и повторно хешируем результат с хорошо распределенным хешем. С хорошим хешем это может только усугубить ситуацию (тратится больше времени, и мы можем вводить новые коллизии, но никогда их не удалять). С ...

Jon Hanna 14.01.2014 14:23

... та же хеш-таблица, над которой я работаю, тот же код для генерации "1" ... "999999" и их добавление занимает 1 секунду. Эффект менее выражен с хешами на основе простых чисел, поэтому в этом случае дополнительное время, потраченное на повторное хеширование (и, возможно, сокращение возможных результатов, хотя это маловероятно), ничего не дает, но низкая производительность при мощности -два таблицы демонстрируют плохое распределение в целом.

Jon Hanna 14.01.2014 14:31

@JonHanna: Спасибо за это. Не уверен, что вы имеете в виду, говоря «получать целые числа за раз», но я постараюсь взглянуть повнимательнее. Мне все еще нравится это в первом приближении для хеша, но если у вас есть другой хеш, который так же просто запомнить и исправить, но с лучшим распределением, я был бы очень рад изменить свою практику :)

Jon Skeet 14.01.2014 15:10

Я имел в виду, что использовал fixed(char* ptr = str){int* iPtr = (int*)ptr;..., но я также пытался просто сделать foreach(char c in str) и преобразовать каждый char в int, и то же самое применимо. Относительная слабость стала очевидной для меня, когда у меня была причина использовать таблицы степени двух и я получал плохие результаты (я сам использовал почти то же, что и выше). Решение, к которому я наконец пришел, - это забыть о том, что его легко запомнить, и один раз создать трудно запоминающийся метод, а затем упростить его использование и поместить его код в nuget.org/packages/SpookilySharp Я добавлю полный ответ здесь на обеденный перерыв.

Jon Hanna 14.01.2014 15:24

@JonSkeet и теперь ответил.

Jon Hanna 14.01.2014 18:33

@JonHanna: Спасибо за это. Придется посмотреть поподробнее, когда будет куча времени :)

Jon Skeet 14.01.2014 18:51

Я думаю, важно отметить, что мы должны быть осторожны с изменением хеш-кода во время выполнения. У нас была ошибка в моем проекте, потому что предыдущий разработчик реализовал алгоритм GetHashCode, основанный на этом ответе. Но в его реализации у него был список объектов, он использовал хэш каждого элемента в коллекции для генерации хеш-кода объекта. Поэтому при изменении коллекции изменился и хэш-код. Это вызывало проблемы с привязкой в ​​WPF. И если бы у вас был объект, например, в словаре, вы бы тоже получили ошибки.

Dzyann 14.02.2014 20:11

@Dzyann: Да, изменять ключ таким образом, чтобы это влияло на равенство - и, следовательно, на хэш-код - это всегда плохая идея. Добавлю примечание.

Jon Skeet 14.02.2014 20:59

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

Dzyann 14.02.2014 22:32

Я бы посоветовал вам заменить 17 и 23 константами здесь. (Спасибо за ссылку.) Благодаря этому простой поиск по словарю стал намного эффективнее, в моем случае на ~ 60% лучше.

jnm2 23.04.2014 21:04

@ jnm2: Это не тот алгоритм для начала - он использует XOR, а не ADD. Я буду придерживаться этих констант для этого ответа, но, может быть, вам стоит добавить свой собственный ответ?

Jon Skeet 23.04.2014 21:07

Фактически, я собирался предположить, что xoring вместо добавления не уменьшит простоту хеш-алгоритма перехода. Что вы думаете?

jnm2 23.04.2014 21:08

В моем случае XOR ускоряет GetHashCode () на 12%.

jnm2 23.04.2014 21:17

@ jnm2: Ну, это не уменьшило бы эту простоту - но это не то, чем я занимался последние несколько лет. Я добавлю FNV в качестве альтернативы.

Jon Skeet 23.04.2014 21:38
int hash = 2166136261; Не хватает ли гипса? Компилятор говорит, что 2166136261 - это uint ... Я поменял его на int hash = (int)2166136261;
Roman Ganz 24.04.2014 16:52

Я попытался реализовать этот подход для ValueUtils, но в моем тестировании этот вариант FNV вызвал значительные коллизии (24%) в некоторых симметричных наборах данных. И, возможно, это потому, что это НЕ хеш FNV? Традиционные хэши FNV на октет (байт), а не на 32-битное слово. Это дает этому варианту меньше возможностей смешивать эти биты ...

Eamon Nerbonne 01.06.2014 18:15

@EamonNerbonne: Что вы имеете в виду под «этим подходом»? Теперь ответ содержит две разные версии ...

Jon Skeet 01.06.2014 19:53

Я имею в виду этот вариант FNV - это не совсем FNV, и я почти уверен, что это только усугубляет ситуацию. Я, кстати, тоже пробовал рецепт h=prime; repeat h=h*prime + ?; это, кажется, меняется; он вполне подходит для больших простых чисел, особенно если ваш промежуточный разряд имеет ширину 64 бита.

Eamon Nerbonne 01.06.2014 23:27

@Eamon: Боюсь, я недостаточно знаю теорию, чтобы комментировать дальше :(

Jon Skeet 01.06.2014 23:50

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

Eamon Nerbonne 01.06.2014 23:58

@EamonNerbonne: Хорошо. Я отредактирую, чтобы указать, что это модификация, и что она не работает, по крайней мере, в некоторых случаях.

Jon Skeet 01.06.2014 23:59

@EamonNerbonne: Какие лучшие коэффициенты вам известны?

jnm2 03.06.2014 16:09

@ jnm2 В моих экспериментах смещение мало что значит, и тенденция такова, что большие простые числа работают лучше, с оговоркой, что все это сложно проверить, потому что это медленно (очень медленно), чтобы быть тщательным, и это зависит от способа, которым ваш набор данных "испорчен". Если ваши поля имеют совершенно случайно распределенные хэш-коды - все это не имеет значения, но, конечно, в реальном мире эти хэш-коды не случайны, и поля коррелированы. Есть довольно веская причина, по которой большие простые числа тоже будут лучше - они лучше смешивают биты, особенно если ваши данные в основном состоят из небольших чисел.

Eamon Nerbonne 03.06.2014 17:38

@ jnm2, поэтому я бы выбрал большое число (скажем, порядка 2 ^ 16) и настроился на реализацию словаря .NET, который НЕ используется Dictionary <,>: linksource.microsoft.com/#mscorlib/system/collections/…

Eamon Nerbonne 03.06.2014 17:45

@ jnm2 Я столкнулся с этими двумя вопросами, продолжая изучать эту проблему: stackoverflow.com/questions/1835976/… и stackoverflow.com/questions/1145217/…, и оба пришли к выводу: используйте любое старое большое простое число. В принятом ответе на первый вопрос упоминаются два, выбранных принципиальным образом, но вряд ли этот принцип действительно относится к реальному миру, поэтому он все же рекомендует основную идею: выберите большое простое число, а НЕ 23 или 31.

Eamon Nerbonne 04.06.2014 19:48

Кстати: обратите внимание, что смещение (насколько я могу судить) совершенно бессмысленно. Распределительные законы также действуют по модулю, а это означает, что это просто идентичное смещение, которое будут разделять все объекты, - это, безусловно, не влияет на какую-либо хеш-таблицу, которую я знаю.

Eamon Nerbonne 04.06.2014 19:52

@EamonNerbonne: Думаю, это правда, если все объекты одного типа. Если у вас есть словарь, в котором некоторые ключи являются подклассами других ключей, это может иметь значение ... хотя в любом случае только тогда, когда значения дополнительных полей равны 0. Опять же, для меня это в основном привычка :(

Jon Skeet 04.06.2014 20:01

@JonSkeet Да, если у вас есть объекты разного типа и вы используете разные смещения, у вас будет некоторое преимущество. Хотя, думаю, нет причин быть первоклассным ... В любом случае, дополнение настолько дешево, что нет особых причин избегать его.

Eamon Nerbonne 04.06.2014 20:04

Я использовал этот алгоритм для псевдослучайного генератора, и он ведет себя немного странно: stackoverflow.com/questions/26847262/…

Max Yankov 10.11.2014 18:35

Если вы получили номер 486187739 от stackoverflow.com/a/2816747/21499 - я действительно намеревался рекомендовать 92821.

Hans-Peter Störr 01.04.2015 14:35

Поскольку каждый экземпляр класса «объект» имеет уникальный хэш-код, мне пришла в голову идея, что было бы хорошо, если бы мы использовали base.GetHashCode () в качестве начального числа или чего-то еще для создания нашего хэш-кода для объекта.

Ahmad Siavosh 05.08.2015 11:06

@AhmadSiavosh: Нет, это идея плохой, потому что вы хотите, чтобы разные, но равные объекты имели один и тот же хэш-код. (Я не думаю, что object.GetHashCode также гарантированно уникален. Вполне возможно, что "очень маловероятно столкновение", но это не одно и то же.)

Jon Skeet 05.08.2015 11:13

Если fieldL - это List<obj>, он будет работать, просто выполнив hash = ... ^ fieldL.GetHashCode(), или я должен пройти через такие пункты, как foreach(){hash = ... ^ item.GetHashCode()} ???

Jaider 12.02.2016 19:14

@Jaider: Это тоже не годится. List<T> не отменяет Equals или GetHashCode. #

Jon Skeet 12.02.2016 19:29

Я пробовал этот код для 3 дублей и получил огромное количество коллизий. Мне нужно получить хэш-коды для 4194304 кортежей. Есть ли способ лучше? Использование некоторых более крупных простых чисел немного помогло, но я все еще получаю коллизии.

dmarra 16.02.2016 03:58

@ user984444: Что ж, вы должны ожидать довольно много столкновений с таким количеством записей. Сколько вы получаете?

Jon Skeet 16.02.2016 09:07

@JonSkeet Трудно сказать. Я использую это для кэширования вывода некоторого шума Перлина, а индикатором столкновения является некоторый "интересный" вывод в моем изображении; Он выглядит как ... когда вы выигрываете пасьянс. Это смягчается (и шаблон меняется) с большими простыми числами. Я знаю, это бесполезно. Я изменил свою структуру (кортеж двойников в качестве ключа) на класс, чтобы сеть заботилась о хэш-коде за меня и больше не имела коллизий.

dmarra 16.02.2016 18:43

@ user984444: Гм, в этом случае одинаковые ключи не будут равными, если только вы не переопределите GetHashCode в своем классе, и в этом случае у вас такая же проблема. Может, стоит задать новый вопрос со всеми подробностями ...

Jon Skeet 16.02.2016 18:44

@JonSkeet: Неправда; реализация GetHashCode по умолчанию работает отлично (в противном случае это было бы невероятно очевидно в моем конечном результате). Он также работает для структуры, но работает НАЧАЛО МЕДЛЕННО. Я хотел использовать структуры, но использование класса, похоже, отлично подходит для моего варианта использования.

dmarra 16.02.2016 23:02

@ user984444: Если вы не переопределите GetHashCode и Equals самостоятельно или не унаследуете от другого класса, который это делает, вы получите ссылочное равенство. Это нет, что даст вам структура. Похоже, нам нужен новый пост с подробностями.

Jon Skeet 16.02.2016 23:43

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

dmarra 17.02.2016 05:04

будучи очень разборчивым, настройки StyleCop по умолчанию генерируют предупреждение для этого кода (SA1407), поскольку вы не использовали круглые скобки для определения приоритета арифметических операторов, даже если он понятен любому разработчику, читающему код, и компилятору, как мы все знаем правило БОДМЫ.

MikeW 30.03.2016 12:32

@MikeW: Я не думаю, что BODMAS включает XOR :) Я думаю, что заключительный фрагмент кода будет более понятным с круглыми скобками - добавлю их сейчас. Я согласен, что для версии с умножением и сложением они не нужны.

Jon Skeet 30.03.2016 12:34

Для будущих читателей: рассмотрите возможность использования HashCode.Combine()

RobIII 23.11.2017 23:45

@JonSkeet есть идеи, как это сделать в t-sql? Мне нужен хеш C# серии guid для соответствия хешу t-sql серии uniqueidentifier. но afaik в t-sql невозможно обернуть результаты целочисленной арифметики.

BaltoStar 02.03.2018 01:22

@BaltoStar: я ничего не знаю о хешировании в T-SQL. Если он уже обеспечивает четко определенное хеширование для значений GUID, я бы, вероятно, попытался имитировать это на C#, а не наоборот.

Jon Skeet 02.03.2018 09:57

@JonSkeet в C#, почему бы просто не хешировать MD5 для упорядоченной конкатенации идентификаторов GUID?

BaltoStar 02.03.2018 15:41

@JamesKo: Я добавлю ссылку на HashCode.Combine, когда .NET Core 2.1 действительно будет выпущен, и я могу ссылаться на документы. Не думаю, что до того времени многим он будет полезен.

Jon Skeet 16.03.2018 10:21

@JonSkeet Конечно.

James Ko 17.03.2018 01:07

Я не уверен, как здесь обрабатывать нули. Кажется, что ни один из ответов не затрагивает эту тему, если предположить, что все мы эксперты в этой теме. @JonSkeet В этих комментариях упоминается: «Я обычно использую 0 в качестве эффективного хэш-кода для null - это не то же самое, что игнорировать поле». Однако как это на самом деле реализовано, у меня есть вопросы. Похоже, вы говорите, что свойство null должно обнулить текущее значение хеш-функции, но это кажется странным поведением. Некоторым может быть очевидно, что делать, но я был бы признателен за пример, показывающий, как обрабатывать нули, или лучшее объяснение.

crush 07.05.2018 17:08

Прочитав несколько других вопросов и ответов по этой теме, я понял, что не очень хорошо понимаю, о чем говорит @JonSkeet. Я неправильно понял, что он говорит, что я должен заменить 0 как константу хеширования, когда свойство имеет значение null. Увидев пример здесь, я понимаю, что он просто заявлял, что я должен заменить 0 в качестве хэш-кода свойства, что сейчас кажется таким очевидным ... учитывая, что это именно то, что он сказал.

crush 07.05.2018 17:18

Действительно ли нужно использовать простые числа вроде 17 или 23, если хэш моего объекта зависит только от одного свойства int32? Могу я просто вернуть MyProperty.GetHashCode()?

stt106 14.05.2018 20:03

@ stt106: Для одного свойства я бы просто вернул хэш-код этого свойства, да.

Jon Skeet 14.05.2018 20:04

К вашему сведению, Visual Studio 2017 может генерировать GetHashCode() без ReSharper. docs.microsoft.com/en-us/visualstudio/ide/reference/…

cactuaroid 27.10.2018 16:59

Зачем умножать хеш на каждой строке? Почему: int hash = 17; hash = hash * 23 + ...? Почему бы просто не использовать продукт явно, как, например, hash = 391 + field1.GetHashCode();? Поскольку порядок операций в любом случае будет сначала выполнять умножение?

emery.noel 08.10.2019 16:06

@ emery.noel: Это не будет иметь никакого значения после первой строки (вам все равно нужно умножить, чтобы включить предыдущий хеш), и IMO имеет большое преимущество в том, чтобы сделать каждую строку согласованной.

Jon Skeet 08.10.2019 16:58

Важному моменту уделялось не так много внимания. Важно, чтобы возвращаемый хэш-код НЕ МЕНЯЛСЯ, если объект является изменяемым и объект изменяется. Это связано с тем, что хэш-код используется (например) для размещения объектов в словарях. Если изменяемый объект изменяется после вставки в словарь, то объект не найден, когда вы идете искать его. Приведенное выше должно кэшировать хэш при первом вычислении и всегда возвращать исходное значение. Иначе будут странные баги.

Tb. 08.04.2020 20:11

@Tb .: Или вы документируете это в соответствии с документами: «Если вы решите переопределить GetHashCode () для изменяемого ссылочного типа, в вашей документации должно быть четко указано, что пользователи вашего типа не должны изменять значения объекта, пока объект хранится в хеш-таблице ". Часто это бывает полезно, поскольку вы можете создать объект, но не изменять его впоследствии. Это не «до блеска», но может быть совершенно практичным.

Jon Skeet 08.04.2020 20:46

Ссылка на статью FNV битая, но я нашел ее в архиве: archive.vn/KJeJy

Jalal 19.02.2021 10:54

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

// Unique ID from database
private int _id;

...    
{
  return _id.GetHashCode();
}

Это означает, что если у вас есть объекты Person и Account, и у них обоих есть ID = 1, они будут иметь одинаковый хэш-код. А это не нормально.

pero 22.03.2010 18:28

На самом деле комментарий выше неверен. Всегда будет возможность коллизии хэш-кода (хеш-код определяет местонахождение только корзины, а не отдельного объекта). Таким образом, такая реализация - для хэш-кода, содержащего смешанные объекты - привела бы к множеству коллизий, что нежелательно, но было бы абсолютно нормально, если бы у вас когда-либо были объекты только одного типа в ваших хэш-таблицах. Кроме того, он не распределяется равномерно, однако базовая реализация на system.object тоже не работает, поэтому я бы не стал слишком беспокоиться об этом ...

piers7 29.03.2010 06:14

Хэш-код может быть просто идентификатором, поскольку идентификатор является целым числом. Нет необходимости вызывать GetHashCode для целого числа (это функция идентификации)

Darrel Lee 23.11.2012 23:18

@DarrelLee, но его _id может быть гидом. _id.GetHashCode - хорошая практика кодирования, поскольку цель ясна.

nawfal 14.04.2013 16:57

@DarrelLee, это не лучший вариант, потому что последовательные идентификаторы из базы данных не обеспечивают хорошего распределения

Trident D'Gao 29.06.2013 00:04

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

Jon Hanna 14.01.2014 22:29

У меня есть класс хеширования в библиотеке 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);
}

Я не оценивал его производительность, поэтому любые отзывы приветствуются.

Что ж, это вызовет бокс, если поля являются типами значений.

nightcoder 04.04.2010 19:39

«может быть улучшено позже путем перехвата OverflowException». Вся суть unchecked состоит в том, чтобы избежать исключений при переполнении, которое желательно для GetHashCode. Так что это не неправильно, если значение выходит за пределы int, и это совсем не повредит.

Tim Schmelter 24.02.2014 17:06

Одна из проблем этого алгоритма заключается в том, что любой массив, заполненный нулями, всегда будет возвращать 0, независимо от его длины.

Nathan Adams 17.04.2015 15:12

Этот вспомогательный метод также выделяет новый объект []

James Newton-King 20.07.2016 15:35

Как упоминает @NathanAdams, тот факт, что null полностью пропускается, может дать вам неожиданные результаты. Вместо того, чтобы пропускать их, вы должны просто использовать какое-то постоянное значение вместо input[i].GetHashCode(), когда input[i] равен нулю.

David Schwartz 28.10.2016 22:04

В большинстве случаев, когда Equals () сравнивает несколько полей, на самом деле не имеет значения, хеширует ваш GetHash () в одном поле или во многих. Вам просто нужно убедиться, что вычисление хэша действительно дешево (Нет распределения, пожалуйста) и быстро (Никаких тяжелых вычислений и, конечно, без подключений к базе данных) и обеспечивает хорошее распределение.

Подъем тяжестей должен быть частью метода Equals (); хэш должен быть очень дешевой операцией, чтобы можно было вызывать Equals () для как можно меньшего числа элементов.

И последний совет: Не полагайтесь на стабильность GetHashCode () при выполнении нескольких приложений.. Многие типы .Net не гарантируют, что их хэш-коды останутся неизменными после перезапуска, поэтому вам следует использовать значение GetHashCode () только для структур данных в памяти.

«В большинстве случаев, когда Equals () сравнивает несколько полей, на самом деле не имеет значения, хеширует ваш GetHash () в одном поле или во многих». Это опасный совет, потому что для объектов, которые отличаются только нехешированными полями, вы получите коллизии хешей. Если это происходит часто, производительность коллекций на основе хешей (HashMap, HashSet и т. д.) Будет снижаться (до O (n) в худшем случае).

sleske 15.04.2010 19:44

На самом деле это произошло в Java: в ранних версиях JDK String.hashCode () рассматривал только начало строки; это привело к проблемам с производительностью, если вы использовали строки в качестве ключей в HashMaps, которые различались только в конце (что является обычным, например, для URL-адресов). Поэтому алгоритм был изменен (я полагаю, в JDK 1.2 или 1.3).

sleske 15.04.2010 19:51

Если это одно поле «обеспечивает хорошее распределение» (последняя часть моего ответа), тогда одного поля достаточно .. Если это не обеспечивает хорошее распространение, тогда (и только тогда) вам понадобится другое вычисление. (Например, просто используйте другое поле, которое делает обеспечивает хорошее распределение, или используйте несколько полей)

Bert Huijben 16.04.2010 13:12

Я не думаю, что есть проблема с тем, что GetHashCode выполняет выделение памяти, при условии, что это происходит только при первом использовании (с последующими вызовами, просто возвращающими кешированный результат). Важно не то, что нужно делать все возможное, чтобы избежать столкновений, а то, что нужно избегать «системных» столкновений. Если у типа есть два поля intoldX и newX, которые часто отличаются на единицу, хеш-значение oldX^newX будет назначать 90% таких записей хеш-значений 1, 2, 4 или 8. Использование oldX+newX [непроверенная арифметика] может привести к большему количеству коллизий. ...

supercat 08.09.2013 01:02

... чем более сложная функция, но набор из 1 000 000 вещей, которые имеют 500 000 различных значений хеш-функции, будет очень хорошо, если каждое значение хеш-функции имеет две связанные вещи, и очень плохо, если одно значение хеш-функции имеет 500 001 вещь, а другие - по одной.

supercat 08.09.2013 01:04

Вот мой помощник по хэш-коду. Преимущество заключается в том, что он использует аргументы универсального типа и поэтому не вызывает бокса:

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>

nawfal 14.04.2013 16:43

Вы можете провести рефакторинг этих методов и ограничить основную логику одной функцией.

nawfal 14.04.2013 17:06

Между прочим, 31 - это сдвиг и вычитание на ЦП, что очень быстро.

Chui Tey 23.08.2013 03:14

Метод расширения в int - это неприятное загрязнение пространства имен - ответ ниже @ safak-gur прекрасно помогает решить эту проблему.

Eamon Nerbonne 01.06.2014 23:32

@nightcoder, вы можете использовать параметры.

ANeves thinks SE is evil 09.02.2015 16:54

@ChuiTey Это то, что есть у всех Простые числа Мерсенна.

Pharap 12.06.2015 06:11

не должна ли переменная hash начинаться с нуля? stackoverflow.com/a/113600/9638388

geekley 20.07.2018 21:11

Просто потому, что это круто, вы также можете сделать это с помощью однострочника: source?.Aggregate(0, (current, item) => unchecked(current * 31 + (item?.GetHashCode() ?? 0))) ?? 0;

KnorxThieus 09.03.2019 18:54

@ANeves Я предлагаю вам не использовать params, если он предназначен для более широкого использования (например, публичная библиотека). params включает распределение массива (плюс затраты O (n) на заполнение массива), что плохо для ситуаций, чувствительных к производительности. params object[] вдвойне плох теперь, когда вы вводите стоимость упаковки также для типов значений.

nawfal 06.05.2020 18:48

Это хороший:

/// <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 () не принимает никаких параметров, поэтому ему необходимо вызвать его с двумя ключами, которые нужно как-то определить. Извините, без дополнительных объяснений это только выглядит умно, но не так хорошо.

Michael Stum 07.10.2010 21:28

А зачем вам общие перегрузки? Тип не важен (и не используется в вашем коде), поскольку объекты все имеют метод GetHashCode(), поэтому вы всегда можете использовать метод с параметром массива params. Или мне что-то здесь не хватает?

gehho 08.10.2010 13:31

Речь идет о производительности, избегайте цикла для меньших <= 4 полей. Но я думаю, что дженерики можно пропустить и вместо этого просто использовать объект.

Magnus 08.10.2010 13:57

Когда вы используете объект вместо дженериков, вы получаете боксы и выделения памяти, которые вам не нужны в GetHashCode. Так что дженерики - это то, что нужно.

CodesInChaos 22.11.2010 01:26

Завершающие шаги shift / xor (h += (h << 10); h ^= (h >> 6); h += (h << 3); h ^= (h >> 11); h += (h << 15); имеют кодовый запах: они не зависят от какого-либо ввода и кажутся мне ужасно избыточными.

sehe 22.04.2011 23:54

@nawfal какие у вас соображения по скорости?

Magnus 24.12.2012 15:29

@Magnus ничего особенного, кроме общего правила, что хеширование должно быть быстрым. Это не может быть так быстро, как мне бы хотелось. Но, как я уже сказал, это дает лучшее распределение значений, которое может быть подходящим для некоторых случаев.

nawfal 25.12.2012 14:41

@nawfal Выполнение этого 100 миллионов раз занимает около 390 мс. Выполнение решения, предложенного Джоном Скитом, 100 миллионов раз занимает около 320 мс, так что это не большая разница.

Magnus 25.12.2012 14:59

@Magnus да ладно, я удалю свой исходный комментарий. Небольшое замечание, что это может быть не так быстро, как некоторые другие решения здесь, но, как вы говорите, не должно иметь значения. Распределение отличное, лучше, чем у большинства решений здесь, так что +1 от меня! :)

nawfal 25.12.2012 15:28

Как это соотносится по качеству (распределению) и производительности с простым использованием промежуточного звена long с умножением каждого ввода на большое число? Например. для двух значений, что-то вроде этого one liner: return ((long)v1 * 805306457 + (long)v2 * 189783887).GetHashCode(); [Простые числа выбраны, чтобы избежать числового переполнения long в проверяемой среде и иметь тенденцию устанавливать разные биты.]

ToolmakerSteve 01.03.2018 04:42

ValueTuple - обновление для C# 7

Как @cactuaroid упоминает в комментариях, можно использовать кортеж значений. Это экономит несколько нажатий клавиш и, что более важно, выполняется исключительно в стеке (без мусора):

(PropA, PropB, PropC, PropD).GetHashCode();

(Примечание: оригинальный метод с использованием анонимных типов, похоже, создает объект в куче, то есть мусор, поскольку анонимные типы реализованы как классы, хотя это может быть оптимизировано компилятором. Было бы интересно протестировать эти параметры, но вариант кортежа должен быть выше.)

Анонимный тип (оригинальный ответ)

Microsoft уже предоставляет хороший общий генератор HashCode: просто скопируйте значения свойств / полей в анонимный тип и хешируйте его:

new { PropA, PropB, PropC, PropD }.GetHashCode();

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

Да, анонимная реализация GetHashCode очень эффективна (кстати, она такая же, как в ответе Джона Скита), но единственная проблема с этим решением заключается в том, что вы генерируете новый экземпляр при любом вызове GetHashCode. Это может быть немного накладным, особенно в случае интенсивного доступа к большим хешированным коллекциям ...

digEmAll 08.01.2011 12:50

Это работает в VB с .NET 4.0, но, просматривая IL, он использует вызовы box, поскольку тип использует обобщенные типы. Распаковки нет, но из того, что я здесь читаю, простое присутствие бокса предполагает, что это может быть немного неэффективно. Кажется, это единственный выбор для VB, поскольку эквивалента checked / `unchecked 'нет.

Kumba 11.01.2011 12:37

@digEmAll Хороший момент, я не думал о накладных расходах на создание нового объекта. Ответ Джона Скита наиболее эффективен и не использует бокс. (@Kumba Чтобы решить непроверенный в VB, просто используйте Int64 (длинный) и усеките его после вычислений.)

Rick Love 02.04.2011 21:30

В VB.Net: New With {PropA, PropB, PropC, PropD}.GetHashCode()

mwolfe02 16.04.2013 19:40

VB.NET должен использовать ключ при создании анонимного типа: New With {Key PropA}.GetHashCode() В противном случае GetHashCode не вернет один и тот же хэш-код для разных объектов с одинаковыми «идентифицирующими» свойствами.

David Osborne 20.08.2014 19:58

Не забудьте перечислить свои IEnumerables, иначе случится что-то плохое. new { PropA, PropB, C = PropC.ToList() }.GetHashCode()

Keith 19.10.2015 23:16

@Keith в этом случае я бы подумал о сохранении IEnumerable в качестве значения списка вместо того, чтобы перечислять его каждый раз при вычислении хэш-кода. Caclating ToList каждый раз внутри GetHashCode может снизить производительность во многих ситуациях.

Rick Love 20.10.2015 23:40

И не забывайте, что приватное свойство / поля в этом случае не нужны;).

shA.t 29.08.2017 11:22

@Keith: свойства все объекта не должны влиять на хэш-код. Хэш-код просто должен дать достаточно хорошо распределение ваших объектов. И для вычисления должно быть быстрый. Оставьте перечислимое. И если у вас есть список, не включайте весь список. Используйте Count и, возможно, первый элемент (используйте ноль, если элементов нет). если у вашего класса нет других вариантов, кроме списка; в этом случае, как предлагает Рик, лучше всего кэшировать хэш списка. Напомним, что по определению хэш объекта всегда должен быть одинаковым. Если коллекция изменяется, НЕ включайте ее в hash calc.

ToolmakerSteve 01.03.2018 07:15

Для тех, кому это нравится, (PropA, PropB, PropC, PropD).GetHashCode() теперь доступен на C# 7 без проблем с давлением сборщика мусора @digEmAll. Быстрые и простые комбинации хеш-кодов

cactuaroid 16.08.2018 14:59

@cactuaroid Отлично! Итак, используя кортеж (который является структурой) вместо анонимного типа (класса). Использует ли он тот же расчет за кулисами для Tuple GetHashcode ()?

Rick Love 16.08.2018 16:55

@RickLove Я не уверен в математике. Tuple.GetHashCode () и ValueTuple.GetHashCode () выглядят одинаково. ValueTuple.GetHashCode () вызывает HashHelper. Tuple.GetHashCode () вызывает Tuple.CombineHashCodes. Для анонимного типа Как Equals и GetHashCode реализованы для анонимных типов?

cactuaroid 16.08.2018 18:03

@cactuaroid: действительно, это отличное решение!

digEmAll 16.08.2018 19:43

Прошу прощения, что @Timo уже писал о ValueTuple.GetHashCode () ниже.

cactuaroid 17.08.2018 17:08

Вот мой упрощенный подход. Для этого я использую классический шаблон строителя. Он безопасен по типу (без упаковки / распаковки), а также совместим с .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)).

nawfal 14.04.2013 16:52

И какую пользу вы получаете от this.result * Prime2 * item.GetHashCode(), когда часто используется this.result * Prime2 + item.GetHashCode()?

nawfal 14.04.2013 16:54

Я не могу использовать AddItems<T>(params T[] items) чаще, потому что typeof(T1) != typeof(T2) и т. д.

bitbonk 15.04.2013 10:25

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.

Вы можете преобразовать несколько значений в хешированное значение, и некоторые из них будут одинаковыми, поэтому не используйте его в качестве идентификатора. (может быть, когда-нибудь я воспользуюсь вашим компонентом)

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

Jon Hanna 14.01.2014 13:36

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

deadManN 16.09.2015 08:59

Да, но ваши второй и пятый не пытаются избежать столкновений.

Jon Hanna 16.09.2015 11:44

Не уверен, что это за поток ... но он сделал то же самое, msdn.microsoft.com/en-us/library/…

deadManN 19.09.2015 15:37

Да, этот антипаттерн довольно распространен.

Jon Hanna 19.09.2015 17:06

вот почему я полагаюсь на это, но спасибо за облегчение ... другое дело в том, что у другого шаблона меньше времени на расчет? ну знаешь, вроде, материя collision vs calculation time тоже есть

deadManN 20.09.2015 16:34

Необходимо достичь баланса. Используйте действительно хороший хэш-код, такой как Spookyhash, и вы получите намного, намного лучшее предотвращение столкновений, но у него будет гораздо больше времени на вычисление, чем у любого из них (но когда дело доходит до хеширования очень больших объемов данных, Spookyhash очень быстр). Простой сдвиг одного из значений перед xoring - это лишь незначительные дополнительные затраты для хорошего снижения коллизии. Умножение простых чисел снова увеличивает время и качество. Следовательно, вопрос о том, что лучше между shift или mult, спорный. Обычный xor, хотя очень часто имеет много конфликтов с реальными данными, и его лучше избегать

Jon Hanna 20.09.2015 19:57

Вот мой вспомогательный класс, использующий Реализация Джона Скита.

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();

Bill Barry 05.09.2014 21:12

Я считаю, что тернарный оператор с obj != null будет компилироваться в инструкцию box, которая будет выделять память, если T является типом значения. Вместо этого вы можете использовать obj.Equals(null), который будет компилироваться в виртуальный вызов метода Equals.

Martin Liversage 14.09.2014 03:00

Поскольку this.hashCode != h. Это не вернет то же значение.

Şafak Gür 15.06.2015 11:01

Извините, мне удалось удалить мой комментарий вместо его редактирования. Более выгодно создать новую структуру, а затем изменить hashCode на non-readonly и сделать: «unchecked {this.hashCode ^ = h * 397;} return this;» Например?

Erik Karlsson 15.06.2015 11:28

Неизменяемость имеет свои преимущества (Почему изменчивые структуры - зло?). Что касается производительности, то, что я делаю, довольно дешево, поскольку оно не выделяет места в куче.

Şafak Gür 15.06.2015 13:35

Нет бокса, если вы называете его как Hash (1), а не как Hash <MyInterface> (myStruct). stackoverflow.com/questions/8823239

user764754 11.04.2016 21:12

Вот еще одна свободная реализация алгоритм, опубликованный выше Джоном Скитом, но которая не включает выделения или операции упаковки:

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 могут здесь переполниться.

Mark Hurd 30.09.2014 08:28

Очень похоже на решение 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;
        }
    }
}

Не обрабатывает нули.

JJS 27.12.2016 20:09

Пользователи 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 будет поставляться?

Dan J 14.12.2017 03:37

@DanJ Какое счастливое совпадение, изменения HashCode для corefx были объединены всего за пару часов до вашего комментария :) Этот тип планируется выпустить в .NET Core 2.1.

James Ko 14.12.2017 03:41

Это потрясающе - и довольно много времени на обработку. Проголосовали. :)

Dan J 14.12.2017 03:48

@DanJ Еще лучшие новости - он должен быть доступен прямо сейчас в ночных сборках CoreFX, размещенных в ленте MyGet ядра dotnet.

James Ko 16.12.2017 02:44

Милый - это не помогает мне в работе, так как мы не совсем передовые который, но это полезно знать. Ваше здоровье!

Dan J 18.12.2017 01:18

Вот вставляемый пакет polyfill, который можно использовать для всего .NET 4.0+ (включая System.HashCode): nuget.org/packages/Gapotchenko.FX

ogggre 30.03.2019 15:49

Если у нас не более 8 объектов (надеюсь), есть еще одна альтернатива.

ValueTuple - это структура, которая, похоже, имеет надежную реализацию GetHashCode.

Это означает, что мы могли бы просто сделать это:

// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();

Давайте посмотрим на текущую реализацию .NET Core для ValueTupleGetHashCode.

Это из ValueTuple:

    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);
    }

А это от HashHelper:

    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;
        }
    }

На английском:

  • Поворот влево (круговое смещение) h1 на 5 позиций.
  • Сложите результат и h1 вместе.
  • Выполните XOR результата с помощью h2.
  • Начните с выполнения вышеуказанной операции над {static random seed, h1}.
  • Для каждого следующего элемента выполните операцию с предыдущим результатом и следующим элементом (например, h2).

Было бы неплохо узнать больше о свойствах этого алгоритма хэш-кода ROL-5.

К сожалению, переход на ValueTuple для нашего собственного GetHashCode может оказаться не таким быстрым, как нам хотелось бы и ожидать. Этот комментарий в соответствующем обсуждении показывает, что прямой вызов HashHelpers.Combine более эффективен. С другой стороны, этот внутренний, поэтому нам пришлось бы скопировать код, пожертвовав многим из того, что мы здесь получили. Кроме того, мы будем нести ответственность за запоминание первого Combine со случайным семенем. Я не знаю, каковы будут последствия, если мы пропустим этот шаг.

Предполагая, что h1 >> 27 равен 0, чтобы игнорировать его, h1 << 5 равен h1 * 32, поэтому он такой же, как h1 * 33 ^ h2. Согласно эта страница, он называется «Модифицированный Бернштейн».

cactuaroid 17.08.2018 17:28

Это статический вспомогательный класс, реализующий реализацию Джоша Блоха; и предоставляет явные перегрузки для «предотвращения» упаковки, а также для реализации хеширования специально для длинных примитивов.

Вы можете передать сравнение строк, которое соответствует вашей реализации 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.

Steven Coco 09.05.2019 03:14

.NET Standard 2.1 и выше

Если вы используете .NET Standard 2.1 или выше, вы можете использовать структуру System.HashCode. Есть два способа его использования:

HashCode.Combine

Метод Combine можно использовать для создания хэш-кода, содержащего до восьми объектов.

public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);

HashCode.Add

Метод 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 - это просто

Вы можете прочитать полную запись в блоге «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 на двух разных объектах производят идентичные хэш-коды. Обратите внимание, что столкновения разрешены (некоторые ошибочно полагают, что это не так), но их следует свести к минимуму.

Хорошая хеш-функция должна отображать ожидаемые входные данные как можно более равномерно по выходному диапазону. Он должен иметь единообразие.

Предотвратить DoS

В .NET Core каждый раз, когда вы перезапускаете приложение, вы будете получать разные хэш-коды. Это функция безопасности для предотвращения атак типа «отказ в обслуживании» (DoS). Для .NET Framework вы должен активируете эту функцию, добавив следующий файл App.config:

<?xml version  = "1.0"?>  
<configuration>  
   <runtime>  
      <UseRandomizedStringHashAlgorithm enabled = "1" />  
   </runtime>  
</configuration>

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

Подробнее об этом здесь.

Криптографически безопасный?

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

  • Невозможно сгенерировать сообщение, которое дает заданное значение хеш-функции.
  • Невозможно найти два разных сообщения с одинаковым значением хеш-функции.
  • Небольшое изменение в сообщении должно настолько сильно изменить хеш-значение, что новое хеш-значение будет казаться некоррелированным со старым хеш-значением (эффект лавины).

Это очень хороший ответ. В качестве дополнения вы можете рассмотреть возможность изменения «скорости» на «производительность» и добавления свойства отсутствия выделения памяти. Встроенный тип HashCode этому тоже удовлетворяет.

Timo 10.07.2020 18:22

Как это соотносится с ответом ValueTuple.GetHashCode(), недавно обновленным @ricklove выше?

Thiago Silva 18.02.2021 06:10

HashCode.Combine - это статический метод, который ничего не выделяет, в то время как ValueTuple начинает с выделения в стеке.

Muhammad Rehan Saeed 18.02.2021 11:35
HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers) - красивый синтаксис :)
Amos Egel 09.03.2021 11:14

Если вы хотите полифилить 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;
        }

Другие вопросы по теме