什么是HashSet的&LT的查找时间复杂度; T>（&的IEqualityComparer LT; T>）？ [英] What is the lookup time complexity of HashSet<T>(IEqualityComparer<T>)?

问题描述

在C＃.NET，我喜欢用，因为他们的所谓O（1）查找时间复杂度HashSets。如果我有一大组将要查询的数据，我通常喜欢用HashSet的一个列表，因为它有这个时间复杂度。

In C#.NET, I like using HashSets because of their supposed O(1) time complexity for lookups. If I have a large set of data that is going to be queried, I often prefer using a HashSet to a List, since it has this time complexity.

什么混淆我对于HashSet的，这需要的IEqualityComparer作为参数的构造：

What confuses me is the constructor for the HashSet, which takes IEqualityComparer as an argument:

的 http://msdn.microsoft.com/en-us/library/bb359100.aspx

在上面的链接，该言论注意，构造复杂度为O（1）操作，但如果是这样的话，我很好奇，如果查找仍然是O（1）。

In the link above, the remarks note that the "constructor is an O(1) operation," but if this is the case, I am curious if lookup is still O(1).

在特定的，在我看来，如果我是写的Comparer在传递到HashSet的构造函数，每当我执行查找，比较器代码将不得不在每一个关键的执行进行检查，看是否有匹配。这不会是O（1），但为O（n）。

In particular, it seems to me that, if I were to write a Comparer to pass in to the constructor of a HashSet, whenever I perform a lookup, the Comparer code would have to be executed on every key to check to see if there was a match. This would not be O(1), but O(n).

是否执行内部构造的查找表作为元素被添加到集合

Does the implementation internally construct a lookup table as elements are added to the collection?

在一般情况下，怎么可能我确定有关.NET数据结构的复杂性信息？

In general, how might I ascertain information about complexity of .NET data structures?

推荐答案

A HashSet的通过散列工作（通过 IEqualityComparer.GetHashCode ），插入对象和对象掷到每桶哈希值。水桶本身被存储在一个阵列，因此将O（1）的一部分。

A HashSet works via hashing (via IEqualityComparer.GetHashCode) the objects you insert and tosses the objects into buckets per the hash. The buckets themselves are stored in an array, hence the O(1) part.

例如（这不一定究竟是如何C＃实现的作品，它只是给出了一个味）需要哈希的第一个字符，并以井出发抛出一切1到水桶1散列2，斗2，依此类推。里面那个桶是由哈希第二个字符瓜分桶的另一个数组。因此，对在散列....

For example (this is not necessarily exactly how the C# implementation works, it just gives a flavor) it takes the first character of the hash and throws everything with a hash starting with 1 into bucket 1. Hash of 2, bucket 2, and so on. Inside that bucket is another array of buckets that divvy up by the second character in the hash. So on for every character in the hash....

现在，当你看的东西了，它哈希它，并跳转直通适当的水桶。它有做几阵查找（一个在散列每个字符），但不成长为N的函数，你添加对象的数量，因此O（1）的评级。

Now, when you look something up, it hashes it, and jumps thru the appropriate buckets. It has to do several array lookups (one for each character in the hash) but does not grow as a function of N, the number of objects you've added, hence the O(1) rating.

为您的其他问题，这里是一个博客帖子的许多藏品操作的复杂性：的 http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html

To your other question, here is a blog post with the complexity of a number of collections' operations: http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html

这篇关于什么是HashSet的&LT的查找时间复杂度; T>（&的IEqualityComparer LT; T>）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！