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
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/