295

I am trying to figure out when and why to use a Dictionary or a HashTable. I have done a bit of a search on here and have found people talking about the generic advantages of the Dictionary which I totally agree with, which leads the boxing and unboxing advantage for a slight performance gain.

But I have also read the Dictionary will not always return the objects in the order they are inserted, thing it is sorted. Where as a HashTable will. As I understand it this leads to the HashTable being far faster for some situations.

My question is really, what might those situations be? Am I just wrong in my assumptions above? What situations might you use to choose one above the other, (yes the last one is a bit ambiguous).

John Saunders
  • 160,644
  • 26
  • 247
  • 397
Jon
  • 15,110
  • 28
  • 92
  • 132

10 Answers10

319

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

Mehrdad Afshari
  • 414,610
  • 91
  • 852
  • 789
  • 21
    @Jon- The chaining and rehashing is discussed in depth here- http://msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx – RichardOD Jul 06 '09 at 20:52
  • Thank you both. Just found that page as Richard posted it... Was going to ask about Chaining but the MSDN site is actually helpful! – Jon Jul 06 '09 at 20:56
  • 6
    @Mehrdad - What's not clear to me about how collisions are resolved is this:if multiple keys could result in the same hash, then how do you ensure you're getting the right value on lookups, ie how does the function know which element to return? In http://msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx it says,"Rather than reprobing in the event of a collision, as is done with the Hashtable class, the Dictionary simply chains any collisions onto the bucket's list." Does this mean that when using Dictionary, collisions are not something the developer has to worry about? – Howiecamp Feb 02 '10 at 03:26
  • 6
    @Howiecamp: This is not really much different from `Hashtable`. Hash tables store 3 pieces of information in an entry: key hash, key itself, and the value. For items with equal hash, it'll have to traverse the list to find the item with equal key and return its value. This is pretty much true for `Hashtable` too. As a developer using a `Dictionary` normally, you don't need to worry about it. – Mehrdad Afshari Feb 02 '10 at 11:32
  • @Mehrdad Just to be clear, both the Hashtable and Dictionary objects store the key itself, and both also hide collisions from the developer? – Howiecamp Feb 05 '10 at 05:33
  • to add to this, hash tables are thread safe. not all operations with a dictionary are thread safe – John Smith Nov 22 '15 at 22:06
  • *"None of them guarantee preserving the order of items."` - There is no such thing as an order with hash tables in general. They don't store data index based but based on a key mapping. When you say *"not guaranteed"* it implies that there actually is an order and with some luck the order is the original order in which elements were added. –  Jun 07 '23 at 09:48
130

I guess it doesn't mean anything to you now. But just for reference for people stopping by

Performance Test - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable

Memory allocation:

Memory usage performance test

Time used for inserting:

Time used for inserting

Time for searching an item:

Time for searching an item

Razvan Dumitru
  • 11,815
  • 5
  • 34
  • 54
Abdul Munim
  • 18,869
  • 8
  • 52
  • 61
  • 2
    @JohnHenckel no, sorted list has slower lookup. Bigger performance coefficient means better performance and better memory usage. So, sorted list has the best memory usage according to the charts but it sucks in other areas such as inserting and lookup. – dmitry1100 Feb 05 '20 at 08:58
  • Hi all, Sorry to ask a basic question. But, if "bigger performance coefficient" means better performance, then from the charts, it looks like Hashtable is faster than Dictionary ? If yes, then why do people say that Dictionary is faster than Hastable in practice (because Dictionary does not use boxing/unboxing) ? – Job_September_2020 Dec 20 '20 at 00:01
  • 2
    I am confused by the meaning of the units in this graph. If the Y-axis is "time", a higher value should be "more time", but my own test shows a SortedDictionary is much slower than Dictionary. So, perhaps add a message "Higher is faster" – Bouke Versteegh Mar 08 '21 at 08:28
38

Differences between Hashtable and Dictionary

Dictionary:

  • Dictionary returns error if we try to find a key which does not exist.
  • Dictionary faster than a Hashtable because there is no boxing and unboxing.
  • Dictionary is a generic type which means we can use it with any data type.

Hashtable:

  • Hashtable returns null if we try to find a key which does not exist.
  • Hashtable slower than dictionary because it requires boxing and unboxing.
  • Hashtable is not a generic type,
Community
  • 1
  • 1
user2771704
  • 5,994
  • 6
  • 37
  • 38
25

Another important difference is that the Hashtable type supports lock-free multiple readers and a single writer at the same time, while Dictionary does not.

Steven
  • 681
  • 10
  • 6
  • 9
    Concurrent Dictionary will support(.Net 4.0) – Tamilmaran Feb 06 '12 at 04:35
  • 1
    I'm not sure if I understand this answer. Looking here https://msdn.microsoft.com/en-us/library/system.collections.hashtable%28v=vs.90%29.aspx it says "To support multiple writers all operations on the Hashtable must be done through the wrapper returned by the Synchronized method, provided that there are no threads reading the Hashtable object." That seems to make the "lock-free multiple readers" feature pretty useless, so then we're back to having to lock all access to the Hashtable, just like with Dictionary. – RenniePet Sep 16 '15 at 22:37
18

MSDN Article: "The Dictionary<TKey, TValue> class has the same functionality as the Hashtable class. A Dictionary<TKey, TValue> of a specific type (other than Object) has better performance than a Hashtable for value types because the elements of Hashtable are of type Object and, therefore, boxing and unboxing typically occur if storing or retrieving a value type".

Link: http://msdn.microsoft.com/en-us/library/4yh14awz(v=vs.90).aspx

akjoshi
  • 15,374
  • 13
  • 103
  • 121
Juan Camilo Caro J.
  • 181
  • 1
  • 2
11

Both are effectively the same class (you can look at the disassembly). HashTable was created first before .Net had generics. Dictionary, however is a generic class and gives you strong typing benefits. I would never use HashTable since Dictionary costs you nothing to use.

Adam Luter
  • 2,193
  • 1
  • 15
  • 20
9

Another important difference is that Hashtable is thread safe. Hashtable has built in multiple reader/single writer (MR/SW) thread safety which means Hashtable allows ONE writer together with multiple readers without locking. In the case of Dictionary there is no thread safety, if you need thread safety you must implement your own synchronization.

To elaborate further:

Hashtable, provide some thread-safety through the Synchronized property, which returns a thread-safe wrapper around the collection. The wrapper works by locking the entire collection on every add or remove operation. Therefore, each thread that is attempting to access the collection must wait for its turn to take the one lock. This is not scalable and can cause significant performance degradation for large collections. Also, the design is not completely protected from race conditions.

The .NET Framework 2.0 collection classes like List<T>, Dictionary<TKey, TValue>, etc do not provide any thread synchronization; user code must provide all synchronization when items are added or removed on multiple threads concurrently If you need type safety as well thread safety, use concurrent collections classes in the .NET Framework. Further reading here.

Community
  • 1
  • 1
NullReference
  • 2,828
  • 2
  • 30
  • 33
2

Dictionaries have the advantage of being a generic type, which makes it type safe and a bit faster due to lack of need for boxing. The following comparison table (constructed using the answers found in a similar SO question post) illustrates some of the other reasons that support dictionaries over hash tables (or vice versa).

janeon
  • 59
  • 4
1

If you care about reading that will always return the objects in the order they are inserted in a Dictionary, you may have a look at

OrderedDictionary - values can be accessed via an integer index (by order in which items were added) SortedDictionary - items are automatically sorted

ToXinE
  • 308
  • 2
  • 13
0

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.

jitendra mahaapatro
  • 39