Недостаток C# с Double.GetHashCode ()
Битовый формат для чисел типа double хранит знак в первом бите. Алгоритм хеширования C# для double - это двоичный xor для верхних и нижних 32 бит.
Таким образом, когда вы хешируете двойное A и его отрицательное значение -A, единственная разница в хэшах заключается в первом бите.
Для хеширования нескольких полей в большинстве ссылок предлагается использовать что-то вроде этого:
public override int GetHashCode()
{
unchecked
{
int hash = 17;
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
return hash;
}
}
Наконец, рассмотрим два объекта с двумя двойниками каждый, например:
Объект1: {A, -B} Объект2: {-A, B}
Для любых двух удвоений A и B эти два объекта, кажется, всегда хешируют одно и то же значение (используя метод выше, независимо от начального числа и множителя). Обоснование, грубо говоря, состоит в том, что энтропия хранится в самом старшем бите, и этот бит переполняется, теряя важную информацию.
Я хочу использовать другой хеш для двойников с аналогичной производительностью, но с превосходной энтропией. Какие-либо предложения?
Edit: Пожалуйста, не пишите / не комментируйте неизбежность столкновений.
Вы часто сравниваете наборы двойников, у которых есть наборы, которые равны, за исключением того факта, что один является обратным другому? Коллизий никогда нельзя избежать полностью, вы можете только попытаться избежать шаблонов которые на самом деле находятся в данных, которые вы хешируете.
@juharr Знаки различаются не только значениями, но и парами, которые являются обратным знаком для других пар. При рассмотрении пары, имеющей только одно значение с другим знаком, столкновения не кажутся обычными.
Ответы 2
Вы только что указали, почему простой XOR не лучший способ комбинировать хэши.
Для справки, вот как System.Tuple<T1,T2> объединяет 2 хэша:
// From System.Web.Util.HashCodeCombiner
internal static int CombineHashCodes(int h1, int h2)
{
return (((h1 << 5) + h1) ^ h2);
}
https://referencesource.microsoft.com/#mscorlib/system/tuple.cs,1806cf6634f5a371
Заменить реализацию GetHashCode () для типов компонентов действительно сложно, но вы можете ввести дополнительный термин после объединения хэшей.
Например, XOR в конкатенации знаковых битов компонентов, чтобы гарантировать, что Hash (d, -d)! = Hash (-d, d).
internal static int GetSign(double d)
{
return d >= 0 ? 1 : 0;
}
public override int GetHashCode()
{
var signs = GetSign(d2) << 1 | GetSign(d1);
var h = CombineHashCodes(d1.GetHashCode(), d2.GetHashCode());
return h ^ signs;
}
Это не делает проблему лучше. Если мы определим наш собственный двойной хешер как public static int MyHash(double d) { if (d == 0) return 0; long w = BitConverter.DoubleToInt64Bits(d); return CombineHashCodes((int)w, (int)(w>>32)); } public static int MyHash(double x, double y) { return CombineHashCodes(MyHash(x), MyHash(y)); }, то у нас все равно останется свойство MyHash(x, -y) == MyHash(-x, y)!
Код OP не XOR объединяет хеши. Они умножают каждый хеш на 23, а затем складывают их, не учитывая переполнения. Это отличается, довольно похоже на то, почему ваш код отличается от прямого XOR (он смещает один из них перед добавлением битов), что объясняет, почему у этого есть такая же проблема, как упоминает Эрик.
Если я изменю левый сдвиг на правый, этот ответ решит мою проблему. Я пометил это как принятый ответ. Спасибо, Дэвид!
Для ясности: это решение не является новым методом хеширования для double, но оно решает мою проблему с использованием встроенного double.GetHashCode ().
Вы можете использовать хеширование через long. Замените int hash на long hash, например:
public override int GetHashCode()
{
unchecked
{
long hash = 17;
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
return hash.GetHashCode();
}
}
Теперь вы устранили проблему переполнения. И из теста, который я сделал (на одной паре double :-)), ваша проблема.
Ожидаете ли вы, что у вас будет много значений, которые различаются только знаком? Потому что независимо от того, что вы делаете, у вас будут разные значения, которые дают один и тот же хеш.