3

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.

Improve this question
3
  • 1
    Hashtables and Dictionarys are faster than a list. Depends on what you do with them. Commented Jan 31, 2013 at 17:46
  • 1
    A HashSet 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 Commented Jan 31, 2013 at 17:47
  • "value that you need as a key" this won't be possible if you have duplicate values Commented Jan 31, 2013 at 17:48

3 Answers 3

Reset to default
4

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

4

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 unique1.
  • 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 know what type you're storing).

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

Improve this answer

Comments

2

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.