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

https://stackoverflow.com/questions/1646807

22-07-2019
|

Вопрос

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

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

XORing
Операция XOR с простым умножением
Простые числовые операции, такие как умножение/деление (с проверкой переполнения или переносом)
Создание строки и последующее использование метода хеш-кода классов String.

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

Решение

Я бы лично избегал 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, никто не знает, почему это работает хорошо, но это так. Это также легко запомнить, легко реализовать и легко распространить на любое количество полей.

Другие советы

Хотя шаблон, изложенный в ответе Джона Скита, в целом хорошо работает как семейство хеш-функций, выбор констант важен, а начальное число 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 на различные простые числа около hash = (hash * factor) ^ i; (оставляя CustomHash()), и все они работали хуже, чем в приведенном выше решении.

Наконец, я также сравнил с общим набором функций рекомендации ReSharper <=> и оригинальным <=>, как отмечалось выше, он значительно превосходит его. Стиль ReSharper XOR, по-видимому, имеет частоту столкновений в диапазоне 20-30% для общих предположений варианта использования и не должен использоваться по моему мнению.

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

Пример использования 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.Я не знаю, когда выйдет .NET Standard 2.1 Preview, и не знаю точно, будет ли HashCode будет частью этого.
Общего назначения, поэтому он не будет обрабатывать сверхспецифические случаи, а также код, созданный вручную.

Я полагаю, что команда .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;
}

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

(field1, field2).GetHashCode();

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

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

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

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

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

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

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

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

this.toString().hashCode();

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow