ISet<T>与IReadOnlySet<T>是否被约定为具备O(1)查找性能？

云原生阿岚

2026-7-23

关于ISet和IReadOnlySet查找性能契约的疑问

我希望方法能接受宽泛的IEnumerable<T>作为输入，但如果输入不是HashSet<T>，像下面的示例代码操作可能会产生O(n²)的性能影响（延迟加载的IEnumerable情况更糟）：

public static IEnumerable<Booking> ByIds(this IEnumerable<Booking> bookings, IEnumerable<int> ids)
{
    return bookings.Where(b => ids.Contains(b.Id));
}

我考虑过几种方案，但都有弊端：

让调用者提前调用ToHashSet()：这属于实现细节，不该由调用者关注
强制输入为HashSet：同样是调用者无需关心的实现细节
在ByIds中始终调用ToHashSet()：面对超大集合会造成不必要的性能浪费

因此我设计了如下实现：

public static IEnumerable<Booking> ByIds(this IEnumerable<Booking> bookings, IEnumerable<int> ids)
{
    ids = ids.EnsureHashSet();

    return bookings.Where(b => ids.Contains(b.Id));
}

public static IEnumerable<T> EnsureHashSet<T>(this IEnumerable<T> source)
{
    if ( source is ISet<T> || source is IReadOnlySet<T> )
        return source;

    return source.ToHashSet();
}

我的疑问是：ISet<T>和IReadOnlySet<T>的契约中是否存在明确意图，规定它们应具备O(1)的查找性能？我明白无法阻止异常实现，但正常合规的实现是否至少有此设计意图？

解答

从.NET官方的设计契约来看，ISet<T>和IReadOnlySet<T>的核心设计目标之一就是提供高效的成员查找能力。

对于ISet<T>，官方设计意图明确指出它用于表示不包含重复元素的集合，其Contains方法的设计目标是实现接近O(1)的平均时间复杂度——这也是哈希集合（比如HashSet<T>）的核心特性。.NET的标准实现（HashSet<T>、SortedSet<T>）都严格遵循这一点：HashSet<T>的Contains是O(1)平均复杂度，SortedSet<T>是O(log n)，都远优于线性查找的O(n)。

IReadOnlySet<T>作为只读版本的集合契约，继承了ISet<T>的核心语义，它的设计同样是为了提供高效的成员检查。正常合规的实现（比如HashSet<T>的只读包装、ImmutableHashSet<T>）也都会保证高效的查找性能，不会出现线性查找的情况。

换句话说，虽然契约没有通过代码强制O(1)性能，但从设计意图和标准实现的角度，所有合规的ISet<T>/IReadOnlySet<T>实现都应该提供远优于线性查找的成员检查性能。你的EnsureHashSet方法设计合理，既避免了不必要的集合转换，又保证了后续查找操作的性能。

内容的提问来源于stack exchange，提问作者Dirk Boer

ISet<T>与IReadOnlySet<T>是否被约定为具备O(1)查找性能？

解答 #

解答