Ответ 1
Это происходит потому, что каждый из элементов _nullableWrappers имеет тот же хэш-код, который возвращается GetHashCode(), что приводит к тому, что хеширование вырождается в O (N), а не O (1).
Вы можете проверить это, распечатав все хэш-коды.
Если вы измените свою структуру следующим образом:
public struct NullableLongWrapper
{
private readonly long? _value;
public NullableLongWrapper(long? value)
{
_value = value;
}
public override int GetHashCode()
{
return _value.GetHashCode();
}
public long? Value => _value;
}
он работает намного быстрее.
Теперь очевидным вопросом является WHY - это хэш-код для всех NullableLongWrapper.
Ответ на этот вопрос обсуждается в этом разделе. Тем не менее, он не совсем отвечает на вопрос, так как ответ Ганса вращается вокруг структуры, имеющей TWO-поля, из которых следует выбирать при вычислении хеш-кода, - но в этом коде есть только одно поле для выбора - и это тип значения (a struct).
Однако мораль этой истории: Никогда не полагайтесь на значения по умолчанию GetHashCode() для типов значений!
Добавление
Я думал, что, возможно, то, что происходило, было связано с ответом Ганса в связанной с ним нитью - возможно, это принимало значение первого поля (bool) в структуре Nullable<T>), и мои эксперименты показывают, что это могут быть связаны - но это осложнилось:
Рассмотрим этот код и его вывод:
using System;
public class Program
{
static void Main()
{
var a = new Test {A = 0, B = 0};
var b = new Test {A = 1, B = 0};
var c = new Test {A = 0, B = 1};
var d = new Test {A = 0, B = 2};
var e = new Test {A = 0, B = 3};
Console.WriteLine(a.GetHashCode());
Console.WriteLine(b.GetHashCode());
Console.WriteLine(c.GetHashCode());
Console.WriteLine(d.GetHashCode());
Console.WriteLine(e.GetHashCode());
}
}
public struct Test
{
public int A;
public int B;
}
Output:
346948956
346948957
346948957
346948958
346948959
Обратите внимание, что второй и третий хеш-коды (для 1/0 и 0/1) одинаковы, но все остальные. Я нахожу это странным, потому что, очевидно, изменение A меняет хэш-код, как и изменение B, но, учитывая два значения X и Y, тот же хэш-код генерируется для A = X, B = Y и A = Y, B = X.
(Похоже, что некоторые вещи XOR происходят за кулисами, но это догадывается.)
Кстати, такое поведение, при котором поля BOTH могут отображаться в качестве хеш-кода, доказывает, что комментарий в исходном источнике для ValueType.GetHashType() является неточным или неправильным:
Действие: Наш алгоритм для возврата хэш-кода немного сложнее. Мы ищем первое нестатическое поле и получаем его hashcode. Если тип не имеет нестатических полей, мы возвращаем хэш-код типа. Мы не можем взять хэш-код статического члена, потому что если этот элемент имеет тот же тип, что и исходный тип, мы закончим бесконечный цикл.
Если этот комментарий был правдой, то четыре из пяти хеш-кодов в приведенном выше примере были бы одинаковыми, так как A имеет одинаковое значение, 0, для всех этих. (Предполагает, что A является первым полем, но вы получаете те же результаты, если вы меняете значения вокруг: оба поля явно способствуют хеш-коду.)
Затем я попытался изменить первое поле как bool:
using System;
public class Program
{
static void Main()
{
var a = new Test {A = false, B = 0};
var b = new Test {A = true, B = 0};
var c = new Test {A = false, B = 1};
var d = new Test {A = false, B = 2};
var e = new Test {A = false, B = 3};
Console.WriteLine(a.GetHashCode());
Console.WriteLine(b.GetHashCode());
Console.WriteLine(c.GetHashCode());
Console.WriteLine(d.GetHashCode());
Console.WriteLine(e.GetHashCode());
}
}
public struct Test
{
public bool A;
public int B;
}
Output
346948956
346948956
346948956
346948956
346948956
Ничего себе! Поэтому, делая первое поле bool, все хэш-коды выходят одинаково независимо от значений любого из полей!
Это все еще выглядит для меня некоторой ошибкой.
Ошибка была исправлена в .NET 4, но только для Nullable. Пользовательские типы по-прежнему приводят к плохому поведению. источник