如何实现0(1)查找属于容器的项目状态

本文关键字：项目 状态 属于 何实现 实现 查找 | 更新日期: 2023-09-27 18:14:00

我有一个容器，其中包含大量(数百万)对象，并且必须为每个项目维护一个已验证的状态，例如:

class MyContainer<T>
{
    bool IsValidated(T t);
}

项是否被验证完全是容器的概念。物品没有这样的概念。那么在这种情况下，如何实现项目的Validated状态呢?我将用我想到的两个解决方案来解释这个问题:

解决方案1)通过强制添加到集合中的项从基类继承，为项本身添加一个Validated属性:

class MyContainer<T> where T : BaseItem
{
    bool IsValidated(T t)
    {
        return t.IsValidated;
    }
}
class BaseItem
{
    bool IsValidated;
}

但这似乎是错误的。项是否被验证是容器关心的问题。该条目不应该有任何关于"验证"的概念。但另一方面，这是我能想到的唯一解决方案，给定一个Item，允许在O(1)中查找其验证状态。

解决方案2)在容器中维护一个字典，将Items与验证状态关联起来:

class MyContainer<T>
{
    Dictionary<T, bool> isValidated;
    bool IsValidated(T t)
    {
        return isValidated[t];
    }
}

这解决了第一个解决方案的"错误"。它从Item中删除了所有验证知识，也不要求项继承基类。但不好的一面是，确定一个Item的验证状态的查找现在是O(log n)。

我无法克服的是，就设计而言，最糟糕的解决方案(#1)如何在查找性能方面更好。除了解决方案#1的糟糕设计之外，我想不出任何能产生O(1)查找的方法。

对于O(1)是否有一个设计良好的解决方案，或者我应该只解决O(log n)查找?

如何实现0(1)查找属于容器的项目状态

正如Dave所写，字典的复杂度接近于0 (1)

通过键来检索值非常快，接近0(1)。因为Dictionary类是作为散列实现的表。

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

相关文章：