Efficiency of DataColumnCollection.Contains

Posted by Sameer on June 1, 2007 in .NET articles | ∞

The runtime complexity of DataColumnCollection.Contains is O(1) for case sensitive lookup ,and O(n) for case insensitive lookup. O(1) means constant time, i.e. it is done same speed regardless of whether the dataset size is 10, or 10,000,000 records, and O(n) means it will run in a speed to the size proportional to the data you are running it on.

When would you use DataColumnCollection.Contains? When you have a DataTable and you want to know if it contains a column, before deleting it, you can run the following (C# example):

DataTable dt = Users.GetBusinessObject.GetData();
if (dt.Columns.Contains("SupplementaryColumn"))
{
    dt.Columns.Remove("SupplementaryColumn"));
}

How do we know this runs in constant time? i.e. how do we determine this? Download Reflector and when you run it on our DataTable class, this is what we find. Our column names are stored as a Hashtable, which has O(1) lookup speed.

private readonly Hashtable columnFromName;

When we call Contains, it runs the following code:

public bool Contains(string name)
{
return ((this.columnFromName[name] is DataColumn) || (this.IndexOfCaseInsensitive(name) >= 0));
}

Breaking this down, it first does a case sensitive search for the name on the hashtable, and if not, it calls the case insensitive search which is O(n) complexity.