.net - HashSet 与 List 性能

Question

很明显，泛型类的搜索性能HashSet<T>高于泛型List<T>类。只需将基于散列的键与List<T>类中的线性方法进行比较。

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

我的问题：盈亏平衡点在哪里？

为了简化场景（公平起见），让我们假设List<T>该类使用元素的Equals()方法来标识一个项目。

score 930 · Accepted Answer

很多人都说，一旦你达到了速度实际上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();
}

score 93 · Accepted Answer

比较两种行为不同的结构的性能本质上是没有意义的。使用传达意图的结构。即使您说您List<T>不会有重复项，并且迭代顺序与 a 相比并不重要，但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 卓越的可扩展性具有内存成本。每个条目连同其哈希码一起存储为一个新对象。这篇文章可能会给你一个想法。

score 77 · Accepted Answer

你看错了。是的，List 的线性搜索将在少量项目中击败 HashSet。但是对于那么小的集合，性能差异通常并不重要。这通常是您必须担心的大型集合，这就是您认为 Big-O的地方。但是，如果您测量了 HashSet 性能的真正瓶颈，那么您可以尝试创建一个混合 List/HashSet，但您将通过进行大量经验性能测试来做到这一点 - 而不是问关于 SO 的问题。

score 56 · Accepted Answer

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

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

score 35 · Accepted Answer

只是想我会加入一些针对不同场景的基准来说明以前的答案：

几个 (12 - 20) 个小字符串（长度在 5 到 10 个字符之间）
许多（~10K）小字符串
一些长字符串（长度在 200 到 1000 个字符之间）
许多（~5K）长字符串
几个整数
许多 (~10K) 整数

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

在列表的开头（“开始”，索引 0）
靠近列表的开头（“早期”，索引 1）
在列表的中间（“中间”，索引计数/2）
接近列表末尾（“迟到”，索引计数为 2）
在列表的末尾（“end”，索引计数-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 位、至强 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]

score 11 · Accepted Answer

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

score 8 · Accepted Answer

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

score 6 · Accepted Answer

一如既往，答案是“视情况而定”。我假设您正在谈论 C# 的标签。

你最好的选择是确定

一组数据
使用要求

并编写一些测试用例。

它还取决于您如何对列表进行排序（如果它已经排序），需要进行什么样的比较，对列表中的特定对象执行“比较”操作需要多长时间，甚至您打算如何使用收藏。

一般来说，最好的选择不是基于您正在使用的数据的大小，而是您打算如何访问它。您是否有与特定字符串或其他数据相关联的每条数据？基于散列的集合可能是最好的。您存储的数据的顺序是否重要，或者您是否需要同时访问所有数据？一个常规的列表可能会更好。

额外的：

当然，我上面的评论假设“性能”意味着数据访问。需要考虑的其他事项：当您说“性能”时，您在寻找什么？绩效个人价值是向上的吗？是否管理大型（10000、100000 或更多）值集？是用数据填充数据结构的性能吗？删除数据？访问单个数据位？替换价值观？迭代值？内存使用情况？数据复制速度？例如，如果您通过字符串值访问数据，但您的主要性能要求是最小内存使用量，则您可能会遇到设计冲突问题。

score 4 · Accepted Answer

这取决于。如果确切的答案真的很重要，请进行一些分析并找出答案。如果您确定集合中的元素数量永远不会超过一定数量，请使用列表。如果数字无界，请使用 HashSet。

score 3 · Accepted Answer

取决于你在散列什么。如果您的键是整数，那么在 HashSet 更快之前您可能不需要很多项目。如果您在字符串上键入它，那么它会更慢，并且取决于输入字符串。

当然，您可以很容易地制定基准吗？

score 3 · Accepted Answer

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

score 1 · Accepted Answer

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

希望这可以帮助！

.net - HashSet 与 List 性能

12 回答 12

样本输出

Related

Reference