Реализация по умолчанию для объекта.GetHashCode()

Question

Как работает реализация по умолчанию для GetHashCode() работать?И обрабатывает ли он структуры, классы, массивы и т.д.эффективно и достаточно хорошо?

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

Answer 1

namespace System {
    public class Object {
        [MethodImpl(MethodImplOptions.InternalCall)]
        internal static extern int InternalGetHashCode(object obj);

        public virtual int GetHashCode() {
            return InternalGetHashCode(this);
        }
    }
}

Внутренний хэш - код сопоставляется с Объектный код::GetHashCode функция в среде CLR, которая выглядит следующим образом:

FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

Полное осуществление Получить hashcodeex является довольно большим, поэтому проще просто ссылаться на исходный код на C ++.

Answer 2

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

При переопределении равенства у вас всегда должно быть совпадающее Equals() и GetHashCode() (т.е.для двух значений, если Equals() возвращает true , они должен возвращает тот же хэш-код, но обратное не требуется) - и обычно также предоставляется ==/!=операторов, и часто для реализации IEquatable<T> слишком.

Для генерации хэш-кода обычно используется факторизованная сумма, поскольку это позволяет избежать коллизий при парных значениях - например, для базового хэша из 2 полей:

unchecked // disable overflow, for the unlikely possibility that you
{         // are compiling with overflow-checking enabled
    int hash = 27;
    hash = (13 * hash) + field1.GetHashCode();
    hash = (13 * hash) + field2.GetHashCode();
    return hash;
}

Это имеет то преимущество, что:

• хэш {1,2} не совпадает с хэшем {2,1}
• хэш {1,1} не совпадает с хэшем {2,2}

etc - что может быть обычным явлением, если просто использовать невзвешенную сумму или xor (^) и т.д.

Answer 3

Документация для GetHashCode способ для Объект говорит "реализация этого метода по умолчанию не должна использоваться в качестве уникального идентификатора объекта для целей хеширования". и тот, который для Тип значения говорит "Если вы вызываете метод GetHashCode производного типа, возвращаемое значение вряд ли подойдет для использования в качестве ключа в хэш-таблице"..

Основные типы данных, такие как byte, short, int, long, char и string реализуйте хороший метод GetHashCode.Некоторые другие классы и структуры, такие как Point например, внедрите GetHashCode метод, который может подходить, а может и не подходить для ваших конкретных потребностей.Вам просто нужно попробовать это, чтобы убедиться, достаточно ли это хорошо.

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

Answer 4

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

Я рекомендую прочитать весь пост, но вот краткое изложение (добавлены акценты и пояснения).

Причина хэш по умолчанию для структур медленный и не очень хороший:

Способ, которым разработана среда CLR, заключается в том, что каждый вызов элемента, определенного в System.ValueType или System.Enum типы [могут] вызвать распределение боксов [...]

Разработчик хэш-функции сталкивается с дилеммой:сделайте хорошее распределение хэш-функции или сделайте это быстро.В некоторых случаях возможно достичь их обоих, но это трудно сделать это в общем виде в ValueType.GetHashCode.

Каноническая хэш-функция структуры "объединяет" хэш-коды всех полей.Но единственный способ получить хэш-код поля в ValueType метод заключается в том, чтобы используйте отражение.Итак, авторы CLR решили обменять скорость на дистрибутив и значение по умолчанию GetHashCode версия просто возвращает хэш-код первого ненулевого поля и "забивает" его идентификатором типа [...] Это разумное поведение, если только это не так.Например, если вам не повезло и первое поле вашей структуры имеет одинаковое значение для большинства экземпляров, то хэш-функция выдаст тот же результат все время.И, как вы можете себе представить, это приведет к резкому снижению производительности, если эти экземпляры будут храниться в хэш-наборе или хэш-таблице.

[...] Реализация, основанная на отражении, происходит медленно.Очень медленно.

[...] Оба ValueType.Equals и ValueType.GetHashCode есть специальная оптимизация.Если тип не имеет "указателей" и правильно упакован [...], то используются более оптимальные версии: GetHashCode выполняет итерацию по экземпляру и блокирует XORs по 4 байта и Equals метод сравнивает два экземпляра, используя memcmp.[...] Но оптимизация - это очень сложная задача.Во-первых, трудно понять, когда включена оптимизация [...] Во-вторых, сравнение памяти не обязательно даст вам правильные результаты.Вот простой пример:[...] -0.0 и +0.0 равны, но имеют разные двоичные представления.

Реальная проблема, описанная в посте:

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

Мы использовали кортеж, который содержал пользовательскую структуру с реализацией равенства по умолчанию.И к сожалению, структура имела необязательное первое поле, которое почти всегда было равно [пустой строке].Производительность была в норме до тех пор, пока количество элементов в наборе значительно не увеличилось, что вызвало реальную проблему с производительностью: на инициализацию коллекции с десятками тысяч элементов уходили минуты.

Итак, чтобы ответить на вопрос "в каких случаях я должен упаковать свой собственный и в каких случаях я могу безопасно полагаться на реализацию по умолчанию", по крайней мере, в случае структуры, вы должны переопределить Equals и GetHashCode всякий раз, когда ваша пользовательская структура может использоваться в качестве ключа в хэш-таблице или Dictionary.
Я бы также рекомендовал внедрить IEquatable<T> в этом случае следует избегать бокса.

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

Answer 5

Вообще говоря, если вы переопределяете Equals , вы хотите переопределить GetHashCode .Причина этого в том, что оба они используются для сравнения равенства вашего класса / структуры.

Equals используется при проверке Foo A, B;

если (A == B)

Поскольку мы знаем, что указатель вряд ли будет совпадать, мы можем сравнить внутренние элементы.

Equals(obj o)
{
    if (o == null) return false;
    MyType Foo = o as MyType;
    if (Foo == null) return false;
    if (Foo.Prop1 != this.Prop1) return false;

    return Foo.Prop2 == this.Prop2;
}

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

Обычно я так и делаю,

GetHashCode()
{
    int HashCode = this.GetType().ToString().GetHashCode();
    HashCode ^= this.Prop1.GetHashCode();
    etc.

    return HashCode;
}

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

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

Answer 6

Если вы просто имеете дело с POCOs, вы можете использовать эту утилиту, чтобы несколько упростить свою жизнь:

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}