哪个在哈希表或排序列表中找到项目更快？-Whichisfastertofindaniteminahashtableorinasortedlist?

Algorithm complexity is a good thing to know, and hashtables are known to be O(1) while a sorted vector (in your case I guess it is better to use a sorted array than a list) will provide O(log n) access time.

算法复杂度是一件好事,并且哈希表已知为O(1),而排序向量(在您的情况下我认为使用排序数组比列表更好)将提供O(log n)访问时间。

But you should know that complexity notation gives you the access time for N going to the infinite. That means that if you know that your data will keep growing, complexity notation gives you some hint on the algorithm to chose.

但是你应该知道复杂符号可以让你获得N进入无限的访问时间。这意味着如果您知道您的数据将继续增长,复杂符号会给您一些选择的算法提示。

When you know that your data will keep a rather low length: for instance having only a few entries in your array/hashtable, you must go with your watch and measure. So have a test.

当您知道数据的长度相当低时:例如,您的数组/哈希表中只有少量条目,您必须使用手表并进行测量。所以有一个测试。

For instance, in another problem: sorting an array. For a few entries bubble sort while O(N^2) may be quicker than .. the quick sort, while it is O(n log n).

例如,在另一个问题中:对数组进行排序。对于少数条目冒泡排序,而O(N ^ 2)可能比快速排序更快,而它是O(n log n)。

Also, accordingly to other answers, and depending on your item, you must try to find the best hash function for your hashtable instance. Otherwise it may lead to dramatic bad performance for lookup in your hashtable (as pointed out in Hank Gay's answer).

此外,相应于其他答案,并且根据您的项目,您必须尝试为哈希表实例找到最佳哈希函数。否则,它可能导致在哈希表中查找的显着不良性能(正如Hank Gay的回答中指出的那样)。

Edit: Have a look to this article to understand the meaning of Big O notation .

编辑:看看这篇文章,了解Big O表示法的含义。

Assuming that by 'sorted list' you mean 'random-accessible, sorted collection'. A list has the property that you can only traverse it element by element, which will result in a O(N) complexity.

假设“排序列表”是指“随机可访问,已排序的集合”。列表具有您只能逐个元素遍历它的属性,这将导致O(N)复杂性。

The fastest way to find an element in a sorted indexable collection is by N-ary search, O(logN), while a hashtable without collissions has a find complexity of O(1).

在排序的可索引集合中查找元素的最快方法是通过N-ary搜索,O(logN),而没有collissions的哈希表具有O(1)的查找复杂度。

Unless the hashing algorithm is extremely slow (and/or bad), the hashtable will be faster.

除非散列算法非常慢(和/或坏),否则哈希表会更快。

UPDATE: As commenters have pointed out, you could also be getting degraded performance from too many collisions not because your hash algorithm is bad but simply because the hashtable isn't big enough. Most library implementations (at least in high-level languages) will automatically grow your hashtable behind the scenes—which will cause slower-than-expected performance on the insert that triggers the growth—but if you're rolling your own, it's definitely something to consider.

更新:正如评论者指出的那样,你也可能因太多的冲突而降低性能,不是因为你的哈希算法很糟糕,而是因为哈希表不够大。大多数库实现(至少在高级语言中)将自动增加你的哈希表幕后 - 这将导致插入的性能低于预期,触发增长 - 但如果你自己滚动,它肯定是一些东西考虑。

The get operation in a SortedList is O(log n) while the same operation e a HashTable is O(1). So, normally, the HashTable would be much faster. But this depends on a number of factors:

SortedList中的get操作是O(log n),而HashTable的相同操作是O(1)。因此,通常情况下,HashTable会更快。但这取决于许多因素:

• The size of the list

列表的大小

• Performance of the hashing algorithm

散列算法的性能

• Number of collisions / quality of the hashing algorithm

散列算法的冲突数/质量

It depends entirely on the amount of data you have stored.

它完全取决于您存储的数据量。

Assuming you have enough memory to throw at it (so the hash table is big enough), the hash table will locate the target data in a fixed amount of time, but the need to calculate the hash will add some (also fixed) overhead.

假设你有足够的内存来抛出它(所以哈希表足够大),哈希表将在固定的时间内定位目标数据,但是计算哈希值的需要会增加一些(也是固定的)开销。

Searching a sorted list won't have that hashing overhead, but the time required to do the work of actually locating the target data will increase as the list grows.

搜索排序列表不会产生散列开销,但实际定位目标数据所需的时间将随着列表的增长而增加。

So, in general, a sorted list will generally be faster for small data sets. (For extremely small data sets which are frequently changed and/or infrequently searched, an unsorted list may be even faster, since it avoids the overhead of doing the sort.) As the data set becomes large, the growth of the list's search time overshadows the fixed overhead of hashing, and the hash table becomes faster.

因此,通常,对于小数据集,排序列表通常会更快。 (对于经常更改和/或不经常搜索的非常小的数据集,未排序的列表可能更快,因为它避免了进行排序的开销。)随着数据集变大,列表的搜索时间增长过大散列的固定开销,哈希表变得更快。

Where that breakpoint is will vary depending on your specific hash table and sorted-list-search implementations. Run tests and benchmark performance on a number of typically-sized data sets to see which will actually perform better in your particular case. (Or, if the code already runs "fast enough", don't. Just use whichever you're more comfortable with and don't worry about optimizing something which doesn't need to be optimized.)

断点的位置将根据您的特定哈希表和sorted-list-search实现而有所不同。在许多通常大小的数据集上运行测试和基准测试性能,以查看在特定情况下哪些实际上会更好。 (或者,如果代码已经“足够快”运行,请不要。只需使用您感觉更舒服的东西,不要担心优化不需要优化的东西。)

In some cases, it depends on the size of the collection (and to a lesser degree, implementation details). If your list is very small, 5-10 items maybe, I'd guess the list would be faster. Otherwise xtofl has it right.

在某些情况下,它取决于集合的大小(在较小程度上,实现细节)。如果你的名单非常小,可能有5-10个项目,我猜这个名单会更快。否则xtofl就是对的。

HashTable would be more efficient for list containing more than 10 items. If the list has fewer than 10 items, the overhead due to hashing algo will be more.

对于包含10个以上项目的列表,HashTable会更有效。如果列表少于10个项目,则由于哈希算法导致的开销将更多。

In case you need a fast dictionary but also need to keep the items in an ordered fashion use the OrderedDictionary. (.Net 2.0 onwards)

如果您需要快速字典但需要以有序方式保留项目,请使用OrderedDictionary。 (.Net 2.0起)