HashSet vs. List 的性能比较
HashSet vs. List 的性能比较
很明显，泛型HashSet类的搜索性能比泛型List类要高。只需比较以哈希为基础的关键字和List类中的线性方法。
但是，计算哈希键本身可能会占用一些CPU周期，因此对于少量项目，线性搜索可能是HashSet的真正替代方案。
我的问题是：何时达到了平衡点？
为了简化场景（并且公平），让我们假设List类使用元素的Equals()方法来识别一个项目。
admin 更改状态以发布 2023年5月23日
无论是比较行为不同的两种结构的性能还是使用传达意图的结构，都是没有什么意义的。即使你说你的 List 不会有重复并且迭代顺序无所谓，使其可比较到 HashSet，但使用 List 仍然是一个相对不太容错的选择。
话虽如此，我还是会检查一些其他方面的性能，
+------------+--------+-------------+-----------+----------+----------+-----------+ | Collection | Random | Containment | Insertion | Addition | Removal | Memory | | | access | | | | | | +------------+--------+-------------+-----------+----------+----------+-----------+ | List| O(1) | O(n) | O(n) | O(1)* | O(n) | Lesser | | HashSet | O(n) | O(1) | n/a | O(1) | O(1) | Greater** | +------------+--------+-------------+-----------+----------+----------+-----------+
-
尽管在这两种情况下添加都是 O(1)，但在 HashSet 中相对较慢，因为在存储之前需要预处理哈希码的成本。
-
HashSet 的优越可扩展性是有一种内存成本的。每个条目都被存储为一个新对象以及它的哈希码。这篇文章可能会给你一个想法。
很多人认为，一旦你达到速度实际上成为问题的规模，HashSet总是会击败List，但这取决于你正在做什么。
假设你有一个List，它在平均情况下只会有5个项。在大量的循环中，如果每个循环仅添加或删除一个项目，你可能会更好地使用List。
我在我的机器上进行了测试，好吧，它必须非常非常小才能从List中获得优势。对于短字符串的列表，优势在大小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 list = new List();
HashSet hashset = new HashSet();
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