HashSet （IEqualityComparer ）的查找时间复杂度是多少？
在C＃.NET中，我喜欢使用HashSets，因为它们的查找时间复杂度为O（1）。 如果我要查询大量数据，我通常更喜欢将HashSet用于List，因为它具有这种时间复杂性。
令我困惑的是HashSet的构造函数，它将IEqualityComparer作为参数：
http://msdn.microsoft.com/en-us/library/bb359100.aspx
在上面的链接中，备注注意到“构造函数是一个O（1）操作”，但如果是这种情况，我很好奇，如果查找仍然是O（1）。
特别是，在我看来，如果我要编写一个Comparer来传递给HashSet的构造函数，每当我执行查找时，必须在每个键上执行Comparer代码以检查是否存在一场比赛。 这不是O（1），而是O（n）。
当元素添加到集合中时，实现是否在内部构建查找表？
总的来说，我如何确定有关.NET数据结构复杂性的信息？
HashSet通过散列（通过IEqualityComparer.GetHashCode ）对您插入的对象进行工作，并根据散列将对象抛存到存储桶中。 桶本身存储在arrays中，因此是O（1）部分。
例如（这不一定是C＃实现的工作方式，它只是给出了一种风味）它占用了散列的第一个字符，并将带有以1开头的散列的所有内容抛入存储桶1.散列2，存储桶2，等等上。 在该桶中是另一个桶arrays，它们通过哈希中的第二个字符进行分配。 那么对于哈希中的每个字符….
现在，当你向上看时，它会散列它，然后跳过适当的桶。 它必须进行多次数组查找（哈希中每个字符一次）但不会随着N的增加而增长，N是您添加的对象数，因此是O（1）等级。
对于您的另一个问题，这是一篇博客文章，其中包含许多馆藏运营的复杂性： http ： //c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html
如果我要编写一个Comparer来传递给HashSet的构造函数，每当我执行查找时，必须在每个键上执行Comparer代码以检查是否存在匹配。 这不是O（1），而是O（n）。
让我们调用您正在搜索“查询”值的值。
你能解释为什么你认为必须在每个键上执行比较器以查看它是否与查询匹配？
这种看法是错误的。 （当然，比较器提供的哈希码对于每个键都是相同的！）搜索算法对哈希码与查询的哈希码匹配的每个键执行相等比较器，以哈希表中的桶数为模。 这就是散列表获得O（1）查找时间的方式。
当元素添加到集合中时，实现是否在内部构建查找表？
是。
总的来说，我如何确定有关.NET数据结构复杂性的信息？
阅读文档。
它取决于IEqualityComparer实现提供的散列函数（ GetHashCode() ）的质量。 理想的散列函数应该提供分布均匀的散列码随机集。 这些哈希码将用作允许将键映射到值的索引，因此通过键搜索值变得更有效，尤其是当键是复杂对象/结构时。
必须在每个键上执行Comparer代码以检查是否存在匹配。 这不是O（1），而是O（n）。
这不是哈希表的工作原理，这是一种直接的powershell搜索。 在哈希表的情况下，你会有更智能的方法，它使用索引搜索（哈希码）。
如果传递IEqualityComparer，查找仍为O（1）。 哈希集仍然使用相同的逻辑，就像您没有传递IEqualityComparer一样; 它只使用IEqualityComparer的GetHashCode和Equals实现，而不是System.Object的实例方法（或者有问题的对象提供的覆盖）。