字典键的两个字符串

Question

我有两个字符串,id喜欢使用它们作为字典键,但我有点懒惰创建另一个对象,计算字符串的哈希码等.

所以不是那样,我可以获得两个字符串的哈希码,添加它们并使用结果作为字典的键吗？

有可能引起碰撞吗？对？.

有任何想法吗？

Answer 1

我有两个字符串,id喜欢使用它们作为字典键,但我有点懒惰创建另一个对象

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

我可以获取两个字符串的哈希码,添加它们并使用结果作为字典的键吗？

Tuple<T1, T2>用于组合哈希码的公式类似于(没有记录或保证不会改变):((h1 << 5) + h1) ^ h2这应该足以满足您的需要.顺便说一句,天真添加通常不是组合哈希码的最佳方式.

有可能引起碰撞吗？对？.

这始终是可能的,即使有一个单一的字符串.字符串多于32位整数.

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一样好不好.

至于碰撞,这取决于你的意思.哈希表(字典在内部使用哈希表结构)总是有可能获得关键冲突,但这就是比较发挥作用的地方.如果两个不同的键生成相同的哈希码,则字典类将比较键与键,以查看它们是否真的是相同的值,或者只生成相同的哈希码.

pidgeonhole原则(维基百科)最好地描述了哈希表总是有可能发生碰撞的原因.

这意味着如果你有两个不同的键会导致碰撞,那就不会有问题,它们都会以正确的值存储在字典中.

当然,如果您创建两次相同的密钥,字典会将其计为相同的密钥,并且无法添加新值,或覆盖现有密钥(取决于您要求它添加值的方式.)

这将在重复键上抛出异常:

dict.Add(key, value);

这将添加或覆盖现有的:

dict[key] = value;

为了回应Ani的评论,我为LINQPad编写了以下简单的测试脚本.输出是:

KeyValuePair: 975ms
MyKeyValuePair: 52ms

脚本:

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);
    }
}