Быстрые и простые комбинации хэш-кодов

Ответ 1

Я бы лично избегал XOR - это означает, что любые два равных значения приведут к 0 - так хэш (1, 1) == hash (2, 2) == hash (3, 3) и т.д. Также hash (5, 0) == hash (0, 5) и т.д., Которые могут возникать изредка. Я намеренно использовал его для установки хэширования - если вы хотите хешировать последовательность элементов, и вы не заботитесь о заказе, это приятно.

Я обычно использую:

unchecked
{
    int hash = 17;
    hash = hash * 31 + firstField.GetHashCode();
    hash = hash * 31 + secondField.GetHashCode();
    return hash;
}

То, что предлагает Джош Блох в Эффективной Java. В прошлый раз, когда я ответил на аналогичный вопрос, мне удалось найти статью, где это обсуждалось подробно - IIRC, никто не знает, почему это работает хорошо, но это так. Он также легко запоминается, легко реализуется и легко распространяется на любое количество полей.

Ответ 2

В то время как шаблон, описанный в ответе Джона Скита, хорошо работает как семейство хэш-функций, выбор констант важен, а семя 17 и коэффициент 31, как указано в ответе, не работают хорошо вообще для случаев общего использования. В большинстве случаев хешированные значения намного ближе к нулю, чем int.MaxValue, а количество элементов, которые совместно хэшируются, составляет несколько десятков или менее.

Для хеширования целочисленного набора {x, y}, где -1000 <= x <= 1000 и -1000 <= y <= 1000, он имеет ужасную скорость столкновения почти 98,5%. Например, {1, 0} -> {0, 31}, {1, 1} -> {0, 32} и т.д. Если мы расширим охват, также включим n-кортежи, где 3 <= n <= 25, он будет менее страшен с частотой столкновений около 38%. Но мы можем сделать гораздо лучше.

public static int CustomHash(int seed, int factor, params int[] vals)
{
    int hash = seed;
    foreach (int i in vals)
    {
        hash = (hash * factor) + i;
    }
    return hash;
}

Я написал цикл поиска выборки в Монте-Карло, который протестировал вышеописанный метод с различными значениями для семени и фактора в разных случайных n-наборах случайных целых чисел i. Допустимые диапазоны были 2 <= n <= 25 (где n было случайным, но смещенным в сторону нижнего конца диапазона) и -1000 <= i <= 1000. Для каждой пары семян и факторов было выполнено не менее 12 миллионов уникальных испытаний на столкновение.

Примерно через 7 часов лучшая найденная пара (где семя и коэффициент были ограничены до 4 цифр или меньше) составляла: seed = 1009, factor = 9176, с частотой столкновений 0,1131%. В пяти- и шестизначных областях существуют даже лучшие варианты. Но я выбрал верхний 4-значный исполнитель для краткости, и он хорошо отражается во всех распространенных сценариях хеширования int и char. Он также отлично работает с целыми числами гораздо больших величин.

Стоит отметить, что "быть простым", по-видимому, не является общей предпосылкой хорошей производительности как семени и/или фактора, хотя это, вероятно, помогает. 1009, отмеченное выше, фактически является простым, но 9176 не является. Я явно протестировал вариации на этом, где я изменил factor на различные простые числа около 9176 (оставив seed = 1009), и все они выполнялись хуже, чем указанное решение.

Наконец, я также сравнил с общим семейством рекомендаций рекомендации ReSharper hash = (hash * factor) ^ i;, а оригинальный CustomHash(), как отмечено выше, серьезно превзошел его. Стиль ReSharper XOR, по-видимому, имеет коэффициенты столкновений в диапазоне 20-30% для предположений общего использования и не должен использоваться по моему мнению.

Ответ 3

Если вы используете .NET Core 2.1 или более позднюю версию, рассмотрите возможность использования структуры System.HashCode для создания составных хэш-кодов. Он имеет два режима работы: Добавить и Объединить.

Пример с использованием Combine, который, как правило, проще и может содержать до восьми элементов:

public override int GetHashCode()
{
    return HashCode.Combine(object1, object2);
}

Пример использования Add:

public override int GetHashCode()
{
    var hash = new HashCode();
    hash.Add(this.object1);
    hash.Add(this.object2);
    return hash.ToHashCode();
}

Плюсы:

• Часть самого .NET, начиная с .NET Core 2.1/.NET Standard 2.1 (хотя, см. ниже)
• Судя по всему, обладает хорошими характеристиками производительности и микширования, основываясь на работе, которую автор и рецензенты проделали до слияния с репозиторием corefx
• Обрабатывает нули автоматически
• Перегрузки, которые принимают IEqualityComparer экземпляры

Минусы:

• Недоступно в .NET Framework. HashCode является частью .NET Standard 2.1, но по состоянию на сентябрь 2019 года команда .NET не планирует поддерживать стандарт .NET в .NET Framework, как .NET Core/.NET 5 - это будущее .NET.
• Общего назначения, поэтому он не будет обрабатывать сверхспецифичные случаи, а также ручной код

Ответ 4

Я предполагаю, что команда .NET Framework выполнила достойную работу по тестированию своей System.String.GetHashCode(), поэтому я бы использовал ее:

// System.String.GetHashCode(): http://referencesource.microsoft.com/#mscorlib/system/string.cs,0a17bbac4851d0d4
// System.Web.Util.StringUtil.GetStringHashCode(System.String): http://referencesource.microsoft.com/#System.Web/Util/StringUtil.cs,c97063570b4e791a
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash1 = (5381 << 16) + 5381;
    int hash2 = hash1;

    int i = 0;
    foreach (var hashCode in hashCodes)
    {
        if (i % 2 == 0)
            hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ hashCode;
        else
            hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ hashCode;

        ++i;
    }

    return hash1 + (hash2 * 1566083941);
}

Другая реализация - System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32) и System.Array.CombineHashCodes(System.Int32, System.Int32). Это проще, но, вероятно, не имеет такого хорошего распределения, как метод выше:

// System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#System.Web/Util/HashCodeCombiner.cs,21fb74ad8bb43f6b
// System.Array.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#mscorlib/system/array.cs,87d117c8cc772cca
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash = 5381;

    foreach (var hashCode in hashCodes)
        hash = ((hash << 5) + hash) ^ hashCode;

    return hash;
}

Ответ 5

Используйте комбинационную логику в кортеже. В примере используется С# 7 кортежей.

(field1, field2).GetHashCode();

Ответ 6

Если ваши хеши ввода имеют одинаковый размер, равномерно распределенные и не связанные друг с другом, тогда XOR должен быть в порядке. Плюс это быстро.

Ситуация, о которой я предлагаю это, - это то, где вы хотите сделать

H = hash(A) ^ hash(B); // A and B are different types, so there no way A == B.

конечно, если A и B можно ожидать, что хеш будет иметь одно и то же значение с разумной (не пренебрежимо малой) вероятностью, тогда вы не должны использовать XOR таким образом.

Ответ 7

Если вы ищете скорость и не слишком много столкновений, то XOR является самым быстрым. Чтобы предотвратить кластеризацию вокруг нуля, вы можете сделать что-то вроде этого:

finalHash = hash1 ^ hash2;
return finalHash != 0 ? finalHash : hash1;

Конечно, некоторые прототипы должны дать вам представление о производительности и кластеризации.

Ответ 8

Предполагая, что у вас есть соответствующая функция toString() (где должны появиться ваши различные поля), я бы просто вернул ее хеш-код:

this.toString().hashCode();

Это не очень быстро, но должно очень хорошо избегать столкновений.

Ответ 9

Я бы рекомендовал использовать встроенные хэш-функции в System.Security.Cryptography, а не сворачивать ваши собственные.