Будет ли эта хеш-функция сталкиваться необычно часто?

Question

У меня был следующий код для генерации хэша объекта:

public int GetHashCode(MyType obj)
{
   return (obj.Prop1.GetHashCode() + obj.Prop2.GetHashCode() + obj.Prop3.GetHashCode()).GetHashCode();
}

Т.е. я добавляю хэш-коды всех свойств, а затем принимаю хэш этого.

В обзореКоллега предположил, что это будет сталкиваться слишком часто.Я не уверен, что это правда, потому что:

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

Кто прав?

Это в C #, если ответ зависит от языка.

Answer 1

Да.

Предположим, что Prop1, Prop2 и т. Д. Имеют тип int.Обычно используется только нижний диапазон целых чисел.Ваш подход с суммой будет сталкиваться чаще, чем необходимо.

HasCode 7 равен 7, что имеет смысл при хешировании int самостоятельно.Но с вашим кодом все кортежи <7, 3>, <3, 7> и <8, 2> будут иметь одинаковый хэш.То же самое с простым XOR вместо сложения.

Обычный подход заключается в добавлении некоторых (простых) чисел и сдвига:

public int GetHashCode(MyType obj)
{
  int hash = 0;
  unchecked
  {         
     hash += 19 * obj.Prop1.GetHashCode();
     hash += 31 * obj.Prop2.GetHashCode();
     hash += 37 * obj.Prop3.GetHashCode();
  }
  return hash;
}

Числа 19, 31, 37 не слишком критичны.И если вы предпочитаете, вы можете использовать ИЛИ или XOR вместо +.

Answer 2

XORing будет лучше:

public int GetHashCode(MyType obj)
{
   return obj.Prop1.GetHashCode() ^ 
          obj.Prop2.GetHashCode() ^ 
          obj.Prop3.GetHashCode();
}

Answer 3

Вы можете использовать модифицированный генератор FNV HashCode, на очень похожий вопрос я ответил (100) здесь