C# - 二进制搜索(排序)字典

Question

我有一个记录文件，按字母顺序排序:

• 安德鲁·d432
• 本x127
• ...
• ...
• 扎克 b332

第一个字段是人名，第二个字段是一些id。读取文件后，我不需要对数据进行任何更改。

我想将每条记录视为键值对，其中人名是键。我不知道使用哪个类来访问记录(尽可能快)。 Dictionary 没有二进制搜索。另一方面，据我所知，SortedList 和 SortedDictionary 应该只在我需要插入/删除数据时使用。

编辑:澄清一下，我说的只是访问记录，例如:

x = MyDic[Zac]

Answer 1

没有人说明为什么字典是 O(1) 以及为什么它比二进制搜索更快。一方面是字典不按键排序。字典的全部要点是转到键值引用的项的确切*(出于所有实际目的)位置。它不会“搜索”该项目 - 它知道您想要的项目的确切位置。

因此，二分搜索在基于散列的字典上将毫无意义，因为当集合已经确切知道项目的位置时，无需“搜索”该项目。

_{*在哈希冲突的情况下，这并不完全正确，但字典的原则是直接获取项目，任何额外的查找都是一个实现细节，应该很少见。}

On the other hand, as I understand, SortedList and SortedDictionary should be used only when I need to insert/remove data.

当您希望在添加或删除数据时自动对数据进行排序时，应使用它们。请注意，SortedDictionary 失去了“普通”字典的性能增益，因为它现在必须使用键值搜索位置。它的主要用途是允许您按顺序迭代键。

如果您的每个项目都有一个唯一的键值，不需要以任何特定顺序迭代项目，并且想要最快的“获取”性能，那么 Dictionary 是最佳选择。