32-битная хеш-функция для объектов C#

Немного информации для всех. GetHashCode() на разных платформах .NET отличается. Например: «Hello».GetHashCode() в .NET 2.0 и «Hello».GetHashCode() в .NET 4.0 дают разные результаты. Следовательно, почему вы не можете сериализовать HashTables или Dictionary из коробки с помощью .NET.

Реализация собственных хеш-алгоритмов обеспечивает согласованность на разных платформах. Просто чтобы вы знали, вы не хотите идти меньше, чем Int32. Мой совет - придерживаться Int64 (длинный). Таким образом, у вас будет меньше коллизий, что и является целью хеширования :) Это библиотека, которую я написал много лет назад. У каждого алгоритма Hash есть свои плюсы и минусы (скорость против наименьшего количества столкновений). Эта конкретная версия использует строки в качестве входных данных, но вы можете изменить их по своему усмотрению:

static public class StringHash
    {
        //---------------------------------------------------------------------
        static public Int64 RSHash(String str)
        {
            const Int32 b = 378551;
            Int32 a = 63689;
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = hash * a + str[i];
                a = a * b;
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 JSHash(String str)
        {
            Int64 hash = 1315423911;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash ^= ((hash << 5) + str[i] + (hash >> 2));
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 ELFHash(String str)
        {
            Int64 hash = 0;
            Int64 x = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = (hash << 4) + str[i];

                if ((x = hash & 0xF0000000L) != 0)
                {
                    hash ^= (x >> 24);
                }
                hash &= ~x;
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 BKDRHash(String str)
        {
            const Int64 seed = 131; // 31 131 1313 13131 131313 etc..
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = (hash * seed) + str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 SDBMHash(String str)
        {
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = str[i] + (hash << 6) + (hash << 16) - hash;
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 DJBHash(String str)
        {
            Int64 hash = 5381;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = ((hash << 5) + hash) + str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 DEKHash(String str)
        {
            Int64 hash = str.Length;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = ((hash << 5) ^ (hash >> 27)) ^ str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 BPHash(String str)
        {
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = hash << 7 ^ str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 FNVHash(String str)
        {
            Int64 fnv_prime = 0x811C9DC5;
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash *= fnv_prime;
                hash ^= str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 APHash(String str)
        {
            Int64 hash = 0xAAAAAAAA;

            for (Int32 i = 0; i < str.Length; i++)
            {
                if ((i & 1) == 0)
                {
                    hash ^= ((hash << 7) ^ str[i] * (hash >> 3));
                }
                else
                {
                    hash ^= (~((hash << 11) + str[i] ^ (hash >> 5)));
                }
            }

            return hash;
        }
    }

Эрик Липперт создал отличная запись в блоге о том, как правильно реализовать метод GetHashCode(). Вы должны помнить, что целью GetHashCode() является помещение объектов в хеш-таблицу. Использование его для этой цели означает, что вы, скорее всего, захотите перебрать его или отсортировать в будущем. Если для этого вы используете криптографические функции, ваша итерация или процедура сортировки будут выполняться очень медленно. Функции шифрования предназначены для защиты данных, а не для их уникальной идентификации. Прочитайте сообщение в блоге Эрика Липперта. Это поможет вам

Вы можете реализовать GetHashCode, усекая хэш SHA. Но вы, вероятно, не должны.

Назначение GetHashCode — разрешить вставку объектов в хеш-таблицы. Целью хеш-таблиц является оптимизация поиска: в среднем поиск ключа в хэш-таблице требует всего O(1) времени по сравнению с O(log n) для дерева или O(n) для несортированного списка.

Вы действительно хотите, чтобы ваш метод GetHashCode минимизировал коллизии, чтобы предотвратить вырождение поиска в хеш-таблице до времени O(n). Но вы также хотите, чтобы они были быстрыми, потому что весь смысл хэш-таблиц заключается в оптимизации. Если вычисление вашего хеш-кода занимает много времени, вы могли бы просто сохранить свои данные в файле List.

Криптографические хэши работают медленно. Обычно они разработаны таким образом, чтобы препятствовать атакам методом грубой силы. Это делает их непригодными для использования с GetHashCode.

Итак, как следует реализовать GetHashCode? Простой, часто используемый подход состоит в том, чтобы просто объединить XOR всех переменных-членов, которые используются в вашей функции Equals.

struct Complex
{
    double real;
    double imag;

    public override int GetHashCode()
    {
        return real.GetHashCode() ^ imag.GetHashCode();
    }

    // ...
}

Другой простой подход, подходящий для массивоподобных объектов, — это полиномиальная хеш-функция.

class MyClass
{
    int[] data;

    public override int GetHashCode()
    {
        int result = 0;

        foreach (int n in data)
        {
            result = result * 41 + n;
        }

        return result;
    }

    // ...
}

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

Чем короче ширина хеш-значения, тем выше вероятность возникновения коллизий. Поскольку Int32 хранит максимум 4294967296 различных значений, вам необходимо подумать, будет ли оно содержать достаточно уникальное значение для ваших целей, что будет зависеть от того, предназначено ли это для проверки безопасности или проверки личности.

Мне интересно, почему вы хотите переопределить GetHashCode(), должно ли значение умещаться в 32 бита? Если да, то почему?