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

162

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

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

Fung
источник
Посмотрите на комментарий, который я оставил к статье: stackoverflow.com/questions/763731/gethashcode-extension-method
Пол Уэсткотт
34
Кроме того: вы можете получить хеш-код по умолчанию (даже если GetHashCode()он был переопределен) с помощьюSystem.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj)
Marc Gravell
@MarcGravell спасибо за помощь, я искал именно этот ответ.
Андрей Савиных
@MarcGravell Но как бы я сделал это с другим методом?
Томаш Зато - Восстановить Монику

Ответы:

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

Дэвид Браун
источник
5
Эта документация цитата должна быть из очень ранней версии. Это больше не пишется так в текущих статьях MSDN, вероятно, потому что это совершенно неправильно.
Ганс Пассант
4
Они изменили формулировку, да, но она все еще говорит в основном то же самое: «Следовательно, реализация по умолчанию этого метода не должна использоваться в качестве уникального идентификатора объекта для целей хеширования».
Дэвид Браун
7
Почему в документации утверждается, что реализация не особенно полезна для хеширования? Если объект равен самому себе и ничему другому, любой метод хеш-кода, который всегда будет возвращать одно и то же значение для данного экземпляра объекта, и, как правило, будет возвращать разные значения для разных экземпляров, в чем проблема?
суперкат
3
@ ta.speot.is: Если вы хотите определить, был ли конкретный экземпляр уже добавлен в словарь, равенство ссылок идеально. Как вы заметили, для строк обычно больше интересует, была ли уже добавлена ​​строка, содержащая ту же последовательность символов . Вот почему stringпереопределяет GetHashCode. С другой стороны, предположим, что вы хотите вести подсчет того, сколько раз различные элементы управления обрабатывают Paintсобытия. Вы можете использовать Dictionary<Object, int[]>(каждый int[]хранится будет содержать только один элемент).
суперкат
6
@ It'sNotALie. Тогда поблагодарите Archive.org за предоставленную копию ;-)
RobIII
88

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

При переопределении равенства у вас всегда должно быть совпадение 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 ( ^) и т. д

Марк Гравелл
источник
Отличное замечание о пользе алгоритма факторизованной суммы; что-то, чего я раньше не осознавал!
лазейка
Не будет ли факторизованная сумма (как написано выше) иногда вызывать исключения переполнения?
Синелав
4
@sinelaw да, это должно быть выполнено unchecked. К счастью, uncheckedэто по умолчанию в C #, но было бы лучше сделать это явным; отредактировано
Марк Грэвелл
7

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

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

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

Guffa
источник
2
Я не согласен с тем, что вы должны регулярно добавлять свою собственную реализацию. Просто подавляющее большинство классов (в частности) никогда не будут проверяться на равенство - или там, где они есть, встроенное ссылочное равенство прекрасно. В (уже редком) случае написания структуры это было бы более распространенным, правда.
Марк Гравелл
@Marc Gravel: Это, конечно, не то, что я хотел сказать. Я буду корректировать последний абзац. :)
Guffa
Базовые типы данных не реализуют хороший метод GetHashCode, по крайней мере, в моем случае. Например, GetHashCode для int возвращает само число: (123). GetHashCode () возвращает 123.
fdermishin
5
@ user502144 А что с этим не так? Это идеальный уникальный идентификатор, который легко вычислить, без ложных срабатываний на равенство ...
Ричард Раст
@Richard Rast: все в порядке, за исключением того, что ключи могут плохо распределяться при использовании в Hashtable. Посмотрите на этот ответ: stackoverflow.com/a/1388329/502144
fdermishin
5

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

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

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

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

geekley
источник
1

Вообще говоря, если вы переопределяете 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
Подход ^ = не особенно хорош для генерации хеша - он имеет тенденцию приводить к множеству общих / предсказуемых коллизий - например, если Prop1 = Prop2 = 3.
Марк Гравелл
Если значения совпадают, я не вижу проблемы со столкновением, поскольку объекты равны. 13 * Hash + NewHash кажется интересным, хотя.
Беннет Дилл
2
Бен: попробуйте это для Obj1 {Prop1 = 12, Prop2 = 12} и Obj2 {Prop1 = 13, Prop2 = 13}
Томаш Кафка
0

Если вы просто имеете дело с 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;
    }
}
Даниэль Маршалл
источник