HashTable or Dictonary lookup time

Question

Is the Lookup Time for a HashTable or Dictionary Always O(1) as long as it has a Unique Hash Code?

If a HashTable has 100 Million Rows would it take the same amount of time to look up as something that has 1 Row?

Answer 1

As long as there are no collisions with the hashes, yes.

Answer 2

Yes if the collision (depends upon how your Hash function performs) is minimized then they both give look up time O(1) i.e. constatnt time

Answer 3

var dict = new Dictionary<string, string>();
for (int i = 0; i < 100; i++) {
    dict.Add("" + i, "" + i);
}
long start = DateTime.Now.Ticks;

string s = dict["10"];

Console.WriteLine(DateTime.Now.Ticks - start);

for (int i = 100; i < 100000; i++) {
    dict.Add("" + i, "" + i);
}
start = DateTime.Now.Ticks;
s = dict["10000"];
Console.WriteLine(DateTime.Now.Ticks - start);

This prints 0 on both cases. So it seems the answer would be Yes. [Got moded down so I'll explain better]

It seems that it is constant. But it depends on the Hash function giving a different result in all keys. As there is no hash function that can do that it all boils down to the Data that you feed to the Dictionary. So you will have to test with your data to see if it is constant.

Answer 4

Might be helpful : .NET HashTable Vs Dictionary - Can the Dictionary be as fast?

Answer 5

No. It is technically possible but it would be extremely rare to get the exact same amount of overhead. A hash table is organized into buckets. Dictionary<> (and Hashtable) calculate a bucket number for the object with an expression like this:

int bucket = key.GetHashCode() % totalNumberOfBuckets;

So two objects with a different hash code can end of in the same bucket. A bucket is a List<>, the indexer next searches that list for the key which is O(n) where n is the number of items in the bucket.

Dictionary<> dynamically increases the value of totalNumberOfBuckets to keep the bucket search efficient. When you pump a hundred million items in the dictionary, there will be thousands of buckets. The odds that the bucket is empty when you add an item will be quite small. But if it is by chance then, yes, it will take just as long to retrieve the item.

The amount of overhead increases very slowly as the number of items grows. This is called amortized O(1).