为什么HashSets的可空值的结构非常慢？

我调查了性能下降，并追踪到减缓HashSets。
我有可用作主键的可空值的结构。 例如：

public struct NullableLongWrapper { private readonly long? _value; public NullableLongWrapper(long? value) { _value = value; } } 

我注意到创build一个HashSet<NullableLongWrapper>非常慢。

下面是一个使用BenchmarkDotNet的例子：（ Install-Package BenchmarkDotNet ）

 using System.Collections.Generic; using System.Linq; using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Configs; using BenchmarkDotNet.Jobs; using BenchmarkDotNet.Running; public class Program { static void Main() { BenchmarkRunner.Run<HashSets>(); } } public class Config : ManualConfig { public Config() { Add(Job.Dry.WithWarmupCount(1).WithLaunchCount(3).WithTargetCount(20)); } } public struct NullableLongWrapper { private readonly long? _value; public NullableLongWrapper(long? value) { _value = value; } public long? Value => _value; } public struct LongWrapper { private readonly long _value; public LongWrapper(long value) { _value = value; } public long Value => _value; } [Config(typeof (Config))] public class HashSets { private const int ListSize = 1000; private readonly List<long?> _nullables; private readonly List<long> _longs; private readonly List<NullableLongWrapper> _nullableWrappers; private readonly List<LongWrapper> _wrappers; public HashSets() { _nullables = Enumerable.Range(1, ListSize).Select(i => (long?) i).ToList(); _longs = Enumerable.Range(1, ListSize).Select(i => (long) i).ToList(); _nullableWrappers = Enumerable.Range(1, ListSize).Select(i => new NullableLongWrapper(i)).ToList(); _wrappers = Enumerable.Range(1, ListSize).Select(i => new LongWrapper(i)).ToList(); } [Benchmark] public void Longs() => new HashSet<long>(_longs); [Benchmark] public void NullableLongs() => new HashSet<long?>(_nullables); [Benchmark(Baseline = true)] public void Wrappers() => new HashSet<LongWrapper>(_wrappers); [Benchmark] public void NullableWrappers() => new HashSet<NullableLongWrapper>(_nullableWrappers); } 

结果：

           方法| 中值| 缩放
 ----------------- | ---------------- | ---------
             Longs |  22.8682 us |  0.42
     NullableLongs |  39.0337 us |  0.62
         包装|  62.8877 us |  1.00
  NullableWrappers |  231,993.7278我们|  3,540.34

使用带有Nullable<long>的结构与long结构相比，速度要慢3540倍！
在我的情况下，它是800毫秒和<1毫秒之间的区别。

以下是来自BenchmarkDotNet的环境信息：

OS = Microsoft Windows NT 6.1.7601 Service Pack 1
处理器= Intel（R）Core TM i7-5600U CPU 2.60GHz，ProcessorCount = 4
频率= 2536269滴答，分辨率= 394.2799纳秒，计时器= TSC
CLR = MS.NET 4.0.30319.42000，Arch = 64位RELEASE [RyuJIT]
GC =并发工作站
JitModules = clrjit-v4.6.1076.0

性能这个差是什么原因？

Answer 1

发生这种情况的原因是_nullableWrappers每个元素都有相同的由GetHashCode()返回的散列码，导致哈希退化为O（N）访问而不是O（1）。

你可以通过打印出所有的哈希码来validation。

如果你修改你的结构如下：

 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的哈希码是相同的。

在这个线程中讨论了这个问题的答案。 然而，这并不能回答这个问题，因为Hans的答案围绕着有两个字段的结构来计算哈希代码，但是在这个代码中只有一个字段可供select，而且是一个值types（一个struct ）。

然而，这个故事的寓意是： 永远不要依赖于值types的默认GetHashCode() ！

---

附录

我想也许发生了什么事情是与汉斯的回答在我链接的线程 – 也许它是在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的东西正在幕后发生，但这是猜测。）

顺便说一下，这种行为，其中可以显示两个字段贡献散列码certificateValueType.GetHashType()的参考源中的注释是不准确的或错误的：

行动：我们的algorithm返回哈希码有点复杂。 我们查找第一个非静态字段并获取它的哈希码。 如果types没有非静态字段，我们返回types的哈希码。 我们不能采用静态成员的哈希码，因为如果该成员与原始types的types相同，我们将以无限循环结束。

如果这个评论是真的，那么上面例子中的五个哈希码中的四个将是相同的，因为对于所有那些， A具有相同的值0。 （假设A是第一个字段，但是如果交换值则会得到相同的结果：这两个字段对哈希码都有明确的贡献。）

然后我试着改变第一个领域是一个布尔：

 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 

哇！ 因此，使第一个字段成为布尔值，使得所有的哈希代码都是相同的，而不pipe任何字段的值是多less！

这对我来说仍然是一种错误。

该错误已在.NET 4中修复，但只适用于Nullable。 自定义types仍然会产生不良的行为。 资源

Answer 2

这是由于GetHashCode（）结构的行为。 如果它find引用types – 它会尝试从第一个非引用types字段获取散列。 在你的情况下，它发现，Nullable <>也是结构，所以它只是把它的私有布尔值（4字节）