In .NET, why must code not rely on Dictionary<TKey,TValue> enumeration order, and when does OrderedDictionary<TKey,TValue> or SortedDictionary<TKey,TValue> fit instead?
answer
- an entries array and a free list
- what Remove leaves behind
- a .NET 9 generic type
- index access has a price
basics
~10 sDictionary<TKey,TValue> promises no enumeration order, and after a Remove the next insertion reuses the freed slot mid-sequence. OrderedDictionary<TKey,TValue> (.NET 9) keeps insertion order with index access; SortedDictionary<TKey,TValue> keeps key order.
solid answer
~40 s`Dictionary<TKey,TValue>` stores entries in an internal array and enumerates that array, so with no removals the order happens to match insertion, which is why tests pass until it changes. `Remove` puts the slot on a free list and the next insertion fills it, so a key added later is yielded in the middle; the type makes no ordering promise either way. When order is a requirement, pick a type that promises one. `OrderedDictionary<TKey,TValue>`, added in .NET 9 in `System.Collections.Generic`, keeps insertion order, keeps hashed key lookup and adds index access: `GetAt`, `SetAt`, `IndexOf`, `Insert`, `RemoveAt`. Its cost is `List<T>`-like: removing or inserting before the end shifts later entries, O(n). When the order should follow the key, `SortedDictionary<TKey,TValue>` or `SortedList<TKey,TValue>` sort by an `IComparer<TKey>`.
code
csharp · 13 linesvar plain = new Dictionary<string, int> { ["A-1-4"] = 12, ["B-2-1"] = 3, ["C-3-7"] = 8 };
plain.Remove("B-2-1");
plain["D-4-2"] = 5; // reuses the freed entry slot
Console.WriteLine(string.Join(", ", plain.Keys)); // A-1-4, D-4-2, C-3-7 (on .NET 10; not a documented order)
var ordered = new OrderedDictionary<string, int> { ["A-1-4"] = 12, ["B-2-1"] = 3, ["C-3-7"] = 8 };
ordered.Remove("B-2-1"); // shifts later entries down: O(n)
ordered["D-4-2"] = 5;
Console.WriteLine(string.Join(", ", ordered.Keys)); // A-1-4, C-3-7, D-4-2
Console.WriteLine(ordered.GetAt(1)); // [C-3-7, 8]
Console.WriteLine(ordered.IndexOf("D-4-2")); // 2
ordered.Insert(0, "Z-9-9", 1);
Console.WriteLine(string.Join(", ", ordered.Keys)); // Z-9-9, A-1-4, C-3-7, D-4-2go deeper
Recall that Dictionary<TKey,TValue> does not promise any enumeration order, and name OrderedDictionary for insertion order and SortedDictionary for key order.
Explain why insertion order seems to hold until a Remove, through the entries array and its free list, and what OrderedDictionary's index access costs on removal.
Catch code and tests that silently depend on Dictionary order, and pick an ordered type by workload, avoiding OrderedDictionary where removals near the front are frequent.
Make order explicit in contracts: when output order is part of an API or file format, the type in the code should promise it, so no runtime change can alter what clients see.
## What Dictionary does when you enumerate it `Dictionary<TKey,TValue>` keeps two internal arrays: **buckets**, which map a hash to the first entry of a chain, and **entries**, which hold each key, value, cached hash code and the index of the next entry in the chain. New entries are appended to the entries array, and `foreach` walks that array from index 0, skipping free slots. That design explains the behaviour people mistake for a guarantee: 1. Insert A, B and C with no removals and enumeration yields A, B, C, because they occupy slots 0, 1 and 2. 2. `Remove("B")` marks slot 1 free and pushes it onto a **free list**. 3. The next insertion, D, takes the free slot instead of appending, so enumeration now yields A, D, C. The .NET 10 run in the example prints exactly that. The type documents no enumeration order at all, so even the A, D, C result is an implementation detail; code that needs an order must choose a type that promises one. ## OrderedDictionary<TKey,TValue> (.NET 9) .NET 9 added the generic `OrderedDictionary<TKey,TValue>` to `System.Collections.Generic` (in the `System.Collections` assembly). It combines a hash index for keys with entries kept in insertion order: - **Lookup by key** is hashed, with complexity similar to `Dictionary<TKey,TValue>`; it takes an `IEqualityComparer<TKey>` like any hashed collection. - **Index access**: `GetAt(int)` returns the `KeyValuePair<TKey,TValue>` at a position, `SetAt` replaces a value by position, `IndexOf(key)` returns a key's position, `Insert(index, key, value)` places a new pair, and `RemoveAt(index)` removes by position. It also implements `IList<KeyValuePair<TKey,TValue>>`. - **Order rules**: a new key goes to the end; assigning to an existing key replaces the value in place without moving it; `Remove` and `RemoveAt` close the gap so later entries move up one position. - **Costs**: the source describes them as `List<T>`-like. `Remove` and `Insert` before the end shift every later entry and fix their bucket indexes, O(n); appending is amortized O(1). - **.NET 10** added `TryAdd(key, value, out int index)` and `TryGetValue(key, out value, out int index)`, so an add-or-update can reuse the index with `SetAt` instead of searching again. ```csharp var counts = new OrderedDictionary<string, int>(); foreach (var bin in new[] { "A-1-4", "B-2-1", "A-1-4" }) { if (!counts.TryAdd(bin, 1, out int index)) // .NET 10 overload counts.SetAt(index, counts.GetAt(index).Value + 1); } // counts: [A-1-4, 2], [B-2-1, 1], still in first-seen order ``` Do not confuse it with the older non-generic `System.Collections.Specialized.OrderedDictionary`, whose keys and values are `object`: value types box, every read needs a cast, and the compiler checks nothing. ## What the order costs inside The type keeps the same kind of entry as `Dictionary<TKey,TValue>`, a key, a value, the cached hash code and the index of the next entry in its bucket chain, but it keeps the entries array **dense and in order**. That is what makes `GetAt(i)` a direct array read, and it is also why removal is expensive: after closing the gap, every shifted entry's bucket chain still points at its old index, so the removal walks each chain to fix it. Compared with `List<T>.RemoveAt`, which only copies elements, an early removal here does that copying plus a chain fix-up per entry. ## Choosing an ordered type | Type | Enumeration order | Key lookup | Insert or remove in the middle | Index access | |---|---|---|---|---| | `Dictionary<TKey,TValue>` | none promised | hashed | n/a | no | | `OrderedDictionary<TKey,TValue>` | insertion | hashed | O(n) shift | yes | | `SortedDictionary<TKey,TValue>` | by key | O(log n) | O(log n) | no | | `SortedList<TKey,TValue>` | by key | O(log n) | O(n) shift | yes | The two sorted types order by an `IComparer<TKey>`, not by when a key arrived, and they never hash. Their trade-off between a tree and a pair of arrays is a question of its own. ## Practical rules - If output order matters, such as a report, a serialized payload a client diffs, or a UI list, say so in the type: `OrderedDictionary<TKey,TValue>` for arrival order, a sorted dictionary for key order. - If only lookups matter, keep `Dictionary<TKey,TValue>`; it is the cheapest and the free-list reuse is part of why removals are O(1). - Avoid `OrderedDictionary<TKey,TValue>` for workloads that remove from the front often; every removal shifts the rest. - On a runtime older than .NET 9, a `Dictionary<TKey,TValue>` plus a `List<TKey>` of keys is the usual hand-rolled substitute, with the same O(n) removal cost.
- Does updating an existing key move it in an OrderedDictionary<TKey,TValue>?No. Assigning through the indexer to a key that already exists replaces the value in place and keeps its position. Only removing the key and adding it again sends it to the end; to move an entry deliberately, use `RemoveAt` and `Insert` at the position you want.
- What does the old System.Collections.Specialized.OrderedDictionary cost compared with the .NET 9 generic one?It stores keys and values as `object`, so value types are boxed, every read needs a cast, and type mistakes surface only at run time. The generic `OrderedDictionary<TKey,TValue>` keeps the same idea, insertion order plus key lookup and index access, with full type safety and no boxing.
- Dictionary<TKey,TValue> always enumerates entries in insertion order.
- OrderedDictionary<TKey,TValue> keeps its keys sorted.
- Removing from OrderedDictionary<TKey,TValue> is O(1), just like Dictionary.
- The generic OrderedDictionary<TKey,TValue> has existed since .NET Framework.
- SortedDictionary<TKey,TValue> preserves the order in which keys were added.
Assumes .NET 10; the generic OrderedDictionary<TKey,TValue> arrived in .NET 9, and .NET 10 added TryAdd and TryGetValue overloads that also return the entry's index.