09
- December
2015
No Comments
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(log_{n}) | O(log_{n}) | n/a | O(log_{n}) | |
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(log_{n}) | O(log_{n}) | O(log_{n}) | O(log_{n}) | |
List | array | O(n) | O(1) | O(n) | O(n) | |
SortedList | array | O(log_{n}) | 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
1 2 3 4 5 6 7 8 9 10 11 12 |
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
More about complexity: http://bigocheatsheet.com/