很明显，泛型HashSet<T>类的搜索性能要高于泛型List<T>类。只需将基于哈希的键与List<T>类中的线性方法进行比较。
然而，计算哈希键本身可能需要一些CPU周期，因此对于少量的项，线性搜索可以成为HashSet<T>的真正替代方法。
我的问题是:盈亏平衡在哪里?
为了简化场景(公平起见)，让我们假设List<T>类使用元素的Equals()方法来标识一个项。
当前回答
我只是想用一些不同场景的基准来说明前面的答案:
一些(12 - 20)小字符串(长度在5到10个字符之间) 许多(~10K)小字符串 一些长字符串(长度在200到1000个字符之间) 许多(~5K)长字符串 几个整数 许多(~10K)整数
对于每个场景，查找出现的值:
在列表的开头("start"，索引0) 靠近列表开头("early"， index 1) 在列表的中间("middle"，索引计数/2) 接近列表末尾("late"， index count-2) 在列表的末尾("end"， index 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 Ram, 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]
其他回答
您可以使用HybridDictionary自动检测断点，并接受空值，使其本质上与HashSet相同。
很多人都说，一旦你达到了速度实际上是一个问题的大小，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();
}
答案一如既往地是“视情况而定”。我假设从标签你说的是c#。
你最好的办法就是决定
一组数据 使用要求
并编写一些测试用例。
它还取决于您如何对列表进行排序(如果它已经排序)，需要进行哪种比较，“Compare”操作对列表中的特定对象需要多长时间，甚至取决于您打算如何使用集合。
一般来说，最好的选择不是基于您正在处理的数据的大小，而是基于您打算如何访问它。您是否拥有与特定字符串或其他数据相关联的每个数据片段?基于哈希的集合可能是最好的。存储数据的顺序重要吗?还是需要同时访问所有数据?那么，一个常规的清单可能会更好。
附加:
Of course, my above comments assume 'performance' means data access. Something else to consider: what are you looking for when you say "performance"? Is performance individual value look up? Is it management of large (10000, 100000 or more) value sets? Is it the performance of filling the data structure with data? Removing data? Accessing individual bits of data? Replacing values? Iterating over the values? Memory usage? Data copying speed? For example, If you access data by a string value, but your main performance requirement is minimal memory usage, you might have conflicting design issues.
我只是想用一些不同场景的基准来说明前面的答案:
一些(12 - 20)小字符串(长度在5到10个字符之间) 许多(~10K)小字符串 一些长字符串(长度在200到1000个字符之间) 许多(~5K)长字符串 几个整数 许多(~10K)整数
对于每个场景，查找出现的值:
在列表的开头("start"，索引0) 靠近列表开头("early"， index 1) 在列表的中间("middle"，索引计数/2) 接近列表末尾("late"， index count-2) 在列表的末尾("end"， index 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 Ram, 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]
视情况而定。如果确切的答案真的很重要，那就做一些分析，找出答案。如果你确定你永远不会有超过一定数量的元素在集合中，使用List。如果数字是无界的，则使用HashSet。
推荐文章
- 关于。net中api破坏变化的权威指南
- MVVM:从开始到结束的教程?
- 如果性能很重要，我应该使用Java的String.format()吗?
- 使用“var”会影响性能吗?
- 在Python中哪个更快:x**。5还是math.sqrt(x)?
- 任务有什么用。FromResult< result >
- c#中比较数组的最简单方法
- 我如何创建目录，如果它不存在，以创建文件?
- 我如何分割一个字符串由一个多字符分隔符在c# ?
- 为什么Python的无穷散列中有π的数字?
- 按类型查找WPF窗口中的所有控件
- 为什么java.util.Set没有get(int index)?
- 数组与列表的性能
- 使用私有静态方法的优点
- 为什么这个迭代的列表增长代码给出IndexError:列表赋值索引超出范围?如何重复添加(追加)元素到列表?
