很明显,泛型HashSet<T>类的搜索性能要高于泛型List<T>类。只需将基于哈希的键与List<T>类中的线性方法进行比较。
然而,计算哈希键本身可能需要一些CPU周期,因此对于少量的项,线性搜索可以成为HashSet<T>的真正替代方法。
我的问题是:盈亏平衡在哪里?
为了简化场景(公平起见),让我们假设List<T>类使用元素的Equals()方法来标识一个项。
很明显,泛型HashSet<T>类的搜索性能要高于泛型List<T>类。只需将基于哈希的键与List<T>类中的线性方法进行比较。
然而,计算哈希键本身可能需要一些CPU周期,因此对于少量的项,线性搜索可以成为HashSet<T>的真正替代方法。
我的问题是:盈亏平衡在哪里?
为了简化场景(公平起见),让我们假设List<T>类使用元素的Equals()方法来标识一个项。
当前回答
视情况而定。如果确切的答案真的很重要,那就做一些分析,找出答案。如果你确定你永远不会有超过一定数量的元素在集合中,使用List。如果数字是无界的,则使用HashSet。
其他回答
这取决于很多因素……列表实现,CPU架构,JVM,循环语义,equals方法的复杂性,等等…当列表变得足够大,可以有效地进行基准测试(1000多个元素)时,基于哈希的二进制查找就可以轻松地击败线性搜索,并且差异只会在此基础上扩大。
希望这能有所帮助!
You're looking at this wrong. Yes a linear search of a List will beat a HashSet for a small number of items. But the performance difference usually doesn't matter for collections that small. It's generally the large collections you have to worry about, and that's where you think in terms of Big-O. However, if you've measured a real bottleneck on HashSet performance, then you can try to create a hybrid List/HashSet, but you'll do that by conducting lots of empirical performance tests - not asking questions on SO.
盈亏平衡将取决于计算散列的成本。哈希计算可以是微不足道的,或者不是…:-)总有System.Collections.Specialized.HybridDictionary类帮助你不必担心盈亏平衡点。
您可以使用HybridDictionary自动检测断点,并接受空值,使其本质上与HashSet相同。
您没有考虑到的一个因素是GetHashcode()函数的健壮性。有了完美的哈希函数,HashSet显然会有更好的搜索性能。但是随着哈希函数的减少,HashSet搜索时间也会减少。