C# Dictionary Versus List Lookup Time
Both lists and dictionaries are used to store collections of data. A Dictionary < int, T > and List < T > are similar, both are random access data structures of the .NET framework. The Dictionary is based on a hash table, that means it uses a hash lookup, which is a rather efficient algorithm to look up things, on the other hand, a list you have to go element by element until it finds the result from beginning to the result each time.
When comparing with List data structure , the dictionary is always a more or less fixed lookup time. Lets go for some details. The Dictionary uses hashing to search for the data. A Dictionary first calculated a hash value for the key and this hash value leads to the target data bucket. After that, each element in the bucket needs to be checked for equality. But actually the list will be faster than the dictionary on the first item search because nothing to search in the first step. But in the second step, the list has to look through the first item, and then the second item. So each step the lookup takes more and more time. The larger the list, the longer it takes. Of course the Dictionary in principle has a faster lookup with O(1) while the lookup performance of a List is an O(n) operation.
The Dictionary map a key to a value and cannot have duplicate keys, whereas a list just contains a collection of values. Also Lists allow duplicate items and support linear traversal.
Consider the following example:
Add data to the list
A list cam simply add the item at the end of the existing list item.
Add data to the Dictionary
When you add data to a Dictionary, yo should specify a unique key to the data so that it can be uniquely identified.
A Dictionary have unique identifier, so whenever you look up a value in a Dictionary, the runtime must compute a hash code from the key. This optimized algorithm implemented by some low-level bit shifting or modulo divisions. We determine the point at which Dictionary becomes more efficient for lookups than List.
What is a Dictionary ?
The Dictionary class provides a mapping from a set of keys to a set of values. Dictionary is defined in the System.Collections.Generic namespace. Each addition to the dictionary should have a value and its associated key. It provides fast lookups to get values from its keys.
How to add items in a Dictionary ?
Retrieve items from dictionary
More about.... C# Dictionary
What is a List ?
Internally, List and ArrayList work by maintaining an internal array of objects, replaced with a larger array upon reaching capacity. A List dynamically resize, so ou do not need to manage the size on your own.
How to add items in a List ?
How to retrieve items from List ?
More about.... C# List
Dictionary Versus HashTable
Dictionary is a generic type, Hashtable is not. That means you get type safety with Dictionary, because you can't insert any random object into it, and you don't have to cast the values you take out. Since both Dictionary and Hashtable are internally hashtables, so fast access to many-item data according to key, also both need immutable and unique keys. More about.... Dictionary Vs HashTable
- Difference between a Value Type and a Reference Type
- System level Exceptions Vs Application level Exceptions
- Difference between sub-procedure and function
- What does the term immutable mean
- What does the keyword static mean
- this.close() Vs Application.Exit()
- Difference between a.Equals(b) and a == b
- Difference between Hashtable and Dictionary
- Difference between Exception and Error
- Difference between the Class and Interface in C#
- Why does C# doesn't support Multiple inheritance