С# hashcode для массива ints

Ответ 1

Не очень умный, но достаточный для практических целей:

EDIT: изменилось из-за комментария Хенка Холтермана, спасибо за это.

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

Если вам нужно что-то более сложное, смотрите здесь.

Ответ 2

Вы можете использовать контрольную сумму 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;
    }
}

Ответ 3

Для массива значений обычно от -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;
}

Ответ 4

Любой CRC (или даже XOR) должен быть в порядке.

Ответ 5

Я думаю, что выбор хорошего хэш-алгоритма должен основываться на распределении (в смысле вероятности) целочисленных значений.

Посмотрите Wikipedia для списка алгоритмов

Ответ 6

Вы можете использовать другой подход и использовать рекурсивный словарь для каждого значения в вашем массиве int. Таким образом, вы можете оставить .net, чтобы сделать хэширование примитивного типа.

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