Хорошее переопределение GetHashCode () для объектов списка Foo, соответствующих порядку - PullRequest
Новая
       43

Хорошее переопределение GetHashCode () для объектов списка Foo, соответствующих порядку

28 голосов
/ 11 ноября 2011

EnumerableObject : IEnumerable<Foo>

переносит List<Foo>

Если EnumerableObject a.SequenceEquals( EnumerableObject b), то они равны.

Следовательно, GetHashCode должен быть реализован.Проблема в том, что XOR для каждого элемента в списке будет возвращать один и тот же хеш-код для любого списка со всеми и только одинаковыми элементами, независимо от порядка.Это нормально с точки зрения его работы, но приведет ко многим коллизиям, которые замедляют поиск и т. Д.

Что такое хороший, быстрый GetHashCode метод для списков объектов, зависящий от порядка?

Ответы [ 3 ]

59 голосов
/ 11 ноября 2011

Я бы сделал это так же, как я обычно комбинирую хэш-коды - с добавлением и умножением: 

public override int GetHashCode()
{
    unchecked
    {
        int hash = 19;
        foreach (var foo in foos)
        {
            hash = hash * 31 + foo.GetHashCode();
        }
        return hash;
    }
}

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

12 голосов
/ 11 ноября 2011

Во-первых, еще раз проверьте, что вам вообще нужен хеш-код.Собираетесь ли вы поместить эти списки в структуру с хэш-отображением (например, словарь, хэш-набор и т. Д.)?Если нет, то забудьте об этом.

Теперь, предположив, что вы имеете в виду, что EnumerableObject уже переопределяет Equals(object) (и, следовательно, мы надеемся, что по какой-то причине также реализует IEquatable<EnumerableObject>), тогда это действительно необходимо.Вы хотите сбалансировать скорость и распределение битов.

Хорошая отправная точка - это тип mult + add или shift + xor: 

public override int GetHashCode()
{
    int res = 0x2D2816FE;
    foreach(var item in this)
    {
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
}

(Предполагается, что вы используете item.Equals() для сравнения равенства последовательностей, если вы используете equals IEqualityComparer, вам нужно вызвать его хеш-код).

Оттуда мы можем оптимизировать.

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

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

public override int GetHashCode()
{
    int res = 0x2D2816FE;
    int max = Math.Min(Count, 16);
    for(int i = 0, i != max; ++i)
    {
        var item = this[i];
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
}

public override int GetHashCode()
{
    int res = 0x2D2816FE;
    int min = Math.Max(-1, Count - 16);
    for(int i = Count -1, i != min; --i)
    {
        var item = this[i];
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
}

public override int GetHashCode()
{
    int res = 0x2D2816FE;
    int step = Count / 16 + 1;
    for(int i = 0, i < Count; i += step)
    {
        var item = this[i];
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
}

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

Изменение числа 16 выше регулирует баланс;чем меньше, тем быстрее, но чем выше, тем лучше качество хеша с меньшим риском коллизий хешей.

Редактировать: И теперь вы можете использовать мою реализацию SpookyHash v. 2 : 

public override int GetHashCode()
{
  var hasher = new SpookyHash();//use methods with seeds if you need to prevent HashDos
  foreach(var item in this)
    hasher.Update(item.GetHashCode());//or relevant feeds of item, etc.
  return hasher.Final().GetHashCode();
}

Это создаст намного лучшее распределение, чем mult + add или shift + xor, но при этом будет особенно быстрым (особенно в 64-битных процессах, поскольку алгоритм оптимизирован для этого, хотя он также хорошо работает и в 32-битных системах).

4 голосов
/ 10 января 2018

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

public static class EnumerableExtensions
{
    public static int GetSequenceHashCode<TItem>(this IEnumerable<TItem> list)
    {
        if (list == null) return 0;
        const int seedValue = 0x2D2816FE;
        const int primeNumber = 397;
        return list.Aggregate(seedValue, (current, item) => (current * primeNumber) + (Equals(item, default(TItem)) ? 0 : item.GetHashCode()));
    }
}
...