C# Dictionary Versus List Lookup Time

Both lists and dictionaries serve as data structures for storing collections of data in the .NET framework. Although Dictionary< int, T > and List < T > have similarities as random access data structures, they differ in their underlying mechanisms for data retrieval. The Dictionary is implemented using a hash table, using a hash lookup algorithm that offers efficient searching capabilities. In contrast, a list requires sequential traversal of elements until the desired result is found, which can be less efficient in terms of performance when compared to a hash table.

Dictionary vs List perfomances in C#

When comparing the data structures of Dictionary and List, it is evident that Dictionary provides a more consistent lookup time regardless of the size of the collection. The Dictionary utilizes a hashing technique to efficiently search for data. Initially, a hash value is calculated for the key, leading to the corresponding data bucket. Subsequently, each element within the bucket is checked for equality. On the other hand, the List may initially perform faster than the Dictionary during the first item search since there is no need for a search operation at that stage. However, as subsequent items are searched, the List needs to traverse through each element sequentially, resulting in increased lookup time. This time complexity is denoted as O(n), where 'n' represents the number of elements in the List. In contrast, the Dictionary maintains a constant lookup time of O(1), ensuring faster retrieval of data.

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:

Dictionary<string, int> dictionary = new Dictionary<string, int>(); List<int> newList = new List<int>();

Add data to the list

newList.Add(data);

A list cam simply add the item at the end of the existing list item.

Add data to the Dictionary

dictionary.Add(key, data);

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 ?

Dictionary in C# vb.net

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 ?

Dictionary<string, int> dictionary = new Dictionary<string, int>(); dictionary.Add("first", 1); dictionary.Add("second", 2);

Retrieve items from dictionary

foreach (KeyValuePair<string, int> items in dictionary) { MessageBox.Show(items.Key.ToString ()+ " - " + items.Value.ToString () ); }

More about.... C# Dictionary

What is a List ?

list in C# vb.net

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 ?

List<int> newList = new List<int>(); newList.Add(10); newList.Add(20); newList.Add(30); newList.Add(40);

How to retrieve items from List ?

foreach (string day in week) { MessageBox.Show(day); }

More about.... C# List






Related Topics
  1. Difference between a Value Type and a Reference Type
  2. System level Exceptions Vs Application level Exceptions
  3. Difference between sub-procedure and function
  4. What does the term immutable mean
  1. What does the keyword static mean | C#
  2. this.close() Vs Application.Exit()
  3. Difference between a.Equals(b) and a == b
  4. Difference between Hashtable and Dictionary
  5. Difference between Error and Exception
  6. Difference between the Class and Interface in C#
  7. Why does C# doesn't support Multiple inheritance
  8. How to get the URL of the current page in C# - Asp.Net?