两个字典检索对一个键检索的性能

Question

我有这样的遗留代码，其中经常有字符串字典到字符串字典到某个对象的模式。

Dictionary<string, Dictionary<string, someobject>>

然后，对象的检索总是基于两次TryGetValue

Dictionary<string, Dictionary<string, Dealer>> dicDealers ...

if (dicDealers.TryGetValue(lab, out dealers))
  dealers.TryGetValue(dealerNumber, out dealer);

现在，我在想，如果将两个字符串键组合成一个包含两个字符串成员的键结构，那么在一次访问中就可以检索到对象，这样会更有效。因此，我创建了一个键结构，它覆盖GetHashCode，等于计算bots密钥成员的散列。

public struct Key<T>
{
    private T mKey1;
    private T mKey2;

    public Key(T t, T u)
    {
        mKey1 = t;
        mKey2 = u;
    }

    public override bool Equals(object obj)
    {
        if (obj == null) return false;

        Key<T> rhs = (Key<T>)obj;

        return mKey1.Equals(rhs.mKey1) && mKey2.Equals(rhs.mKey2);
    }

    public override int GetHashCode()
    {
        int hash = 17;

        hash = ((hash << 5) - hash) + mKey1.GetHashCode();
        hash = ((hash << 5) - hash) + mKey2.GetHashCode();
        return hash;
    }
}

现在你可以马上做了。

Key<string> key = new Key<string>(lab, dealerNumber);

if (dicDealers.TryGetValue(key, out someobject))
{
...
}

我认为它应该更快，但事实证明，这两种方式差不多一样快。这怎么可能呢？我能做点什么让第二种技术跑得更快吗？

Answer 1

您正在尝试改进一种已摊销O(1)复杂性的方法。这是一个很高的任务，你永远不能比O(1)更高效，没有任何算法是O(1/x)。

你唯一能改进的就是。字典的Oh取决于GetHashCode()的成本和散列代码分布的好坏。你又在打一场很难打赢的仗。String.GetHashCode()是用hand-optimized code编写的，它产生了一个非常好的散列。

实际上，您并没有提高GetHashCode()的效率，它的开销与原始版本中的两个GetHashCode()调用相同。所以是的，你当然应该期待你的版本花费同样多的时间。

试图生产一个更好的版本是一个很长的机会。您必须对字符串有特殊的了解，比如知道一个好的散列只需要第一个字符，这样您就可以在计算整个字符串上的散列时走捷径。这很少见，也有点危险，糟糕的散列代码分发是有害的。最重要的是，这是不必要的。您所犯的核心错误是试图改进不需要改进的代码。只有当分析器告诉您TryGetValue()是关键代码时，才会考虑这样做。