How C# built-in types are implemented internally?

This is a quick guide to internal implementation of such C# 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

No Comments

You can leave the first : )

Leave a Reply