HashTable or Dictonary Search Time

Question

Is the search time for a HashTable or dictionary always O (1) if it has a unique hash code?

If a HashTable has 100 million rows, will it take as much time as 1 row?

Answer 1

No. This is technically possible, but it would be extremely rare to receive the same amount of overhead. The hash table is organized in buckets. Dictionary <> (and Hashtable) computes the bucket number for an object with an expression like this:

int bucket = key.GetHashCode() % totalNumberOfBuckets; 

Thus, two objects with a different hash code can end in the same bucket. The bucket is a List <>, then the indexer looks for this list for the key, which is O (n), where n is the number of elements in the bucket.

The <> dictionary dynamically increments the value of totalNumberOfBuckets to support efficient bucket searches. When you upload one hundred million items into the dictionary, there will be thousands of buckets. The chances that the bucket is empty when you add an item will be very small. But if this is accidental, then yes, it takes the same amount of time to get the item.

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

Answer 2

As long as there is no collision with hashes, yes.

Answer 3

May be useful: .NET HashTable Vs Dictionary - Can a Dictionary Be So Fast?

Answer 4

 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 in both cases. So the answer seems to be Yes. [Got changes, so I will explain better)

It seems to be permanent. But it depends on the Hash function giving a different result in all keys. Since there is no hash function that can do this, it all comes down to the data you pass to the dictionary. Therefore, you will need to check your data to make sure it is persistent.