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

Question

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

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

我想将每个记录视为键值对,其中人名是键.我不知道使用哪个类来访问记录(尽可能快).Dictionary没有二进制搜索.在另一方面,按照我的理解,SortedList并且SortedDictionary只有当我需要插入应该使用/删除数据.

编辑:为了澄清,我说的只是访问记录,如:

x = MyDic[Zac]

Answer 1

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

因此二进制搜索在字典上是没有意义的,因为当集合已经确切地知道它在哪里时,不需要"搜索"项目.

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

在另一方面,按照我的理解,SortedList并且SortedDictionary只有当我需要插入应该使用/删除数据.

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

如果每个项目都有唯一的键值,则不需要按任何特定顺序迭代项目,并希望获得最快的"获取"性能,那么Dictionary就是要走的路.

Answer 2

通常，字典查找将比集合的二进制搜索更快。有两种特定情况是不正确的：

如果列表很小（在我的测试中，少于15个项目（可能少于10个）），那么计算哈希码和执行字典查找的开销将比在数组上进行二进制搜索要慢。但是除了15项内容外，字典查找胜过二进制搜索。
如果存在很多哈希冲突（由于哈希函数错误或词典的负载因子较高），则词典查找会变慢。如果确实很糟糕，那么二进制搜索可能会击败字典查找。

在使用.NET词典处理各种数据的15年中，我从未见过将标准String.GetHashCode()方法与现实世界的数据一起使用时＃2会成为问题。我唯一遇到麻烦的是我创建了一个错误的GetHashCode()方法。