一个字典的键需要两个字符串

Question

我有两个字符串，我想将它们用作字典键，但我懒得创建另一个对象，计算字符串的哈希码等。

所以，可以获取两个字符串的哈希码，将它们相加，然后使用结果作为字典的键吗？

这样做可能会导致冲突吗？

你有什么想法？

- DarthVader

---

你使用的是哪个 .NET 版本？ - Lasse V. Karlsen

Answer 1

我有两个字符串，我想把它们用作字典键，但我有点懒得再创建另一个对象。

在.NET 4.0中，您可以使用Tuple<T1, T2>类作为键，其中T1和T2 = string。

我能获取两个字符串的哈希码，将它们相加并将结果用作字典的键吗？

用于组合哈希码的Tuple<T1, T2>公式大约如下（未记录或保证不会更改）：((h1 << 5) + h1) ^ h2，这对于您的目的而言应该足够好了。顺便说一句，朴素地添加不是通常结合哈希码的最佳方式。

这可能会导致冲突吗？

这总是可能的，即使只有一个字符串也是如此。字符串的数量超过32位整数的数量。

- Ani

Answer 2

如果您正在使用.NET 4，您可以使用Tuple类：

Dictionary<Tuple<string, string>, TValue> dict = new ...

如果您没有使用.NET 4，您应该创建自己的类型来保存这个。

您可以使用KeyValuePair结构体，但它会继承相关的基本值类型方法，并且因此严重依赖于反射。这对性能有影响（请参见答案底部）。

对于KeyValuePair：

Dictionary<KeyValuePair<string, string>, TValue> dict = new ...

如果您不想自己编写，可以使用以下通用类型：

public struct SimpleTuple<TValue1, TValue2>
{
    private readonly TValue1 _Value1;
    private readonly TValue2 _Value2;

    public SimpleTuple(TValue1 value1, TValue2 value2)
    {
        _Value1 = value1;
        _Value2 = value2;
    }

    public TValue1 Value1 { get { return _Value1; } }
    public TValue2 Value2 { get { return _Value2; } }

    public int GetHashCode()
    {
        unchecked
        {
            int result = 37;

            result *= 23;
            if Value1 != null)
                result += Value1.GetHashCode();

            result *= 23;
            if (Value2 != null)
                result += Value2.GetHashCode();

            return result;
        }
    }

    public override bool Equals(object obj)
    {
        if (obj == null) return false;
        if (obj.GetType() != typeof(SimpleTuple<TValue1, TValue2>))
            return false;

        var other = (SimpleTuple<TValue1, TValue2>)obj;
        return Equals(other.Value1, Value1) && Equals(other.Value2, Value2);
    }
}

当然，KeyValuePair也在.NET 4.0上同样适用。

至于碰撞，这取决于您的意思。哈希表（字典在内部使用哈希表结构）总是有可能发生键碰撞，但这就是比较发挥作用的地方。如果两个不同的键生成相同的哈希码，则字典类将比较键以查看它们是否真正是相同的值，或者只是产生相同的哈希码。

哈希表始终具有发生碰撞的可能性的原因最好用鸽笼原理（维基百科）来描述。

这意味着如果您有两个不同的键会导致碰撞，那么这不是问题，它们都将存储在字典中，具有正确的值。

当然，如果您两次创建相同的键，则字典将将其视为相同的键，并且无论如何都会失败添加新值或覆盖现有值（取决于您如何要求添加该值）。

这将在重复键上引发异常：

dict.Add(key, value);

这将添加或覆盖现有内容：

dict[key] = value;

---

回应Ani的评论，我为LINQPad编写了以下简单的测试脚本。输出结果如下：

KeyValuePair: 975毫秒
MyKeyValuePair: 52毫秒

脚本：

void Main()
{
    const int iterations = 10 * 1000 * 1000;

    // JIT preheat
    Test1(1);
    Test2(1);

    Stopwatch sw = Stopwatch.StartNew();
    Test1(iterations);
    sw.Stop();
    Debug.WriteLine("KeyValuePair: " + sw.ElapsedMilliseconds + "ms");

    sw = Stopwatch.StartNew();
    Test2(iterations);
    sw.Stop();
    Debug.WriteLine("MyKeyValuePair: " + sw.ElapsedMilliseconds + "ms");
}

public static void Test1(int iterations)
{
    for (int index = 0; index < iterations; index++)
    {
        var kvp = new KeyValuePair<int, int>(index, index);
        kvp.GetHashCode();
    }
}

public static void Test2(int iterations)
{
    for (int index = 0; index < iterations; index++)
    {
        var kvp = new MyKeyValuePair<int, int>(index, index);
        kvp.GetHashCode();
    }
}

public struct MyKeyValuePair<TKey, TValue>
{
    private readonly TKey _Key;
    private readonly TValue _Value;

    public MyKeyValuePair(TKey key, TValue value)
    {
        _Key = key;
        _Value = value;
    }

    public TKey Key { get { return _Key; } }
    public TValue Value { get { return _Value; } }

    public int GetHashCode()
    {
        unchecked
        {
            int result = 37;

            result *= 23;
            if (Key != null)
                result += Key.GetHashCode();

            result *= 23;
            if (Value != null)
                result += Value.GetHashCode();

            return result;
        }
    }

    public override bool Equals(object obj)
    {
        if (obj == null) return false;
        if (obj.GetType() != typeof(MyKeyValuePair<TKey, TValue>))
            return false;

        var other = (MyKeyValuePair<TKey, TValue>)obj;
        return Equals(other.Key, Key) && Equals(other.Value, Value);
    }
}

- Lasse V. Karlsen

---

有使用KVP作为键的经验吗？我想知道性能如何，考虑到相等性和哈希码计算应该来自于System.ValueType，因为它似乎没有覆盖它们。 - Ani

我没有直接测量过这一点，但在性能分析中，我从未遇到过字典是主要罪犯的情况。它可能比手动编写具有特定方法的类型慢得多。让我这样做，然后回来编辑。 - Lasse V. Karlsen

@Ani，你说得对，KeyValuePair 不是一个好的选择。我会编辑我的答案。 - Lasse V. Karlsen

你为什么没有为元组添加测试呢？你在回答中建议使用元组，但却没有对其进行度量。我进行了与你对 KeyValuePair 所做的类似测试，但它的性能甚至更差。 - Meta-Knight

我实在记不清了。如果你有更新的测试，请随意编辑我的答案。目前我正在病假期间，只能使用虚拟机来运行它，所以结果可能不太准确。 - Lasse V. Karlsen

Answer 3

使用元组：

var dict = new Dictionary<Tuple<string,string>,SomeType>();
dict.Add(Tuple.Create("Hello","World"), new SomeType());

- mancaus

Answer 4

一个简单的解决方案，适用于所有版本的.net。只需将字符串连接起来即可。

var dictionary = new Dictionary<string, int>();
dictionary.Add("The meaning" + " of life, the universe, and everything", 42);

当然，这只适用于2个字符串（虽然您可以在许多其他类型上使用.ToString（）），如果您不需要仅使用两个字符串之一查找字典，但如果您拥有两者，那么它就非常简单。

- Erik Funkenbusch

---

我要补充的是，如果两个字符串中没有出现某些字符，这种技术才会起作用。例如名字和姓氏。它们两个都不应该有 \n（换行符）。因此，Name\nSurname 就已经“足够好了”（请注意，一些狡猾的黑客可能会利用它来攻击您的网站！虽然很难，但并非不可能）。考虑到许多系统都是基于 C 的，所以使用字符 \0 应该相当安全。（或者您可以简单地转义任何分隔字符串时所使用的字符，例如：Name.Replace("|", "||") + "|" + Surname） - xanatos