C#字典在删除同一个键后没有在最后一个索引处添加新项

Dictionary<string, byte> test = new Dictionary<string, byte>();
test.Add("c", 1);  // [{"c", 1}]
test.Add("b", 2);  // [{"c", 1}, {"b", 2}]
test.Add("a", 3);  // [{"c", 1}, {"b", 2}, {"a", 3}]
test.Remove("b");  // [{"c", 1}, {"a", 3}]
test.Add("b", 2);  // [{"c", 1}, {"b", 2}, {"a", 3}] <= why this happen?
                   // [{"c", 1}, {"a", 3}, {"b", 2}] and not this?

字典是哈希表。如果您查看哈希表的定义，您会注意到哈希表是无序的。

我已经有一段时间没有研究.NET字典实现的具体细节了，所以在我的故事的其余部分中可能会有一些错误——但这是我从细节中记住的：

实现哈希表有很多不同的方案，但.NET使用的方案类似于"开放寻址"算法，但也有一些变体。基本上，新项目会添加到列表（末尾），哈希表（静态数组）会在该列表中添加指针。这就是为什么它实际上似乎维护了秩序。

在某个时刻，由于修改或增长，数据将充满"垃圾"。在这一点上，该实施将做一次重洗。如果我没有记错的话，这也是它检查是否有太多碰撞的点——如果是这样的话，它将使用随机素数来乘以所有哈希值（从而减少碰撞的数量）。它真的很优雅。

由于开放寻址方案指向列表中的元素，因此列表中的顺序并不重要。当你列举一本字典时，你基本上是看这个列表。

您可能想知道为什么它不枚举哈希代码数组。嗯，哈希表通常被过度分配，数据无论如何都存储在另一个列表中。这只是意味着这种替代方案的效率会低得多。如果枚举哈希表，您可能也会得到更一致的结果，但由于冲突，仍然无法得到完全一致的结果。（例如，如果A和B在同一个散列码上，则插入顺序将决定A是跟在B后面，还是反之亦然）。

如果您正在寻找像"集合并集"这样需要一致排序的算法，我建议使用SortedDictionary这样的容器。

您可以在这里看到Dictionary类的实现代码

正如您所看到的，该实现使用了一种跟踪条目数组中空闲位置列表的技术，当添加新值时，首先使用空闲条目。

框架中有一个非通用的ListDictionary类，我相信它总是在列表的末尾添加新项。请记住，对IDictionary实现的访问通常平均为O（n），而对您当前使用的通用Dictionary的访问则平均为0（1）。

我们可以通过创建一个新的字典并向其中添加值来实现这一点。

// you can run this code here: https://www.programiz.com/csharp-programming/online-compiler/
// Online C# Editor for free
// Write, Edit and Run your C# code using C# Online Compiler
using System;
using System.Collections.Generic;
public class HelloWorld
{
    public static void Main(string[] args)
    {
        
        var cities = new Dictionary<string, string>(){
            {"UK", "London, Manchester, Birmingham"},
            {"USA", "Chicago, New York, Washington"},
            {"India", "Mumbai, New Delhi, Pune"}
        };
        
        //creating a new dictionary
        var newVersion = new Dictionary<string, string>();
        
        //print all the values exist in the cities
        Console.WriteLine("..............Initial values in cities 'n");
        foreach (var kvp in cities) {
            Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
        }
        
        cities.Remove("UK"); // removes UK 
        
        //print all the values in the cities after removing "UK" and also add each value to the new dictionary
        Console.WriteLine("'n ..............Values in cities after removal");
        foreach (var kvp in cities) {
            Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
            newVersion[kvp.Key] = kvp.Value;
        }
        
        //add new key value pairs to cities and new dictionary
        cities["test"] = "test1";
        cities["test2"] = "test2";
        newVersion["test"] = "test1";
        newVersion["test2"] = "test2";
        
        //print values in the old dictionary
        Console.WriteLine("'n..............Values in cities after adding new test values");
        foreach (var kvp in cities) {
            Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
        }
        
        //print values in the new dictionary. New dictionary will add the values at the end
        Console.WriteLine("'n..............New version");
        foreach (var kvp in newVersion) {
            Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
            
        }
    }
}

**Sample output:**
..............**Initial values in cities**    
Key = UK, Value = London, Manchester, Birmingham
Key = USA, Value = Chicago, New York, Washington
Key = India, Value = Mumbai, New Delhi, Pune
 ..............**Values in cities after removal**
Key = USA, Value = Chicago, New York, Washington
Key = India, Value = Mumbai, New Delhi, Pune
..............**Values in cities after adding new test values**
Key = test, Value = test1
Key = USA, Value = Chicago, New York, Washington
Key = India, Value = Mumbai, New Delhi, Pune
Key = test2, Value = test2
..............**New version**
Key = USA, Value = Chicago, New York, Washington
Key = India, Value = Mumbai, New Delhi, Pune
Key = test, Value = test1
Key = test2, Value = test2