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

Question

Могут ли люди порекомендовать быстрые и простые способы объединения хеш-кодов двух объектов. Я не слишком беспокоюсь о коллизиях, так как у меня есть хэш-таблица, которая справится с этим эффективно, я просто хочу что-то, что генерирует код максимально быстро.

Читая SO и Интернет, кажется, есть несколько основных кандидатов:

1. XORing
2. XORing с простым умножением
3. Простые числовые операции, такие как умножение / деление (с проверкой переполнения или переносом)
4. Построение строки и затем использование метода хеш-кода классов String

Что бы люди посоветовали и почему?

Answer 1

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

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

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

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

Answer 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%. В 5- и 6-значных областях существуют даже лучшие варианты. Но для краткости я выбрал лучший 4-значный исполнитель, и он довольно хорошо работает во всех распространенных сценариях хеширования int и char. Кажется, он также отлично работает с целыми числами гораздо больших величин.

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

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

Answer 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 (хотя см. Ниже)
• Кажется, имеет хорошие характеристики производительности и микширования, основываясь на работе, которую автор и рецензенты сделали до слияния с репозиторием corefx
• Автоматически обрабатывает нули
• Перегрузки, которые принимают IEqualityComparer экземпляров

Минусы:

• По состоянию на август 2018 г. доступно только при таргетинге на .NET Core 2.1 или более позднюю версию.
  • По состоянию на апрель 2019 года, часть .NET Standard 2.1 Preview. Я не знаю, когда выйдет .NET Standard 2.1 Preview, и я точно не знаю, будет ли HashCode частью этого.
• общего назначения, поэтому он не будет обрабатывать сверхспецифичные случаи, а также ручной код

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

Answer 5

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

(field1, field2).GetHashCode();

Answer 6

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

this.toString().hashCode();

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

Answer 7

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

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

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

Answer 8

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

Answer 9

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

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

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

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