Реализация по умолчанию для Object.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);
        }
    }
}

InternalGetHashCode отображается на функцию ObjectNative :: 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

Полная реализация GetHashCodeEx довольно велика, поэтому проще просто связать исходный код 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}

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

Answer 3

В документации по методу GetHashCode для Object говорится "реализация по умолчанию этого метода не должна использоваться в качестве уникального идентификатора объекта для целей хеширования." и для ValueType говорит «Если вы вызываете метод 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 выполняет итерации по экземпляру и блоки XOR по 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; }
}

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

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

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

Answer 5

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

Равен используется при проверке 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;
}

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

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

Answer 6

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

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