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
Complexity
More about complexity: http://bigocheatsheet.com/