HashSet（IEqualityComparer）的查找时间复杂度是多少？在C#.NET中，我喜欢使用HashSet，因为它们的查找时间复杂度为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）插入的对象，并根据散列将对象放入桶中。桶本身存储在数组中，因此是O(1)部分。例如（这不一定是C#实现的工作方式，它只是赋予了它一种风格）它采用散列的第一个字符并将散列以1开头的所有内容扔到Bucket1、Hash2、Bucket2等中。在。在该桶内是另一个桶数组，由散列中的第二个字符分配。所以对于散列中的每个字符......现在，当你查找时，它会散列它，然后跳过适当的桶。它必须执行多个数组查找（哈希中的每个字符一个）但不会随着N增长，这是您添加的对象数，所以它是O(1)等级。对于您的其他问题，这里有一篇博客文章涵盖了许多收集操作的复杂性：http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html如果我是编写比较器以传递给HashSet的构造函数，每当我执行查找时，都必须在每个键上执行比较器代码以检查匹配。这不是O(1)，而是O(n)。让我们将您要搜索的值称为“查询”值。你能解释一下为什么你认为比较器必须在每个键上执行以查看它是否与查询匹配吗？这种看法是错误的。（当然，比较器提供的哈希码对于每个key都是相同的！）搜索算法对每个哈希码与查询的哈希码匹配的key执行相等比较器，由哈希表中桶的个数为模.这就是哈希表获得O(1)查找时间的方式。当元素被添加到集合中时，实现是否在内部构建了一个查找表？是的。通常，如何确定有关.NET数据结构复杂性的信息？阅读文档。它取决于IEqualityComparer实现提供的哈希函数(GetHashCode())的质量。理想的哈希函数应该提供一组均匀分布的随机哈希码。这些哈希码将用作允许将键映射到值的索引，因此通过键搜索值变得更加高效，尤其是当键是复杂的对象/结构时。比较器代码必须在每个键上执行以检查匹配。这不是O(1)，而是O(n)。这不是哈希表的工作方式，它是一种直接的powershell搜索。在哈希表的情况下，您会有更聪明的方法，它使用索引搜索（哈希码）。如果传递了IEqualityComparer，查找仍然是O(1)。Hashset仍然使用相同的逻辑，就好像你没有通过IEqualityComparer；它只使用IEqualityComparer的GetHashCode和Equals实现，而不是System.Object的实例方法（或相关对象提供的覆盖）。以上是C#学习教程：HashSet(IEqualityComparer)的查找时间复杂度是多少？如果所有分享的内容对你有用，需要进一步了解C#学习教程，希望大家多多关注。本文收集自网络，不代表立场。如涉及侵权，请点击右侧联系管理员删除。如需转载请注明出处：
