.Net Hashtable VS Dictionary - Can the Dictionary Be as Fast

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

System.Collections.Generic.Dictionary<TKey, TValue> and System.Collections.Hashtable classes both maintain a hash table data structure internally. None of them guarantee preserving the order of items.

Leaving boxing/unboxing issues aside, most of the time, they should have very similar performance.

The primary structural difference between them is that Dictionary relies on chaining (maintaining a list of items for each hash table bucket) to resolve collisions whereas Hashtable uses rehashing for collision resolution (when a collision occurs, tries another hash function to map the key to a bucket).

There is little benefit to use Hashtable class if you are targeting for .NET Framework 2.0+. It's effectively rendered obsolete by Dictionary<TKey, TValue>.

Hashtable vs Dictionary : Faster?

However, isn't hashtable's sorted, which could mean that the search could be faster?

I don't believe that hashtable is sorted.

They share a similar underlying implementation, but Dictionary<TKey, TValue> has been recommended over Hashtable for a long time, which will perform better for value types as it eliminates boxing/unboxing.

See https://referencesource.microsoft.com/#mscorlib/system/collections/hashtable.cs,77

If you really want to know, try benchmarking it. BenchmarkDotNet is a great library for that.

Why is Dictionary preferred over Hashtable in C#?

For what it's worth, a Dictionary is (conceptually) a hash table.

If you meant "why do we use the Dictionary<TKey, TValue> class instead of the Hashtable class?", then it's an easy answer: Dictionary<TKey, TValue> is a generic type, Hashtable is not. That means you get type safety with Dictionary<TKey, TValue>, because you can't insert any random object into it, and you don't have to cast the values you take out.

Interestingly, the Dictionary<TKey, TValue> implementation in the .NET Framework is based on the Hashtable, as you can tell from this comment in its source code:

The generic Dictionary was copied from Hashtable's source

Source

List vs Dictionary (Hashtable)

"Faster" depends on what you need them for.

A .NET List is just a slab of continuous memory (this in not a linked list), which makes it extremely efficient to access sequentially (especially when you consider the effects of caching and prefetching of modern CPUs) or "randomly" trough a known integer index. Searching or inserting elements (especially in the middle) - not so much.

Dictionary is an associative data structure - a key can be anything hashable (not just integer index), but elements are not sorted in a "meaningful" way and the access through the known key is not as fast as List's integer index.

So, pick the right tool for the job.

HashTable or Dictionary lookup time

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

.NET Dictionary, impressively fast but how does it work?

The dictionary<T,T> in .Net is a data structure called a hash table:

On Hash Table and .Net Dictionary:

http://en.wikipedia.org/wiki/Hash_table

http://msdn.microsoft.com/en-us/library/4yh14awz.aspx

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html

On Binary Search:

http://en.wikipedia.org/wiki/Binary_search

You're right, it uses more memory than an array to retrieve data. That's the trade off you pay for faster access. (This is true in most cases, when you start taking into account the setup time to build a hash table vs an array, at times a sorted array could be faster for setup time and access. In general this is a valid assumption though.)

.NET Framework - Any way to get Dictionary to be a little faster?

The dictionary is implemented using a hash table, I have looked at the code using Reflector a while back.

"The dictionary will most likely only
have about 10 buckets, but each bucket
can point to one of about 2,000
possibly things."

There is your problem. The dictionary uses the hash to locate the bucket, but the lookup in the bucket is linear.

You have to implement a hash algorithm with a better distribution to get better performance. The relation should be at least the opposite, i.e. 2000 buckets with 10 items each.

What is the primary difference between Dictionary and Hashtable

The Dictionary class differs from the
Hashtable class in more ways than one.
In addition to being strongly-typed,
the Dictionary also employs a
different collision resolution
strategy than the Hashtable class,
using a technique referred to as
chaining.

You can read this article: http://msdn.microsoft.com/en-us/library/ms379571(v=vs.80).aspx#datastructures20_2_topic6

It's really useful.

What are the differences b/w Hashtable, Dictionary and KeyValuePair?

Hashtable is an untyped associative container that uses DictionaryEntry class to return results of enumeration through its key-value pairs.

Dictionary<K,T> is a generic replacement of Hashtable that was introduced in C# 2.0. It uses KeyValuePair<K,T> generic objects to represent its key-value pairs.

The only place where you should see Hashtable these days is legacy code that must run on .NET 1.1, before generics have been introduced. It's been kept around for compatibility reasons, but you should prefer Dictionary<K,T> whenever you can.



Related Topics



Leave a reply



Submit