HashSet与列表性能

Question

HashSet与列表性能

很明显，泛型的搜索性能HashSet<T>类高于泛型类。List<T>班级，等级。只需将基于散列的密钥与List<T>班级，等级。

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

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

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

Answer 1

很多人都说，一旦你达到了速度的大小，你就会担心HashSet<T>将永远击败List<T>但这取决于你在做什么。假设你有一个List<T>平均只有5件物品在里面。在大量的循环中，如果每个周期都添加或删除单个项，则最好使用List<T>.我在我的机器上做了一个测试，而且，它必须非常小才能从我的机器中获得优势。List<T>..对于短字符串列表，优势在5之后消失，对象在20之后消失。1&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time:&nbsp;617ms1&nbsp;item&nbsp;HASHSET&nbsp;strs&nbsp;time:&nbsp;1332ms2&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time:&nbsp;781ms2&nbsp;item&nbsp;HASHSET&nbsp;strs&nbsp;time:&nbsp;1354ms3&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time :&nbsp;950ms3&nbsp;item&nbsp;HASHSET&nbsp;strs&nbsp;time:&nbsp;1405ms4&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time:&nbsp;1126ms4&nbsp;item&nbsp;HASHSET&nbsp;strs&nbsp;time:&nbsp;1441ms5&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time:&nbsp;1370ms5&nbsp;item&nbsp;H ASHSET&nbsp;strs&nbsp;time:&nbsp;1452ms6&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time:&nbsp;1481ms6&nbsp;item&nbsp;HASHSET&nbsp;strs&nbsp;time:&nbsp;1418ms7&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time:&nbsp;1581ms7&nbsp;item&nbsp;HASHSET&nbsp;strs&nbsp;time:&nbsp; 1464ms8&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time:&nbsp;1726ms8&nbsp;item&nbsp;HASHSET&nbsp;strs&nbsp;time:&nbsp;1398ms9&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time:&nbsp;1901ms9&nbsp;item&nbsp;HASHSET&nbsp;strs&nbsp;time:&nbsp;1433ms1&nbsp;item&nbsp;LIST &nbsp;objs&nbsp;time:&nbsp;614ms1&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1993ms4&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;837ms4&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1914ms7&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;1070ms7&nbsp;i &nbsp;tem&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1900ms10&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;1267ms10&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1904ms13&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;1494ms13&nbsp;item&nbsp;HASHSET&nbsp;ob &nbsp;js&nbsp;time:&nbsp;1893ms16&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;1695ms16&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1879ms19&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;1902ms19&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;195 &nbsp;0ms22&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;2136ms22&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1893ms25&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;2357ms25&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1826ms28&nbsp;item&nbsp; &nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;2555ms28&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1865ms31&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;2755ms31&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1963ms34&nbsp;item&nbsp;LIST&nbsp;objs&nbsp; &nbsp;time:&nbsp;3025ms34&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1874ms37&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;3195ms37&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1958ms40&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;3401ms4 &nbsp;0&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1855ms43&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;3618ms43&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1869ms46&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;3883ms46&nbsp;item&nbsp;HASHS &nbsp;ET&nbsp;objs&nbsp;time:&nbsp;2046ms49&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;4218ms49&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;1873ms下面是代码：static&nbsp;void&nbsp;Main(string[]&nbsp;args){ &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;times&nbsp;=&nbsp;10000000; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;listSize&nbsp;=&nbsp;1;&nbsp;listSize&nbsp;<&nbsp;10;&nbsp;listSize++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;List<string>&nbsp;list&nbsp;=&nbsp;new&nbsp;List<string>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;HashSet<string>&nbsp;hashset&nbsp;=&nbsp;new&nbsp;HashSet<string>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;listSize;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list.Add("string"&nbsp;+&nbsp;i.ToString()); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hashset.Add("string"&nbsp;+&nbsp;i.ToString()); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Stopwatch&nbsp;timer&nbsp;=&nbsp;new&nbsp;Stopwatch(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer.Start(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;times;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list.Remove("string0"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list.Add("string0"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer.Stop(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Console.WriteLine(listSize.ToString()&nbsp;+&nbsp;"&nbsp;item&nbsp;LIST&nbsp;strs&nbsp;time:&nbsp;"&nbsp;+&nbsp;timer.ElapsedMilliseconds.ToString()&nbsp;+&nbsp;"ms"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer&nbsp;=&nbsp;new&nbsp;Stopwatch(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer.Start(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;times;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hashset.Remove("string0"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hashset.Add("string0"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer.Stop(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Console.WriteLine(listSize.ToString()&nbsp;+&nbsp;"&nbsp;item&nbsp;HASHSET&nbsp;strs&nbsp;time:&nbsp;"&nbsp;+&nbsp;timer.ElapsedMilliseconds.ToString()&nbsp;+&nbsp;"ms"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Console.WriteLine(); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;listSize&nbsp;=&nbsp;1;&nbsp;listSize&nbsp;<&nbsp;50;&nbsp;listSize+=3) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;List<object>&nbsp;list&nbsp;=&nbsp;new&nbsp;List<object>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;HashSet<object>&nbsp;hashset&nbsp;=&nbsp;new&nbsp;HashSet<object>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;listSize;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list.Add(new&nbsp;object()); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hashset.Add(new&nbsp;object()); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;object&nbsp;objToAddRem&nbsp;=&nbsp;list[0]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Stopwatch&nbsp;timer&nbsp;=&nbsp;new&nbsp;Stopwatch(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer.Start(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;times;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list.Remove(objToAddRem); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list.Add(objToAddRem); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer.Stop(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Console.WriteLine(listSize.ToString()&nbsp;+&nbsp;"&nbsp;item&nbsp;LIST&nbsp;objs&nbsp;time:&nbsp;"&nbsp;+&nbsp;timer.ElapsedMilliseconds.ToString()&nbsp;+&nbsp;"ms"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer&nbsp;=&nbsp;new&nbsp;Stopwatch(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer.Start(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;times;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hashset.Remove(objToAddRem); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hashset.Add(objToAddRem); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;timer.Stop(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Console.WriteLine(listSize.ToString()&nbsp;+&nbsp;"&nbsp;item&nbsp;HASHSET&nbsp;objs&nbsp;time:&nbsp;"&nbsp;+&nbsp;timer.ElapsedMilliseconds.ToString()&nbsp;+&nbsp;"ms"); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Console.WriteLine(); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;Console.ReadLine();}

Answer 2

你看错了。是的，对列表的线性搜索会超过HashSet来获得少量的项。但是，性能差异通常对如此小的集合并不重要。通常你需要担心的是大量的收藏品，而这正是你需要担心的地方。从大O的角度思考..然而，如果您已经度量过HashSet性能的一个真正的瓶颈，那么您可以尝试创建一个混合List/HashSet，但是您将通过进行大量的经验性能测试来做到这一点-而不是对此提出问题。

Answer 3

&nbsp; 从本质上说，比较两种结构是毫无意义的。性能行为不同的人。使用传达意图的结构。即使你说List<T>不会有重复，迭代顺序也不重要，使其与HashSet<T>，使用它仍然是一个糟糕的选择。List<T>因为它的容错能力相对较低。尽管如此，我会检查其他方面表现，+------------+--------+-------------+-----------+----------+----------+-----------+| Collection | Random | Containment | Insertion | Addition |&nbsp; Removal | Memory&nbsp; &nbsp; ||&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; | access |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;|&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;|&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;|+------------+--------+-------------+-----------+----------+----------+-----------+| List<T>&nbsp; &nbsp; | O(1)&nbsp; &nbsp;| O(n)&nbsp; &nbsp; &nbsp; &nbsp; | O(n)&nbsp; &nbsp; &nbsp; | O(1)*&nbsp; &nbsp; | O(n)&nbsp; &nbsp; &nbsp;| Lesser&nbsp; &nbsp; || HashSet<T> | O(n)&nbsp; &nbsp;| O(1)&nbsp; &nbsp; &nbsp; &nbsp; | n/a&nbsp; &nbsp; &nbsp; &nbsp;| O(1)&nbsp; &nbsp; &nbsp;| O(1)&nbsp; &nbsp; &nbsp;| 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.