很明显,泛型HashSet<T>类的搜索性能要高于泛型List<T>类。只需将基于哈希的键与List<T>类中的线性方法进行比较。
然而,计算哈希键本身可能需要一些CPU周期,因此对于少量的项,线性搜索可以成为HashSet<T>的真正替代方法。
我的问题是:盈亏平衡在哪里?
为了简化场景(公平起见),让我们假设List<T>类使用元素的Equals()方法来标识一个项。
很明显,泛型HashSet<T>类的搜索性能要高于泛型List<T>类。只需将基于哈希的键与List<T>类中的线性方法进行比较。
然而,计算哈希键本身可能需要一些CPU周期,因此对于少量的项,线性搜索可以成为HashSet<T>的真正替代方法。
我的问题是:盈亏平衡在哪里?
为了简化场景(公平起见),让我们假设List<T>类使用元素的Equals()方法来标识一个项。
当前回答
盈亏平衡将取决于计算散列的成本。哈希计算可以是微不足道的,或者不是…:-)总有System.Collections.Specialized.HybridDictionary类帮助你不必担心盈亏平衡点。
其他回答
这取决于很多因素……列表实现,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类帮助你不必担心盈亏平衡点。
答案一如既往地是“视情况而定”。我假设从标签你说的是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.
使用HashSet<>还是List<>取决于您需要如何访问您的集合。如果你需要保证项目的顺序,使用一个列表。如果没有,请使用HashSet。让微软去担心他们的哈希算法和对象的实现吧。
HashSet将访问项目而不必枚举集合(复杂度为O(1)或接近它),并且由于List保证顺序,与HashSet不同,一些项目将必须被枚举(复杂度为O(n))。