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

Question

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

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

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

197

.net hash gethashcode

Источник

user8280 06 апр '09 в 03:25

7 ответов

Решение

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

При переопределении равенства, вы всегда должны иметь соответствующие 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}

и т. д., что может быть обычным делом, если использовать невзвешенную сумму^), так далее.

108

Источник

user23354 06 апр '09 в 04:29

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

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

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

Как устроен CLR, каждый вызов члена, определенного в System.ValueType или же System.Enum типы [могут] вызвать распределение бокса [...]
Реализатор хеш-функции сталкивается с дилеммой: правильно распределить хеш-функцию или сделать ее быстрой. В некоторых случаях возможно достичь их обоих, но это трудно сделать в общем ValueType.GetHashCode,
Каноническая хеш-функция структуры "объединяет" хеш-коды всех полей. Но единственный способ получить хеш-код поля в ValueType Метод заключается в использовании отражения. Таким образом, авторы CLR решили торговать скоростью по распределению и по умолчанию GetHashCode version просто возвращает хеш-код первого ненулевого поля и "наполняет" его идентификатором типа [...]. Это разумное поведение, если только это не так. Например, если вам не повезло и первое поле вашей структуры имеет одинаковое значение для большинства экземпляров, то хеш-функция будет все время давать один и тот же результат. И, как вы можете себе представить, это приведет к значительному снижению производительности, если эти экземпляры будут храниться в хэш-наборе или хэш-таблице.
[...] Реализация на основе отражений медленная. Очень медленно.
[...] И то и другое 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; }
}

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

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

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

12

Источник

user9638388 20 июл '18 в 04:14

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

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

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

7

Источник

user69083 06 апр '09 в 04:02

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

          inline DWORD GetNewHashCode()
    {
        LIMITED_METHOD_CONTRACT;
        // Every thread has its own generator for hash codes so that we won't get into a situation
        // where two threads consistently give out the same hash codes.
        // Choice of multiplier guarantees period of 2**32 - see Knuth Vol 2 p16 (3.2.1.2 Theorem A).
        DWORD multiplier = GetThreadId()*4 + 5;
        m_dwHashCodeSeed = m_dwHashCodeSeed*multiplier + 1;
        return m_dwHashCodeSeed;
    }

Вот стек вызовов:

Тема:: Жетньевхэшкоде

Объект::ComputeHashCode

Объект:: ЖетХашкодекс

4

Источник

user5020243 09 окт '22 в 09:32

Вообще говоря, если вы переопределяете 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, вы можете сообщить о равенстве на основе внутренних значений, а не ссылки на объекты.

2

Источник

user67137 06 апр '09 в 03:42

Если вы просто имеете дело с 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;
    }
}

1

Источник

user5043592 20 мар '19 в 05:00

Другие вопросы по тегам .net hash gethashcode

user31516 06 апр '09 в 03:43 2009-04-06 03:43 · Accepted Answer · 2009-04-06 03:43

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++.