优化查找：字典键查找与数组索引查找
我正在写一个7卡扑克手评估员作为我的宠物项目之一。 在尝试优化速度时（我喜欢挑战），我惊讶地发现，与数组索引查找相比，Dictionary键查找的性能相当慢。
例如，我运行了这个示例代码，列举了所有52个选择7 = 133,784,560个可能的7个牌手：
var intDict = new Dictionary(); var intList = new List(); for (int i = 0; i < 100000; i ++) { intDict.Add(i, i); intList.Add(i); } int result; var sw = new Stopwatch(); sw.Start(); for (int card1 = 0; card1 < 46; card1++) for (int card2 = card1 + 1; card2 < 47; card2++) for (int card3 = card2 + 1; card3 < 48; card3++) for (int card4 = card3 + 1; card4 < 49; card4++) for (int card5 = card4 + 1; card5 < 50; card5++) for (int card6 = card5 + 1; card6 < 51; card6++) for (int card7 = card6 + 1; card7 < 52; card7++) result = intDict[32131]; // perform C(52,7) dictionary key lookups sw.Stop(); Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds); sw.Reset(); sw.Start(); for (int card1 = 0; card1 < 46; card1++) for (int card2 = card1 + 1; card2 < 47; card2++) for (int card3 = card2 + 1; card3 < 48; card3++) for (int card4 = card3 + 1; card4 < 49; card4++) for (int card5 = card4 + 1; card5 < 50; card5++) for (int card6 = card5 + 1; card6 < 51; card6++) for (int card7 = card6 + 1; card7 < 52; card7++) result = intList[32131]; // perform C(52,7) array index lookups sw.Stop(); Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds); 哪个输出：
time for dictionary lookups: 2532 ms time for array index lookups: 313 ms
是否期望这种行为（性能下降8倍）？ IIRC，一个字典平均有O（1）查找，而一个数组有最坏情况的O（1）查找，所以我确实希望数组查找更快，但不是这么多！
我目前正在将字典中的扑克手牌排名存储起来。 我想如果这和字典查找一样快，我必须重新考虑我的方法并使用数组，虽然索引排名会有点棘手，我可能不得不问另一个问题。
不要忘记Big-O符号只说明复杂程度如何随着大小（等）而增长 – 它没有给出任何涉及的常数因素的指示。 这就是为什么有时甚至线性搜索键比字典查找更快，因为键足够少。 在这种情况下，你甚至不用数组进行搜索 – 只是一个直接的索引操作。
对于直接索引查找，数组基本上是理想的 – 它只是一个例子
pointer_into_array = base_pointer + offset * size
（然后指针取消引用。）
执行字典查找相对复杂 – 与有很多键时按键进行线性查找相比非常快，但比直接数组查找要复杂得多。 它必须计算密钥的哈希值，然后确定应该在哪个桶中，可能处理重复的哈希值（或重复的桶），然后检查是否相等。
像往常一样，为作业选择正确的数据结构 – 如果你真的可以通过索引到一个数组（或List ），那么是的，这将是非常快的。
是否期望这种行为（性能下降8倍）？
为什么不？ 每个数组查找几乎是临时/可忽略的，而字典查找可能至少需要一个额外的子程序调用。
它们都是O（1）的意思是，即使你在每个集合中有50倍的项目，性能下降仍然只是它的一个因素（8）。
有些东西可能需要一个千年，而且仍然是O（1）。
如果您在反汇编窗口中单步执行此代码，您将很快了解其中的区别。
当密钥空间非常大并且无法映射到稳定的顺序顺序时，字典结构最有用。 如果您可以将键转换为相对较小范围内的简单整数，那么您将很难找到比数组更好的数据结构。
关于实施说明; 在.NET中，字典基本上是哈希。 通过确保密钥散布到大量独特值的空间中，您可以在某种程度上提高其密钥查找性能。 看起来在你的情况下，你使用一个简单的整数作为键（我相信哈希值自己的值） – 所以这可能是你能做的最好的。
数组查找是关于你能做的最快的事情 – 基本上它只是从数组的开头到你想要找到的元素的一位指针算术。 另一方面，字典查找可能会稍微慢一点，因为它需要进行散列并关注自己寻找正确的存储桶。 虽然预期的运行时间也是O（1） – 但算法常量更大，因此速度会更慢。
欢迎使用Big-O表示法。 你总是要考虑到有一个常数因素。
做一个Dict-Lookup当然比数组查找要贵得多。
Big-O只告诉你算法如何扩展。 将查找量加倍并查看数字如何变化：两者都需要两次左右。
从Dictionary中检索元素的成本是O（1） ，但这是因为字典被实现为哈希表 – 所以你必须首先计算哈希值以知道要返回哪个元素。 Hashtables通常效率不高 – 但它们适用于大型数据集或具有大量唯一哈希值的数据集。
列表（除了是用于编写数组而不是链表的垃圾词之外！）将更快，因为它将通过直接计算您想要返回的元素来返回值。