.NET:如何有效地检查List <string>中50,000项的唯一性？

Question

在某些库代码中,我有一个可以包含50,000个或更多项的List.

库的调用者可以调用导致字符串添加到列表的方法.如何有效地检查要添加的字符串的唯一性？

目前,在添加字符串之前,我扫描整个列表并将每个字符串与要添加的字符串进行比较.这开始显示超过10,000个项目的规模问题.

我将对此进行基准测试,但对洞察力感兴趣.

• 如果我用List <>替换List <>,那么随着列表增长到10,000个项目以及更高,ContainsKey()会更快吗？
• 如果我推迟了所有项目添加后的唯一性检查,它会更快吗？在那一点上,我需要检查每个元素与每个其他元素,仍然是一个n ^^ 2操作.

---

编辑

一些基本的基准结果.我创建了一个抽象类,它暴露了两种方法:Fill和Scan.填充只用n个项目填充集合(我用了50,000).扫描扫描列表m次(我使用5000)以查看是否存在给定值.然后我为List构建了该类的实现,为HashSet构建了另一个实现.

使用的字符串长度统一为11个字符,并通过抽象类中的方法随机生成.

一个非常基本的微观基准.

Hello from Cheeso.Tests.ListTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.4428266
Time to scan: 00:00:13.0291180

Hello from Cheeso.Tests.HashSetTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.3797751
Time to scan: 00:00:00.4364431

因此,对于该长度的字符串,当扫描唯一性时,HashSet比List快大约25倍.此外,对于此大小的集合,在向集合添加项目时,HashSet对List没有任何惩罚.

结果很有趣,无效.为了获得有效的结果,我需要进行预热间隔,多次试验,随机选择实施.但我相信这只会略微改变这一点.

感谢大家.

EDIT2

在添加随机化和多重试验之后,HashSet在这种情况下始终优于List,大约20倍.

这些结果不一定适用于可变长度,更复杂对象或不同集合大小的字符串.

Answer 1

你应该使用HashSet<T>专门为你正在做的事情而设计的课程.

Answer 2

使用HashSet<string> 而不是List<string>,它应该很好地扩展.

Answer 3

从我的测试,HashSet<string>没有时间相比List<string>:)