数组还是HashSet？
我记得大约在半年前，有个伴侣问我一个问题，如今有一个选型：
一个性能敏感场景，有一个集合，需要确定某一个元素在不在那个集合中，我是用数组间接 Contains 仍是利用 HashSet<T>.Contains ？
各人必定想都不消想，都选利用 HashSet<T> ，究竟结果 HashSet<T> 的时间复杂度是O(1)，但是后面又附加了一个前提：
那个集合的元素很少，就4-5个。
那那时候就有一些摆荡了，只要4-5个元素，是不是用数组 Contains 或者间接遍历会不会更快一些？其时我也觉得可能元素很少，用数组就够了。
而比来在编写代码时，又碰到了同样的场景，我决定来做一下尝试，看看元素很少的情况下，是不是利用数组优于 HashSet<T> 。
测试
我构建了一个测试，别离测验考试在差别的容量下，查找一个元素，利用数组和HashSet的区别，代码如下所示：
[ GcForce(true)]
[ MemoryDiagnoser]
[ Orderer(SummaryOrderPolicy.FastestToSlowest)]
publicclassBenchHashSet
privateHashSet< string> _hashSet;
privatestring[] _strings;
[ Params(1,2,4,64,512,1024)]
publicintSize { get; set; }
[ GlobalSetup]
publicvoidSetup( )
_strings = Enumerable.Range( 0, Size).Select(s => s.ToString).ToArray;
_hashSet = newHashSet< string>(_strings);
[ Benchmark(Baseline = true)]
publicboolEnumerableContains( ) => _strings.Contains( "8192");
[ Benchmark]
publicboolHashSetContains( ) => _hashSet.Contains( "8192");
各人猜猜成果怎么样，就算Size只为1，那么HashSet也比数组 Contains 遍历快40%。
那么故事就那么完毕了吗？所以无论若何场景我们都间接无脑利用HashSet就行了吗？各人看滑动条就晓得，故事没有那么简单。
刚刚我们是引用类型的比力，那值类型怎么样？结论就是一样的成果，就算只要1个元素也比数组的Contains快。
那么问题出在哪里？点进去看一下数组 Contains 办法的实现就清晰了，那个工具利用的是 Enumerable 迭代器婚配。
那么我们间接来个原始的， Array.IndexOf 婚配和 for 轮回婚配尝尝，于是有了如下代码：
[ GcForce(true)]
[ MemoryDiagnoser]
[ Orderer(SummaryOrderPolicy.FastestToSlowest)]
publicclassBenchHashSetValueType
privateHashSet< int> _hashSet;
privateint[] _arrays;
[ Params(1,4,16,32,64)]
publicintSize { get; set; }
[ GlobalSetup]
publicvoidSetup( )
_arrays = Enumerable.Range( 0, Size).ToArray;
_hashSet = newHashSet< int>(_arrays);
[ Benchmark(Baseline = true)]
publicboolEnumerableContains( ) => _arrays.Contains( 42);
[ Benchmark]
publicboolArrayContains( ) => Array.IndexOf(_arrays, 42) > -1;
[ Benchmark]
publicboolForContains( )
for( inti = 0; i < _arrays.Length; i++)
if(_arrays[i] == 42) returntrue;
returnfalse;
[ Benchmark]
publicboolHashSetContains( ) => _hashSet.Contains( 42);
接下来成果就和我们料想的差不多了，在数组元素小的时候，利用原始的 for 轮回比力会快，然后HashSet就变成最快的了，在更多元素的场景中Array.IndexOf会比for更快：
至于为什么在元素多的情况 Array.IndexOf 会比 for 更快，那是因为 Array.IndexOf 底层利用了SIMD来优化，在之前的文章中，我们屡次提到了SIMD，那里就不赘述了。
既然如斯我们再来确认一下，到底几个元素以内用for会更快，能够看到16个元素以内，for轮回会快于HashSet：
总结
所以我们应该选择 HashSet<T> 仍是数组呢？那个就需要分情况简单的总结一下：
在小于16个元素场景，利用 for 轮回婚配会比力快。
16-32个元素的场景，速度最快是 HashSet<T> 然后是 Array.IndexOf 、 for 、 IEnumerable.Contains 。
大于32个元素的场景，速度最快是 HashSet<T> 然后是 Array.IndexOf 、 IEnumerable.Contains 、 for 。
从那个上面来看，大于32个元素就不适宜间接用 for 比力了。不外那些不同都很小，除非是性能十分敏感的场景，能够忽略不计，本文处理了笔者的一些困扰，简单记录一下。
Tags：