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



More about complexity:

See More


Leave a Reply

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

Related Post

%d bloggers like this: