陣列還是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)]
public class BenchHashSet
{
	private HashSet<string> _hashSet;
	private string[] _strings;

	[Params(1,2,4,64,512,1024)]
	public int Size { get; set; }

	[GlobalSetup]
	public void Setup()
	{
		_strings = Enumerable.Range(0, Size).Select(s => s.ToString()).ToArray();
		_hashSet = new HashSet<string>(_strings);
	}

	[Benchmark(Baseline = true)]
	public bool EnumerableContains() => _strings.Contains("8192");

	[Benchmark]
	public bool HashSetContains() => _hashSet.Contains("8192");
}

大家猜猜結果怎麼樣，就算Size只為1，那麼HashSet也比陣列Contains遍歷快40%。

那麼故事就這麼結束了嗎？所以無論如何場景我們都直接無腦使用HashSet就行了嗎？大家看滑動條就知道，故事沒有這麼簡單。

剛剛我們是參照型別的比較，那值型別怎麼樣？結論就是一樣的結果，就算只有1個元素也比陣列的Contains快。

那麼問題出在哪裡？點進去看一下陣列Contains方法的實現就清楚了，這個東西使用的是Enumerable迭代器匹配。

那麼我們直接來個原始的，Array.IndexOf匹配和for迴圈匹配試試，於是有了如下程式碼：

[GcForce(true)]
[MemoryDiagnoser]
[Orderer(SummaryOrderPolicy.FastestToSlowest)]
public class BenchHashSetValueType
{
	private HashSet<int> _hashSet;
	private int[] _arrays;

	[Params(1,4,16,32,64)]
	public int Size { get; set; }
	

	[GlobalSetup]
	public void Setup()
	{
		_arrays = Enumerable.Range(0, Size).ToArray();
		_hashSet = new HashSet<int>(_arrays);
	}

	[Benchmark(Baseline = true)]
	public bool EnumerableContains() => _arrays.Contains(42);
	
	[Benchmark]
	public bool ArrayContains() => Array.IndexOf(_arrays,42) > -1;

	[Benchmark]
	public bool ForContains()
	{
		for (int i = 0; i < _arrays.Length; i++)
		{
			if (_arrays[i] == 42) return true;
		}

		return false;
	}

	[Benchmark]
	public bool HashSetContains() => _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比較了。不過這些差別都很小，除非是效能非常敏感的場景，可以忽略不計，本文解決了筆者的一些困擾，簡單記錄一下。