Menu
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?
739
Dictionary is faster than hashtable as dictionary is a generic strong type. Hashtable is slower as it takes object as data type which leads to boxing and unboxing.
A dictionary is 6.6 times faster than a list when we lookup in 100 items.
You're missing the most important "feature" of a hash table, which is that the hash code of the key is used to map the key to a position in the array of buckets. So, given a key, finding the index in the array of buckets takes a constant time (given the hash code calculation is based only on the the value of the key).
In Hashtable, you can store key/value pairs of the same type or of the different type. In Dictionary, you can store key/value pairs of same type. In Hashtable, there is no need to specify the type of the key and value. In Dictionary, you must specify the type of key and value.
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).
69
Might be helpful : .NET HashTable Vs Dictionary - Can the Dictionary be as fast?
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
