Почему хэш-наборы структур с нулевыми значениями невероятно медленные?

это происходит потому, что каждый из элементов _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;
}

он работает гораздо быстрее.

теперь очевидный вопрос: почему хэш-код каждого NullableLongWrapper то же самое.

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

кстати, это поведение, когда оба поля могут быть показаны, чтобы внести свой вклад в хэш-код доказывает, что комментарий в справочном источнике для ValueType.GetHashType() is неточно или неправильно:

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

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