两个字符串的字典重点

Question

我有两个字符串，该ID喜欢用它们作为字典的键，但即时通讯有点懒创建另一个对象，计算串等的哈希码

所以不是说，我可以得到两个字符串的hashcode，添加它们并使用结果作为Dictionary的关键字？

有可能导致碰撞？对？。

任何想法？

Answer 1

我有两个字符串，如以 该ID使用它们作为字典键，但即时通讯 有点懒创建另一个对象

在.NET 4.0中，你可以使用Tuple<T1, T2>类作为键，T1和T2 =字符串。

我可以得到两个字符串 的散列码，添加它们并使用结果作为词典的 关键？

公式Tuple<T1, T2>用来组合哈希码是一样的东西（不记录或保证不变）：((h1 << 5) + h1)^h2，这应该是足够体面的你的目的。顺便说一句，天真添加通常不是组合散列码的最佳方式。

有可能造成碰撞？ 对不对？

这总是可能的，即使是单个字符串。有比32位整数更多的字符串。

Answer 2

使用一个元组：

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

Answer 3

如果你在.NET 4中，你可以使用Tuple类：

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

如果你不是在.NET 4中，需要创建你自己的类型来保存这个。

您可以使用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 principle (Wikipedia)描述。

这意味着，如果两个不同的密钥会引起冲突，它不会是一个问题，他们都会被保存，用正确的价值观，在字典中。

当然，如果您创建两次相同的密钥，字典会将其计为同一个密钥，并且无法添加新值或覆盖现有密钥（具体取决于您如何添加该值。 ）

这将在重复键抛出一个异常：

dict.Add(key, value); 

这将增加，或覆盖现有：

dict[key] = value; 

---

在回应阿尼的评论，我写了下面简单的测试脚本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); 
    } 
} 

Answer 4

简单的解决方案，以及一个与.NET的所有版本。只需将字符串连接在一起即可。

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

当然，这仅与2串工作（尽管你可以在许多其他类型使用的ToString（）），如果你不需要仅由两个字符串中的一个来查找字典，但如果你有两个很简单。