dos cadenas de clave de un diccionario

Question

tengo dos cuerdas, ese id les gusta usarlos como la clave de diccionario, pero soy un poco perezoso para crear otro objeto, calcular el código hash de las cuerdas etc.

Así que en lugar de eso ¿Puedo obtener los códigos hash de dos cadenas, agregarlas y usar el resultado como la clave del Diccionario?

¿Es posible causar colisiones? ¿derecho?.

¿Alguna idea?

Answer 1

que tiene dos cuerdas, que como seria los usan como la clave de diccionario, pero soy un poco perezoso para crear otro objeto

En .NET 4.0, puede utilizar la clase como el Tuple<T1, T2> clave, con T1 y T2 = cadena.

puedo obtener los hashcodes de dos cuerdas , añadirlos y utilizar el resultado como la clave del diccionario?

La fórmula Tuple<T1, T2> utiliza para combinar los códigos hash es algo similar (no documentado o garantizados no cambiar): ((h1 << 5) + h1)^h2, que debe ser lo suficientemente decente para sus propósitos. Por cierto, agregar ingenuamente no es normalmente la mejor manera de combinar códigos hash.

¿Es posible causar colisiones? ¿derecho ?.

Esto siempre es posible, incluso con un solo cadena. Hay más cadenas que enteros de 32 bits.

Answer 2

Usar una tupla:

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

Answer 3

Si estás en .NET 4, puede utilizar la clase Tuple:

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

Si no estás en .NET 4, que debiera crea tu propio tipo para sostener esto.

Puede usar la estructura KeyValuePair, pero hereda los métodos relevantes del tipo de valor base y, por lo tanto, depende en gran medida de la reflexión. Esto tiene implicaciones en el rendimiento (ver parte inferior de respuesta.)

Para KeyValuePair:

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

Aquí es un tipo general se puede utilizar si no quiere cocinar tú mismo:

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

Por supuesto, KeyValuePair también funciona en .NET 4.0 igual que bueno malo.

En cuanto a las colisiones, depende de lo que signifique. Una tabla hash (un diccionario utiliza una estructura hashtable internamente) siempre tiene la posibilidad de obtener colisiones clave, pero es ahí donde entra en juego la comparación.Si dos claves distintas generan el mismo código hash, la clase del diccionario comparará la clave contra la clave para ver si realmente son los mismos valores, o simplemente producirá el mismo código hash.

El razonamiento detrás de por qué una tabla hash siempre tendrá la posibilidad de colisiones se describe mejor con el pidgeonhole principle (Wikipedia).

Esto significa que si dos teclas diferentes causarían una colisión, no sería un problema, ambas se almacenarán, con los valores correctos, en el diccionario.

Por supuesto, si crea la misma clave dos veces, el diccionario la contará como la misma clave y no podrá agregar un nuevo valor, o sobrescribirá el existente (dependiendo de cómo lo solicite para agregar el valor).)

Esto producirá una excepción en duplicados de las llaves:

dict.Add(key, value); 

Esto agregará o sobrescribir existente:

dict[key] = value; 

---

En respuesta al comentario de Ani, escribí el siguiente script de prueba simple para LINQPad. La salida fue:

 
KeyValuePair: 975ms 
MyKeyValuePair: 52ms

guión:

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

solución simple, y uno que funciona con todas las versiones de .NET. Simplemente concatena las cuerdas juntas.

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

Por supuesto, esto sólo funciona con 2 cadenas (aunque se puede utilizar .ToString() en muchos otros tipos) y si no es necesario buscar el diccionario por una sola de las dos cadenas, pero si tienes ambos es bastante simple.