How C# built-in types are implemented internally?

This is a quick guide to internal implementation of such types as Dictionary, Hashtable, List and others.

Data structure Find Add Insert Remove Collisions
Dictionary hash table, uses buckets to solve collisions O(1) O(1)/O(n) n/a O(1) uses buckets for same hash code
SortedDictionary Red-Black tree, uses StoredSet internally O(logn) O(logn) n/a O(logn)
Hashtable O(1)  O(1) O(1) O(1) rehashing
HashSet hastable O(1) O(1)/O(n)  O(1)
SortedSet Red-Black tree O(logn) O(logn) O(logn) O(logn)
List array O(n) O(1) O(n)  O(n)
SortedList array O(logn) O(n) O(n)
Collection array, uses List internally O(n) O(1) O(n) O(n)
Stack  array O(n) O(1) O(n) O(n)

This code you can use to see internal implementation with ILSpy

Dictionary<int, int> dict = new Dictionary<int, int>();
SortedDictionary<int, int> sortedDict = new SortedDictionary<int, int>();
Hashtable hashTbl = new Hashtable();
HashSet<int> set = new HashSet<int>();
SortedSet<int> sortedSet = new SortedSet<int>(); 
List<int> listInt = new List<int>();
SortedList<int, int> listSorted = new SortedList<int, int>();
Collection<int> collInt = new Collection<int>();
Stack<int> stackInt = new Stack<int>();
int[] arrayInt = new[]{1, 2, 3};

Complexity

big-o-complexity

More about complexity: http://bigocheatsheet.com/

See More

Tags:

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Related Post

%d bloggers like this: