最近，我不得不对存储在DataSet中的数据进行一些非常处理繁重的工作。如此沉重的工作足以使我最终使用一种工具来帮助识别代码中的某些瓶颈。当我分析瓶颈时，我注意到尽管DataSet查找并不是很慢(它们不是瓶颈)，但它比我预期的要慢。我一直以为DataSet使用某种HashTable样式的实现，该实现将使查询成为O(1)(或者至少就是我认为的HashTables)。我的查询速度似乎比这慢得多。

我想知道是否有人对.NET的DataSet类的实现一无所知，是否愿意分享他们的知识。

如果我做这样的事情：

DataTable dt = new DataTable();
if(dt.Columns.Contains("SomeColumn"))
{
    object o = dt.Rows[0]["SomeColumn"];
}

包含方法(Contains(...))和检索值存储在对象o中的查找时间将有多快？我本来以为它像HashTable一样非常快(假设我对HashTables的了解是正确的)，但看起来似乎不...

我是从内存中编写该代码的，因此某些事情可能不是"语法上正确的"。

解决方案

我想任何查找都是O(n)，因为我不认为它们会使用任何类型的哈希表，但实际上会使用更多的数组来查找行和列。

实际上，我相信列名称存储在哈希表中。对于区分大小写的查询，应为O(1)或者常量查询。如果必须仔细检查每一个，那么它当然是O(n)。

实际上，建议在引用列时使用整数，这可以提高性能。为了使事情易于管理，我们可以声明常量整数。因此，除了我们所做的以外，我们可以做

const int SomeTable_SomeColumn = 0;

DataTable dt = new DataTable();
if(dt.Columns.Contains(SomeTable_SomeColumn))
{
    object o = dt.Rows[0][SomeTable_SomeColumn];
}

通过Reflector，DataRow [" ColumnName"]的步骤为：

• 从ColumnName获取DataColumn。使用该行的DataColumnCollection [" ColumnName"]。在内部，DataColumnCollection将其DataColumns存储在Hastable中。 O(1)
• 获取DataRow的行索引。索引存储在内部成员中。 O(1)
• 使用DataColumn [index]在索引处获取DataColumn的值。 DataColumn将其数据存储在System.Data.Common.DataStorage(内部，抽象)成员中：return dataColumnInstance._storage.Get(recordIndex);一个示例性的具体实现是System.Data.Common.StringStorage(内部，密封)。 StringStorage(以及我检查过的其他具体的DataStorage)将它们的值存储在数组中。 Get(recordIndex)只是在recordIndex的值数组中获取对象。 O(1)

因此，总的来说，我们是O(1)，但这并不意味着在操作期间进行哈希和函数调用是没有成本的。这只是意味着随着DataRows或者DataColumns数量的增加，它不会花费更多。

有趣的是，DataStorage使用数组作为值。无法想象添加或者删除行时很容易重建。