HashSet与列表性能

很显然，genericsHashSet<T>类的search性能高于genericsList<T>类的search性能。 只需比较基于散列的密钥和List<T>类中的线性方法。

然而，计算散列键本身可能需要一些CPU周期，因此对于less量项目，线性search可以是HashSet<T>的真正替代。

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

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

Answer 1

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

假设你有一个List<T> ，它只有平均5个项目。 在大量循环中，如果每个循环都添加或删除单个项目，最好使用List<T> 。

我在我的机器上做了一个testing，而且，从List<T>获得优势，它必须非常小。 对于短string的列表，优势在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 

这里是以graphics显示的数据：

代码如下：

 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(); } 

Answer 2

你看错了。 是的，列表的线性search会击败less量项目的HashSet。 但是性能差异通常对于那些小的collections无关紧要。 一般来说，你需要担心的是大型的collections品，这就是你在Big-O方面的想法 。 然而，如果你已经测量了HashSet性能的真正瓶颈，那么你可以尝试创build一个混合的List / HashSet，但是你会通过进行大量的经验性能testing来做到这一点，而不是在SO上提出问题。

Answer 3

是否使用HashSet <>或者列表<>取决于你如何访问你的集合 。 如果您需要保证项目的顺序，请使用列表。 如果你不这样做，请使用HashSet。 让微软担心他们的哈希algorithm和对象的实现。

HashSet将访问项目而不必枚举集合（ O（1）或其附近的复杂性），并且由于List保证顺序，与HashSet不同，有些项目将不得不枚举（O（n）的复杂性）。

Answer 4

比较两个性能不同的结构是没有意义的。 使用传达意图的结构。 即使你说你的List<T>不会有重复，并且迭代次序并不重要，使得它与HashSet<T> ，使用List<T>仍然是一个糟糕的select，因为它的容错性相对较小。

也就是说，我会检查一下其他方面的performance，

 +------------+--------+-------------+-----------+----------+----------+-----------+ | 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** | +------------+--------+-------------+-----------+----------+----------+-----------+ 

* Even though addition is O(1) in both cases, it will be relatively slower in HashSet<T> since it involves cost of precomputing hash code before storing it.

** The superior scalability of HashSet<T> has a memory cost. Every entry is stored as a new object along with its hash code. This article might give you an idea.

Answer 5

只是以为我会用不同的场景的基准来说明以前的答案：

1. 一些（12-20）小string（长度在5到10个字符之间）
2. 许多（〜10K）小弦
3. 几个长string（长度在200到1000个字符之间）
4. 许多（〜5K）长的string
5. 几个整数
6. 许多（〜10K）整数

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

1. 在列表的开头（“开始”，索引0）
2. 在名单的开头（“早”，索引1）
3. 在列表中间（“中间”，索引计数/ 2）
4. 在列表末尾（“迟到”，索引计数2）
5. 在列表的末尾（“结束”，索引计数-1）

在每个场景之前，我生成随机大小的随机string列表，然后将每个列表提供给一个哈希集合。 每个场景跑了一万次，本质上是：

（testing伪代码）

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

示例输出

testingWindows 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] 

Answer 6

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

Answer 7

答案一如既往是“ 这要看情况 ”。 我从你正在谈论C＃的标签中假设。

你最好的select是确定

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

并写一些testing用例。

这也取决于你如何对列表进行sorting（如果是完全sorting），需要进行什么样的比较，“比较”操作需要多长时间才能列表中的特定对象，甚至是你打算如何使用采集。

一般来说，最好的select不是基于你正在使用的数据的大小，而是你打算如何访问它。 你有每一块数据与一个特定的string，或其他数据？ 基于哈希的集合可能是最好的。 您正在存储的数据的顺序是重要的，还是需要同时访问所有数据？ 定期清单可能会更好。

额外：

当然，我上面的评论假设“性能”是指数据访问。 还有什么要考虑的：当你说“表演”时你在找什么？ performance个人价值是否抬头？ pipe理大型（10000,10万以上）价值集合吗？ 用数据填充数据结构的性能是什么？ 删除数据？ 访问个人数据位？ replace值？ 迭代值？ 内存使用情况？ 数据复制速度？ 例如，如果通过string值访问数据，但主要性能要求是最小的内存使用量，则可能存在相互冲突的devise问题。

Answer 8

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

Answer 9

这取决于。 如果确切的答案真的很重要，做一些分析和发现。 如果你确定你永远不会有一定数量的元素在集合中，去一个列表。 如果数字是无限的，使用HashSet。

Answer 10

取决于你的哈希值。 如果你的键是整数，你可能不需要太多的项目，在HashSet更快。 如果你在一个string上键入它，那么它会变慢，并取决于inputstring。

当然，你可以很容易地掀起一个基准？

Answer 11

你不考虑的一个因素是GetHashcode（）函数的健壮性。 有了完美的散列函数，HashSet显然会有更好的search性能。 但是随着散列函数的减less，HashSetsearch时间也会减less。

Answer 12

取决于很多因素…列表实现，CPU体系结构，JVM，循环语义，equals方法的复杂性等…当列表变得足够大以便有效地进行基准testing（1000多个元素）时，基于哈希的二进制查找超过了线性search，差异只能从那里扩大。

希望这可以帮助！