Clever Geek Handbook

List vs Dictionary (Hashtable)

It might be a stupid question, but I read that it is Hashtables

also Dictionaries

faster than a list because they index elements with keys.

I know that List

either Array

for elements with no values, and Dictionary

- for elements with values. So I think it might be wise to have Dictionary

with the value you need as the key and the value equal in all of them?

Update

Based on the comments, it looks to me like this HashSet

. This question talks about their effectiveness.

+3


source to share


3 answers


"Faster" depends on what you want.

.NET List

is just a panel of contiguous memory (not a linked list), which makes it extremely efficient to be accessed sequentially (especially if you are considering the effects of caching and prefetching on modern CPUs) or "randomly" through a known integer index. Finding or inserting elements (especially in the middle) is not much.



Dictionary

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

an integer index.

So, choose the right tool for the job.

+3


source


There are some drawbacks to Dictionary / Hashtable and List / array:

  • You have to compute the hash value of the object on every lookup.
  • For small collections, iterating through the array can be faster than calculating this hash, especially since the hash is not guaranteed to be unique 1 .
  • They are not that good at understanding the list of items.
  • They don't keep duplicate entries very well (sometimes you legitimately need a value to appear more than once in an array)
  • Sometimes a type doesn't have a good key to associate with it


Use what is appropriate for the situation. Sometimes it will be a list or an array. Sometimes it will be a dictionary. You should almost never use a HashTable (prefer Dictionary <KeyType, Object> unless you really have the type you are storing).

1 It is usually unique, but since there is little potential for collisions, the collection should check the bucket after calculating the hash value.

+3


source


Your operator "list or array for elements with no values, and dictionary for elements with values" is not strict.

More precisely, a List is a collection of elements, while a Hashtable or Dictionary is a collection of elements along with a unique key that will be used to access each of them.

Use a list for collections with very few items, or when you need to access the entire collection rather than a single item in the collection.

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

+2


source






More articles:


All Articles