List vs Dictionary (Hashtable)

Question

This may be a silly question but I am reading about that Hashtables and Dictionaries are faster than a list because they index the items with keys.

I know a List or Array is for elements without values, and a Dictionary is for elements with values. So I would think that it maybe be smart to have a Dictionary with the value that you need as a key and the value equal in all of them?

Update:

Based on the comments what I think I need is a HashSet. This question talks about their performance.

Answer 1

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

Answer 2

There are some weaknesses to Dictionary/Hashtable vs a List/array as well:

• You have to compute the hash value of the object with each lookup.
• For small collections, iterating through the array can be faster than computing that hash, especially because a hash is not guaranteed to be unique¹.
• They are not as good at iterating over the list of items.
• They are not very good at storing duplicate entries (sometimes you legitimately want a value to show in an array more than once)
• Sometimes a type does not have a good key to associate with it

Use what fits the situation. Sometimes that will be a list or an array. Sometimes it will be a Dictionary. You should almost never use a HashTable any more (prefer Dictionary<KeyType, Object> if you really don't what type you're storing).

_{¹It usually is unique, but because there is a small potential for collisions the collection must check the bucket after computing the hash value.}