HashSet和List的性能差异

Question

很明显，在泛型类 HashSet<T> 和泛型类 List<T>中，前者的搜索性能比后者高。只需比较基于哈希的键和List<T>中的线性方法即可。

然而，计算哈希键本身可能需要一些CPU周期，因此对于少量项，线性搜索可以成为HashSet<T>的真正替代品。

我的问题是：何时达到收支平衡点？

为了简化情景（并公平起见），让我们假设List<T>使用元素的Equals()方法来识别项。

- Michael Damatov

---

如需最小化查找时间，还应考虑数组和排序数组。要正确回答此问题，需要进行基准测试，但您需要告诉我们更多关于T的信息。另外，HashSet的性能可能会受到T.GetHashCode()运行时间的影响。 - Eldritch Conundrum

Answer 1

很多人说，当你的数据规模越来越大且速度是一个问题时，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();
}

- innominate227

---

非常感谢！这是一个很好的解释，我在为游戏引擎寻找一种比 List<T> 更快速添加和删除项目的东西，由于我通常会有大量对象，这种集合非常适合。 - redcodefinal

实际上，在.NET框架中有一个集合，它根据其包含的项数在列表和哈希表实现之间切换：HybridDictionary。 - MgSam

微软似乎已经放弃了这个想法，因为它只提供了一个非通用版本。 - MgSam

尽管这篇回答内容很详尽，但它未能回答原问题有关列表与哈希集搜索性能的问题。你正在测试它们的插入和删除速度，这需要更多时间和不同的性能特征，而不是搜索。请再试一次，使用.Contains方法，你的图表将会发生显著变化。 - Robert McKee

@hypehuman，CPU 不能直接在系统内存上操作数据，而是需要把数据从内存中读取到缓存中进行操作。请求移动内存和实际移动之间存在显著的延迟，因此 CPU 经常会一次性请求移动更大的连续内存块。这背后的思想是，下一个指令所需的内存很可能非常接近上一个指令使用的内存，因此通常已经在缓存中了。当您的数据散布在整个内存中时，获取幸运的机会就减少了。 - Roy T.

Answer 2

比较两个行为不同的结构在性能上基本上是没有意义的。使用能够传达意图的结构。即使你说你的 List 不会有重复项，并且迭代顺序无关紧要，使其可与 HashSet 相比较，但使用 List 仍然是一个糟糕的选择，因为它相对来说容错性较低。

话虽如此，我将检查一些其他性能方面的问题，

+------------+--------+-------------+-----------+----------+----------+-----------+
| 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具有更好的可扩展性，但是会带来内存消耗。每个条目都作为一个新对象存储，并附带其哈希码。这篇文章可能会给你一些想法。

- nawfal

---

我的问题（六年前）并不是关于理论性能的。 - Michael Damatov

HashSet允许使用ElementAt()进行随机访问，我认为这将需要O(n)的时间。另外，也许您可以在表格中加入每个集合是否允许重复项（例如：列表允许，但哈希集不允许）。 - Dan W

@DanW 在表格中，我只是在比较性能，而不是行为特征。感谢您的 ElementAt 提示。 - nawfal

ElementAt只是一个LINQ扩展，它并没有做任何你不能在另一个自己添加的方法中优化的事情。我认为在不考虑ElementAt的情况下，表格更有意义，因为所有其他方法都明确存在于这些类上。 - Dinerdo

感谢这个表格，在我的使用情况中，每次启用/禁用目标时，我需要向填充的集合中添加和删除目标，这帮助我做出了正确的选择（HashSet）。 - CaseyHofland

Answer 3

你的看法有些错误。是的，对于少量的项目来说，使用List进行线性搜索会比HashSet更快。但是对于那么小的集合来说，性能差异通常并不重要。你真正需要担心的是大型集合，这时候你需要考虑到Big-O的概念。然而，如果你已经测量出HashSet性能上的瓶颈，那么你可以尝试创建一个混合的List/HashSet结构，但是你需要通过大量的实际性能测试来完成，而不是在Stack Overflow上提问。

- Eloff

---

当集合变得足够大，需要担心HashSet和List之间的区别是在什么时候？是当集合中有几个元素、成千上万个元素还是亿级元素？ - om-nom-nom

不，如果元素数量超过几百个，性能差异就会很大。关键是如果你要进行HashSet擅长的访问类型（例如，检查元素X是否在集合中），则始终使用HashSet。如果你的集合很小，List更快，那么这些查找实际上很少成为应用程序的瓶颈。如果你可以测量出它确实是瓶颈，那么可以尝试优化它——否则你会浪费时间。 - Eloff

如果你有一个在循环中被多次访问的小集合，这并不是一个罕见的情况。 - dan-gph

@om-nom-nom - 我认为重点在于无论临界点在哪里，因为：“如果性能是一个问题，请使用HashSet<T>。在List<T>可能更快的小数量情况下，差异是微不足道的。” - Scott Smith

Answer 4

无论使用 HashSet<> 还是 List<>，取决于您需要如何访问集合。如果需要保证项目的顺序，请使用 List。如果不需要，则使用 HashSet。让微软担心他们哈希算法和对象的实现。

HashSet将访问项目而无需枚举集合（O(1)或接近其复杂度），而因为List保证顺序，与HashSet不同，某些项目将必须枚举（O(n)的复杂度）。

- Chris

---

列表可能会通过其索引计算特定元素的偏移量（因为所有元素都是相同类型且可能占用相同的内存大小）。因此，列表不必枚举其元素。 - Ilya Serbis

@Lu55 - 这个问题是关于在集合中查找项目的。一个典型的场景是集合是动态的 - 自上次查找给定项以来，可能已经添加或删除了项目 - 因此一个索引是没有意义的（因为它会发生改变）。如果你有一个静态的集合（在你进行计算时不会改变），或者项目从不被删除，并且总是在末尾添加，那么List是首选，因为你可以记住一个索引 - 这就是你所描述的情况。 - ToolmakerSteve

如果您需要对HashSet进行排序，可以使用SortedSet。仍然比List快得多。 - live-love

Answer 5

我想为不同场景提供一些基准测试数据以说明之前的答案:

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

对于每种情况，查找出现的值：

1. 在列表开始处（“start”，索引0）
2. 靠近列表开始处（“early”，索引1）
3. 在列表中间（“middle”，索引count/2）
4. 靠近列表末尾（“late”，索引count-2）
5. 在列表末尾（“end”，索引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内存, 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]

- drzaus

---

有趣，感谢您进行此项工作。不幸的是，我怀疑这些讨论会引发不必要的重构。希望大多数人能够得出的结论是，在最坏的情况下，“List”仍然只需花费0.17毫秒来执行单个查找操作，并且不太可能需要将其替换为“HashSet”，除非查找频率达到荒谬的水平。到那时，使用List通常已经不是问题的主要原因了。 - Paul Walls

这并不是实际信息...或者说它最初就是错误的...我只检查了2到8个字符的小值。对于每10个值，都创建了List / HashSet... HashSet慢了30%...如果使用List的容量，则差异甚至达到了40%。只有当我们在List没有指定容量并且通过整个列表检查每个值之前才添加时，HashSet才会变快10%。 - Maxim

如果项目数减少到4，则即使在最坏的情况下（差异为10％），List仍然会获胜。因此，我不建议在字符串小集合（比如 <20）中使用HashSet。这就是与您的“少量小型”测试不同的地方。 - Maxim

@Maxim 无法说我的结果是“错误的”——这就是在我的机器上发生的事情。你的情况可能会有所不同。实际上，我刚刚在一台新的Win10 4.0GHz 16GB固态电脑上重新运行了它们(https://gist.github.com/zaus/014ac9b5a78b267aa1643d63d30c7554)，并得到了类似的结果。 我看到的结论是，无论搜索键在哪里或列表有多大，哈希集的性能更加稳定，而列表的性能从更好到慢了300倍以上都有可能。但正如PaulWalls最初评论的那样，我们正在谈论严肃的#微优化。 - drzaus

@drzaus 在 gist 中回复了。 - Maxim

Answer 6

盈亏平衡点将取决于计算哈希的成本。哈希计算可能很简单，也可能不是... :-) 还有 System.Collections.Specialized.HybridDictionary 类可帮助您不必担心盈亏平衡点。

- Walden

---

您还需要考虑比较的成本。对于Contains(T)方法，HashSet将进行一次比较以检查它是否具有哈希冲突，而List则在查找正确项之前对每个项进行比较。您还必须考虑由T.GetHashCode()生成的哈希值的分布情况，因为如果它始终返回相同的值，则基本上使HashSet执行与List相同的操作。 - Martin Brown

关于“计算哈希的成本”- 在什么情况下，这比直接比较两个项目的成本要高得多？除非写得很糟糕，否则它将是比较成本的一个小倍数。因此，在所有“通常”的情况下，平衡点发生在少量项目处。 - ToolmakerSteve

Answer 7

您可以使用混合字典（HybridDictionary），它自动检测断点并接受空值，使其与哈希集（HashSet）基本相同。

- Maestro

---

点赞这个想法，但请不要在今天使用它。拒绝非泛型。另外，字典是键值映射，集合不是。 - nawfal

Answer 8

答案，一如既往地是“这要看情况”。我假设你谈论的是C#。

你最好确定以下几点：

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

并编写一些测试用例。此外，还取决于您如何对列表进行排序（如果有排序），需要进行哪种比较，特定对象在列表中的“比较”操作需要多长时间，甚至您打算如何使用该集合。

通常，最好的选择不是基于您正在处理的数据大小，而是基于您打算如何访问它。每个数据与特定字符串或其他数据相关联吗？基于哈希的收藏可能是最好的选择。存储的数据顺序重要吗？您将需要同时访问所有数据吗？普通列表可能更好。

另外：

当然，我上面的评论假设“性能”意味着数据访问。还有一些其他考虑因素：当您说“性能”时，您要寻找什么？是单个值查找的性能吗？是管理大型（10000、100000或更多）值集的性能吗？是填充数据结构的性能？删除数据？访问单个数据位？替换值？遍历值？内存使用率？数据复制速度？例如，如果您通过字符串值访问数据，但主要性能要求是最小内存使用率，则可能存在冲突的设计问题。

- Robert P

Answer 9

这要看情况。如果精确答案非常重要，可以进行一些分析并找出答案。如果您确定集合中元素数量不会超过一定数量，请选择List。如果数量无限制，请使用HashSet。

- Adam Rosenfield

Answer 10

取决于你要哈希的内容。如果你的键是整数，那么在HashSet中存储不太多的项就足以使其更快。如果你的键是字符串，则速度会变慢，并且取决于输入字符串。

当然，你可以很容易地编写一个基准测试吧？

- Peter