C# hashcode dla tablicy int

Question

Mam klasę, która wewnętrznie jest po prostu tablicą liczb całkowitych. Raz skonstruowana tablica nigdy się nie zmienia. Chciałbym wstępnie obliczyć dobry kod skrótu, aby ta klasa mogła być bardzo wydajnie używana jako klucz w słowniku. Długość tablicy wynosi mniej niż około 30 elementów, a liczby całkowite wynoszą ogólnie od -1000 do 1000.

Answer 1

Niezbyt mądra, ale wystarczające dla większości celów praktycznych:

EDIT: zmieniony z powodu komentarza Henk Holterman, dzięki za to.

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

Jeśli potrzebujesz czegoś bardziej wyrafinowane, look here.

Answer 2

Myślę, że wybór dobrego algorytmu hashowania musiałby być oparty na rozkładzie (w sensie prawdopodobieństwa) wartości całkowitych.

Wystarczy popatrzeć na Wikipedia dla listy algorytmów

Answer 3

Wszelkie CRC (lub nawet XOR) powinny być w porządku.

Answer 4

dla tablicy wartości ogólnie między -1000 i 1000, to pewnie użyć czegoś takiego:

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

Można użyć CRC32 kontrolną. Oto kod:

[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

Można przyjąć inne podejście i używać słownika rekurencyjnej dla każdej wartości w swojej tablicy int. W ten sposób możesz opuścić .net, aby wykonać mieszanie typu pierwotnego.

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