就地按键对字典排序

Question

我有一个C#字典

Dictionary<Person, int>

我希望可以就键（Person类中的一个字段）对该字典进行原地排序。我该怎么做？互联网上提供的所有帮助都是关于列表的，没有特定的字典原地排序示例。非常感谢任何帮助！

- SoulReaver

---

我不确定我理解你的问题，因为字典没有枚举顺序？您可以通过键或值进行迭代，并可以轻松在运行时对它们进行排序... - Rowland Shaw

这不可能是你真正想要的。数组可以原地排序，因为排序数组的结果是一个数组。但字典不是一个数组，所以不能用排序其条目的结果来替换它。请对条目进行排序并将结果保存在数组或列表中。而且被接受的答案可能不是你想要的...从 SortedList 或 SortedDictionary 输入和访问条目比从 Dictionary 要慢得多。 - Jim Balter

Answer 1

你无法对 Dictionary<TKey, TValue> 进行排序 - 它本身是无序的。(或者更确切地说，检索条目的顺序是实现特定的。你不应该依赖它在版本之间以相同的方式工作，因为排序不是其设计功能的一部分。)

你可以使用 SortedList<TKey, TValue> 或 SortedDictionary<TKey, TValue>，两者都通过键值 (如果将 IEqualityComparer<T> 传递到构造函数中，则可以进行可配置排序) 进行排序 - 它们可能对你有用?

不要太关注名称 SortedList 中的 "list" 这个词 - 它仍然是一个将键映射到值的字典。它的内部实现使用了一个列表，因此它执行二进制搜索而不是哈希码查找。SortedDictionary 同样基于二进制搜索，但是通过树而不是列表进行。

- Jon Skeet

---

使用SortedList<K,V>时要小心，如果构建一个大列表（假设项目未经预排序），它将非常慢。通常应改用SortedDictionary<K,V>，或使用第三方BDictionary<K,V>以获得类似于SortedDictionary的性能，而不会失去按索引访问项目或“查找最近键”的能力。 - Qwertie

二分查找相比于维护一个散列表和排序键，有什么优势？如果我不是几乎完全在进行有序枚举，为什么我要关心元素的顺序呢？如果我更关心单个元素的查找，但次要地想根据键的顺序进行枚举，那么我是否需要像Steve的回答中所述一样管理一个单独的键列表？如果这是我的预期用途，SortedList和SortedDictionary实际上是错误的工具，对吗？也就是说，如果我只想原地排序字典的键，该怎么办？ - ruffin

@ruffin：优点在于避免复杂性。据我所知，没有内置的“排序和哈希”集合。请注意，这样的集合更难使用和构建——需要提供相等比较和哈希码函数，以及排序函数。当然，同时保持两个集合也会有内存成本。您需要测量二分搜索与哈希查找在实际数据中的成本——您可能会发现，除非您的集合非常大，否则实际上并不重要。 - Jon Skeet

@ruffin “使用二分查找与维护排序键哈希表相比的优势是什么？” - 哈希表所占用的内存和添加或删除条目时维护哈希表的时间。“为什么我关心元素的顺序” - 如果您不关心元素的顺序，则只需使用Dictionary（通常我会推荐其优先于SortedList或SortedDictionary），“但次要地想要基于键的顺序进行枚举” - 当需要时，对枚举的KeyValuePairs进行排序是微不足道的：dict.OrderBy(kv => kv.Key)。 - Jim Balter

@ruffin "如果我真的只想原地排序字典键怎么办？" -- 这是一个范畴错误，不存在这样的事情。数组可以原地排序...但不是数组的东西就不能。 （好吧，除了具有可变节点的链表之外，但在原地对这种东西进行排序是疯狂且非常昂贵的。）但是当然你可以做类似于 var array = dict.Keys.ToArray(); array.Sort(); 的事情。 - Jim Balter

@ruffin "我是否需要像Steve的回答一样管理一个单独的键列表？" -- 他的回答中没有“单独的键列表”...只有dict.Keys...虽然通常最好通过dict.OrderBy(kv => kv.Key)来操作KeyValuePairs。 - Jim Balter

Answer 2

尝试使用 SortedDictionary。

- Chris O

---

你的回答比God慢了21秒，这还好。 - RBT

Answer 3

由于这个答案在搜索中排名很高，我认为展示LINQ OrderBy解决方案是值得的：

class Person
{
    public Person(string firstname, string lastname)
    {
        FirstName = firstname;
        LastName = lastname;
    }
    public string FirstName { get; set; }
    public string LastName { get; set; }
}

static void Main(string[] args)
{
    Dictionary<Person, int> People = new Dictionary<Person, int>();

    People.Add(new Person("John", "Doe"), 1);
    People.Add(new Person("Mary", "Poe"), 2);
    People.Add(new Person("Richard", "Roe"), 3);
    People.Add(new Person("Anne", "Roe"), 4);
    People.Add(new Person("Mark", "Moe"), 5);
    People.Add(new Person("Larry", "Loe"), 6);
    People.Add(new Person("Jane", "Doe"), 7);

    foreach (KeyValuePair<Person, int> person in People.OrderBy(i => i.Key.LastName))
    {
        Debug.WriteLine(person.Key.LastName + ", " + person.Key.FirstName + " - Id: " + person.Value.ToString());
    }
}

输出：

Doe, John - Id: 1
Doe, Jane - Id: 7
Loe, Larry - Id: 6
Moe, Mark - Id: 5
Poe, Mary - Id: 2
Roe, Richard - Id: 3
Roe, Anne - Id: 4

在这个例子中，使用ThenBy对名字进行排序也是有意义的:

foreach (KeyValuePair<Person, int> person in People.OrderBy(i => i.Key.LastName).ThenBy(i => i.Key.FirstName))

然后输出结果为：

Doe, Jane - Id: 7
Doe, John - Id: 1
Loe, Larry - Id: 6
Moe, Mark - Id: 5
Poe, Mary - Id: 2
Roe, Anne - Id: 4
Roe, Richard - Id: 3

LINQ还有OrderByDescending和ThenByDescending，为那些需要它的人提供帮助。

- Daniel S. Fowler

---

这并不是真正地对字典进行排序，而是在使用字典时对其进行排序。 - Lawrence Thurman

Answer 4

正确答案已经给出（只需使用SortedDictionary）。

然而，如果你必须将你的集合作为字典保留，也有可能以有序方式访问字典的键，例如，通过将键排序到列表中，然后使用此列表来访问字典。示例...

Dictionary<string, int> dupcheck = new Dictionary<string, int>();

...填充“dupcheck”变量的一些代码，然后...

if (dupcheck.Count > 0) {
  Console.WriteLine("\ndupcheck (count: {0})\n----", dupcheck.Count);
  var keys_sorted = dupcheck.Keys.ToList();
    keys_sorted.Sort();
  foreach (var k in keys_sorted) {
    Console.WriteLine("{0} = {1}", k, dupcheck[k]);
  }
}

不要忘记为此使用System.Linq;。

- Steve Greene

---

如果你碰巧需要将你的集合保留为字典，那么显而易见的原因是它具有更快的插入、删除和查找速度。至于 var keys_sorted = dupcheck.Keys.ToList(); keys_sorted.Sort(); -- 更简单的方法是 keys_sorted = dupcheck.Keys.OrderBy(k => k).ToList(); ... 如果你要使用值，那么只需 foreach (var ent in dupcheck.OrderBy(kv => kv.Key)) Console.WriteLine($"{ent.Key} = {ent.Value}"); - Jim Balter

这不是对字典对象的排序，只是对显示的排序，而且是一种变通方法 :( - Ambuj

Answer 5

按照设计，字典是不可排序的。如果您需要在字典中进行排序，请考虑使用SortedDictionary。

- Scott Dorman

Answer 6

虽然Dictionary是通过哈希表实现的，但SortedDictionary是通过红黑树实现的。

如果你的算法没有利用数据的顺序，只需要在输出前对数据进行排序，使用SortedDictionary会对性能产生负面影响。

你可以这样“排序”字典：

Dictionary<string, int> dictionary = new Dictionary<string, int>();
// algorithm
return new SortedDictionary<string, int>(dictionary);

- Draex_

---

如果想按键排序条目，只需使用 dictionary.OrderBy(kv => kv.Key)。 - Jim Balter

Answer 7

看一下SortedDictionary，甚至有一个构造函数重载，这样你就可以传入自己的IComparable进行比较。

- Dave D