整数数组的C#哈希码

我有一个类,内部只是一个整数数组。 一旦构造,arrays永远不会改变。 我想预先计算一个好的哈希码,以便这个类可以非常有效地用作词典中的键。 数组的长度小于约30项,并且整数通常在-1000和1000之间。

不是很聪明,但足以满足大多数实际目的:

编辑:由于Henk Holterman的评论而改变,谢谢。

int hc=array.Length; for(int i=0;i 

如果你需要更复杂的东西, 请看这里 。

您可以使用CRC32校验和。 这是代码:

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

对于通常介于-1000和1000之间的值数组,我可能会使用以下内容:

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

任何CRC(甚至XOR)都应该没问题。

我认为选择一个好的哈希算法必须基于整数值的分布(在概率意义上)。

查看维基百科以获取算法列表

您可以采用不同的方法,并为int数组中的每个值使用递归字典。 这样你就可以让.net做原始类型的散列。

 internal class DictionaryEntry { public Dictionary> 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>(); } } internal class KeyStackDictionary { // Helper dictionary to work with a stack of keys // Usage: // var dict = new KeyStackDictionary(); // int[] keyStack = new int[] {23, 43, 54}; // dict.SetValue(keyStack, "foo"); // string value; // if (dict.GetValue(keyStack, out value)) // { // } private DictionaryEntry _dict; public KeyStackDictionary() { _dict = new DictionaryEntry(); } public void SetValue(TKey[] keyStack, TValue value) { DictionaryEntry 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(); 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 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; } }