HashSet vs. List性能

视情况而定。如果确切的答案真的很重要，那就做一些分析，找出答案。如果你确定你永远不会有超过一定数量的元素在集合中，使用List。如果数字是无界的，则使用HashSet。

盈亏平衡将取决于计算散列的成本。哈希计算可以是微不足道的，或者不是…:-)总会有System.Collections.Specialized.HybridDictionary类来帮助你不必担心盈亏平衡点。

这取决于很多因素……列表实现，CPU架构，JVM，循环语义，equals方法的复杂性，等等…当列表变得足够大，可以有效地进行基准测试(1000多个元素)时，基于哈希的二进制查找就可以轻松地击败线性搜索，并且差异只会在此基础上扩大。

希望这能有所帮助!

这取决于你在哈希什么。如果你的键是整数，在HashSet更快之前，你可能不需要很多项。如果你在一个字符串上输入键，那么它会更慢，这取决于输入的字符串。

你肯定可以很容易地建立一个基准吗?

答案一如既往地是“这取决于”。我假设从标签你说的是c#。

你最好的办法就是决定

1. 一组数据
2. 使用要求

并编写一些测试用例。

它还取决于您如何对列表进行排序(如果它已经排序)，需要进行哪种比较，“Compare”操作对列表中的特定对象需要多长时间，甚至取决于您打算如何使用集合。

一般来说，最好的选择不是基于您正在处理的数据的大小，而是基于您打算如何访问它。您是否拥有与特定字符串或其他数据相关联的每个数据片段?基于哈希的集合可能是最好的。存储数据的顺序重要吗?还是需要同时访问所有数据?那么，一个常规的清单可能会更好。

附加:

当然，我上面的评论假设“性能”指的是数据访问。还有一些需要考虑的问题:当你说“性能”时，你在寻找什么?业绩个人价值查吗?是对大(10000、100000或更多)值集的管理吗?是用数据填充数据结构的性能吗?删除数据?访问单个数据位?替换值吗?遍历值?内存使用情况?数据复制速度?例如，如果您通过字符串值访问数据，但您的主要性能要求是最小的内存使用，那么您可能会遇到冲突的设计问题。

是否使用HashSet<>或List<>归结为您需要如何访问您的收藏。如果你需要保证项目的顺序，使用一个列表。如果没有，请使用HashSet。让微软去担心他们的哈希算法和对象的实现吧。

HashSet将访问项目而不必枚举集合(复杂度为O (1)或接近它)，并且由于List保证顺序，与HashSet不同，一些项目将必须被枚举(复杂度为O(n))。

您没有考虑到的一个因素是GetHashcode()函数的健壮性。有了完美的哈希函数，HashSet显然会有更好的搜索性能。但是随着哈希函数的减少，HashSet搜索时间也会减少。

你看错了。是的，对List进行线性搜索对于少量的项会胜过HashSet。但是对于如此小的集合来说，性能差异通常并不重要。通常你需要担心的是大的集合，而那就是你想想Big-O。但是，如果您已经测量到HashSet性能的真正瓶颈，那么您可以尝试创建一个混合的List/HashSet，但是您将通过执行大量的经验性能测试来做到这一点——而不是询问关于SO的问题。

您可以使用HybridDictionary自动检测断点，并接受空值，使其本质上与HashSet相同。

很多人说，一旦你达到了实际关心速度的大小，HashSet<T>将总是击败List<T>，但这取决于你在做什么。

假设你有一个List<T>，它平均只包含5个元素。在大量的循环中，如果每个循环添加或删除一个项，那么使用List<T>可能会更好。

我在我的机器上做了一个测试，而且，好吧，它必须非常非常小才能从List<T>中获得优势。对于一个短字符串列表，在大小为5之后，对于大小为20之后的对象，优势就消失了。

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms


2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms


3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms


4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms


5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms


6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms


7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms


8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms


9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms


1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms


4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms


7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms


10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms


13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms


16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms


19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms


22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms


25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms


28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms


31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms


34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms


37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms


40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms


43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms


46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms


49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

下面是以图表形式显示的数据:

代码如下:

static void Main(string[] args)
{
int times = 10000000;


for (int listSize = 1; listSize < 10; listSize++)
{
List<string> list = new List<string>();
HashSet<string> hashset = new HashSet<string>();


for (int i = 0; i < listSize; i++)
{
list.Add("string" + i.ToString());
hashset.Add("string" + i.ToString());
}


Stopwatch timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
list.Remove("string0");
list.Add("string0");
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
hashset.Remove("string0");
hashset.Add("string0");
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
Console.WriteLine();
}


for (int listSize = 1; listSize < 50; listSize+=3)
{
List<object> list = new List<object>();
HashSet<object> hashset = new HashSet<object>();


for (int i = 0; i < listSize; i++)
{
list.Add(new object());
hashset.Add(new object());
}


object objToAddRem = list[0];
        

Stopwatch timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
list.Remove(objToAddRem);
list.Add(objToAddRem);
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
hashset.Remove(objToAddRem);
hashset.Add(objToAddRem);
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
Console.WriteLine();
}


Console.ReadLine();
}

我只是想用一些不同场景的基准来说明前面的答案:

1. 一些(12 - 20)小字符串(长度在5到10个字符之间)
2. 许多(~10K)小字符串
3. 一些长字符串(长度在200到1000个字符之间)
4. 许多(~5K)长字符串
5. 几个整数
6. 许多(~10K)整数

对于每个场景，查找出现的值:

1. 在列表的开头("start"，索引0)
2. 靠近列表开头("early"， index 1)
3. 在列表的中间("middle"，索引计数/2)
4. 接近列表末尾("late"， index count-2)
5. 在列表的末尾("end"， index count-1)

在每个场景之前，我生成随机大小的随机字符串列表，然后将每个列表提供给一个哈希集。每个场景运行了10,000次，基本上是:

(测试伪代码)

stopwatch.start
for X times
exists = list.Contains(lookup);
stopwatch.stop


stopwatch.start
for X times
exists = hashset.Contains(lookup);
stopwatch.stop

样例输出

在Windows 7上测试，12GB Ram, 64位，Xeon 2.8GHz

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...


Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]




---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...


Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]




---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...


Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]




---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...


Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]




---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...


Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]




---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...


Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]

比较行为不同的性能的两个结构本质上是没有意义的。使用传达意图的结构。即使你说你的List<T>不会有重复，迭代顺序不影响它与HashSet<T>的可比性，使用List<T>仍然是一个糟糕的选择，因为它的容错能力相对较差。

也就是说，我将检查其他方面的性能，

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+

• 尽管在这两种情况下加法都是O(1)，但在HashSet中它会相对较慢，因为它涉及到在存储哈希代码之前预计算哈希代码的成本。

• HashSet优越的可伸缩性有内存成本。每个条目连同它的哈希代码一起存储为一个新对象。这篇文章可能会给你一个想法。