C# hashcode para una matriz de ints

Question

Tengo una clase que internamente es solo una matriz de enteros. Una vez construido, la matriz nunca cambia. Me gustaría precomputar un buen hashcode para que esta clase se pueda usar de manera muy eficiente como clave en un diccionario. La longitud de la matriz es inferior a unos 30 elementos, y los enteros están entre -1000 y 1000 en general.

Answer 1

No es muy inteligente, pero suficiente a efectos prácticos:

EDIT: cambiado debido a los comentarios de Henk Holterman, gracias por eso.

int hc=array.Length; 
for(int i=0;i<array.Length;++i) 
{ 
    hc=unchecked(hc*314159 +array[i]); 
} 
return hc; 

Si necesita algo más sofisticado, look here.

Answer 2

Creo que elegir un buen algoritmo hash tendría que basarse en la distribución (en un sentido de probabilidad) de los valores enteros.

Tenga una mirada en Wikipedia para obtener una lista de algoritmos

Answer 3

Cualquier CRC (o incluso XOR) debería estar bien.

Answer 4

Para una matriz de valores generalmente entre -1000 y 1000, probablemente usar algo como esto:

static int GetHashCode(int[] values) 
{ 
    int result = 0; 
    int shift = 0; 
    for (int i = 0; i < values.Length; i++) 
    { 
     shift = (shift + 11) % 21; 
     result ^= (values[i]+1024) << shift; 
    } 
    return result; 
} 

Answer 5

Usted puede utilizar CRC32 checksum. Aquí está el código:

[CLSCompliant(false)] 
public class Crc32 { 
    uint[] table = new uint[256]; 
    uint[] Table { get { return table; } } 

    public Crc32() { 
     MakeCrcTable(); 
    } 
    void MakeCrcTable() { 
     for (uint n = 0; n < 256; n++) { 
      uint value = n; 
      for (int i = 0; i < 8; i++) { 
       if ((value & 1) != 0) 
        value = 0xedb88320^(value >> 1); 
       else 
        value = value >> 1; 
      } 
      Table[n] = value; 
     } 
    } 
    public uint UpdateCrc(uint crc, byte[] buffer, int length) { 
     uint result = crc; 
     for (int n = 0; n < length; n++) { 
      result = Table[(result^buffer[n]) & 0xff]^(result >> 8); 
     } 
     return result; 
    } 
    public uint Calculate(Stream stream) { 
     long pos = stream.Position; 
     const int size = 0x32000; 
     byte[] buf = new byte[size]; 
     int bytes = 0; 
     uint result = 0xffffffff; 
     do { 
      bytes = stream.Read(buf, 0, size); 
      result = UpdateCrc(result, buf, bytes); 
     } 
     while (bytes == size); 
     stream.Position = pos; 
     return ~result; 
    } 
} 

Answer 6

Puede tomar un enfoque diferente y utilizar un diccionario recursivo para cada valor en su matriz int. De esta manera, puede dejar .net para hacer hashing de tipo primitivo.

internal class DictionaryEntry<TKey, TValue> 
{ 
    public Dictionary<TKey, DictionaryEntry<TKey, TValue>> Children { get; private set; } 
    public TValue Value { get; private set; } 
    public bool HasValue { get; private set; } 

    public void SetValue(TValue value) 
    { 
     Value = value; 
     HasValue = true; 
    } 

    public DictionaryEntry() 
    { 
     Children = new Dictionary<TKey, DictionaryEntry<TKey, TValue>>(); 
    } 
} 

internal class KeyStackDictionary<TKey, TValue> 
{ 
    // Helper dictionary to work with a stack of keys 
    // Usage: 
    // var dict = new KeyStackDictionary<int, string>(); 
    // int[] keyStack = new int[] {23, 43, 54}; 
    // dict.SetValue(keyStack, "foo"); 
    // string value; 
    // if (dict.GetValue(keyStack, out value)) 
    // { 
    // } 

    private DictionaryEntry<TKey, TValue> _dict; 

    public KeyStackDictionary() 
    { 
     _dict = new DictionaryEntry<TKey, TValue>(); 
    } 

    public void SetValue(TKey[] keyStack, TValue value) 
    { 
     DictionaryEntry<TKey, TValue> dict = _dict; 

     for (int i = 0; i < keyStack.Length; i++) 
     { 
      TKey key = keyStack[i]; 
      if (dict.Children.ContainsKey(key)) 
      { 
       dict = dict.Children[key]; 
      } 
      else 
      { 
       var child = new DictionaryEntry<TKey, TValue>(); 
       dict.Children.Add(key, child); 
       dict = child; 
      } 

      if (i == keyStack.Length - 1) 
      { 
       dict.SetValue(value); 
      } 
     } 
    } 

    // returns false if the value is not found using the key stack 
    public bool GetValue(TKey[] keyStack, out TValue value) 
    { 
     DictionaryEntry<TKey, TValue> dict = _dict; 

     for (int i = 0; i < keyStack.Length; i++) 
     { 
      TKey key = keyStack[i]; 

      if (dict.Children.ContainsKey(key)) 
      { 
       dict = dict.Children[key]; 
      } 
      else 
      { 
       break; 
      } 

      if (i == keyStack.Length - 1 && dict.HasValue) 
      { 
       value = dict.Value; 
       return true; 
      } 
     } 

     value = default(TValue); 
     return false; 
    } 
}