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.

`Hashtables and Dictionarys are faster than a list`. Depends on what you do with them. — Frédéric Hamidi, Jan 31 '13 at 17:46
A [`HashSet`](http://msdn.microsoft.com/en-us/library/bb359438.aspx) would provide the functionality that you are thinking with using a `Dictionary` and using the keys but not the values. The issue with that is they must be unique, but you'd have had the same thing using a `Dictionray` — JG in SD, Jan 31 '13 at 17:47
`"value that you need as a key"` this won't be possible if you have duplicate values — Kaf, Jan 31 '13 at 17:48

score 3 · Answer 1 · answered Jan 31 '13 at 17:52

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

score 3 · Accepted Answer · answered Jan 31 '13 at 17:55

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

score 2 · Answer 3 · answered Jan 31 '13 at 17:50

Your statement "list or array is for elements without values, and dictionary is for elements with values", is not strictly true.

More accurately, a List is a collection of elements, and a Hashtable or Dictionary is a collection of elements along with a unique key to be used to access each one.

Use a list for collections of a very few elements, or when you will only need to access the entire collection, not a single element of the collection.

Use a Hashtable or Dictionary when the collection is large and/or when you will need to find/access individual members of the collection.

List vs Dictionary (Hashtable)

3 Answers3