HashTable or Dictionary 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

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).

Answer 2

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