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