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

Complexity

big-o-complexity

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

See More




No Comments


You can leave the first : )



Leave a Reply