Реализация Object.GetHashCode ()

Я читаю эффективный C #, и есть комментарий по поводу Object.GetHashCode(), который я не понял:

Object.GetHashCode() использует внутреннее поле в классе System.Object для генерации хеш-значения. Каждому созданному объекту при создании назначается уникальный ключ объекта, который сохраняется в виде целого числа.
Эти ключи начинаются с 1 и увеличиваются каждый раз, когда создается новый объект любого типа. Поле идентификатора объекта устанавливается в конструкторе System.Object и не может быть изменено позже. Object.GetHashCode() возвращает это значение как хэш-код для данного объекта.

Я попытался посмотреть документацию на Object.GetHashCode() и не нашел никакой информации по этому поводу.

Я написал простой фрагмент кода для печати хэш-кода вновь созданных объектов:

using System;

namespace TestGetHashCode
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 0; i < 100; i++)
            {
                object o = new object();
                Console.WriteLine(o.GetHashCode());
            }
        }
    }
}

Первыми напечатанными числами были:

37121646,
45592480,
57352375,
2637164,
41014879,
3888474,
25209742,
26966483,
31884011

Что, казалось, не подходило для этого

Эти ключи начинаются с 1 и увеличиваются каждый раз, когда создается новый объект любого типа ..._ 9_ возвращает это значение

Затем, чтобы найти это «внутреннее поле в System.Object», я попытался использовать декомпилированные исходные коды ReSharper, но найденный мной код был

[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
[__DynamicallyInvokable]
public virtual int GetHashCode()
{
  return RuntimeHelpers.GetHashCode(this);
}

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

[SecuritySafeCritical]
[__DynamicallyInvokable]
[MethodImpl(MethodImplOptions.InternalCall)]
public static int GetHashCode(object o);

после атрибута MethodImpl кажется, что я не могу просмотреть реализацию, и это для меня тупик.

Может кто-нибудь объяснить комментарий автора (первая цитата)?

Что такое внутреннее поле в классе Object и как оно используется для реализации Object.GetHashCode()?


object c# gethashcode
person Belgi    schedule 28.11.2014    source источник
comment
Это может быть полезно: stackoverflow.com/questions/720177/   -  person Yegor Korotetskiy    schedule 29.11.2014
comment
@ Юваль Ицчаков: это ирония? Иначе почему вы так думаете?   -  person zerkms    schedule 29.11.2014
comment
@ Юваль Ицчаков: как вы думаете, почему GetHashCode() должен возвращать уникальный идентификатор? Это называется Get*Hash*Code(), а не Get*UniqueIdentifier*() специально   -  person zerkms    schedule 29.11.2014
comment
@ Юваль Ицчаков: вы не так справляетесь с такой задачей - это именно то, как вы это делаете. Для типа, у которого нет изменяемых членов, у вас нет другого выбора. Так что, если хотите, можете даже реализовать его как return 42;, и все будет работать (не так эффективно, как могло бы быть, но ничего не сломается).   -  person zerkms    schedule 29.11.2014
comment
Ты прав. По какой-то причине я упустил из виду тот факт, что это object. Хотя реализация его как return 42 будет генерировать равенство для всех возвращаемых объектов. Не уверен, что вы думаете об этом   -  person Yuval Itzchakov    schedule 29.11.2014
comment
@Yuval Itzchakov: будет генерировать равенство для всех возвращаемых объектов --- это неверно. Никогда не следует относиться к объектам одинаково, если их хэш-коды совпадают. На самом деле все наоборот: одинаковые объекты ДОЛЖНЫ возвращать одинаковые хэш-коды, но одинаковые хэш-коды не означают, что объекты равны. msdn.microsoft.com/en -us / library / Не следует думать, что одинаковые хэш-коды подразумевают равенство объектов.   -  person zerkms    schedule 29.11.2014
comment
Но таким образом вы оставляете место для ошибок, поскольку не можете контролировать все базовые реализации, которые смотрят исключительно на равенство хэш-кода.   -  person Yuval Itzchakov    schedule 29.11.2014
comment
@Yuval Itzchakov: кто смотрит исключительно на равенство хэш-кода - никто не должен этого делать. Если кто-то делает что-то глупое - это не повод поощрять их продолжать это делать. Это не относится к .net. Если это случай со сторонней библиотекой - об этом нужно сообщить как об ошибке и исправить.   -  person zerkms    schedule 29.11.2014
comment
Никто не должен, ты прав. Но вы все равно не захотите оставлять на их усмотрение такие ошибки, просто генерируя разные хэш-коды.   -  person Yuval Itzchakov    schedule 29.11.2014
comment
@ Юваль Ицчаков: Я не уверен, что мы здесь обсуждаем. Существует спецификация языка, в которой указано, как это должно быть реализовано, нравится это кому-то или нет.   -  person zerkms    schedule 29.11.2014
comment
@YuvalItzchakov Это не выбор решать, следует ли внедрять хэш-коды без ложных срабатываний, вы просто не можете. Хэш-код - это конечное число, точнее Int32, что означает, что Int64, например, не может иметь уникальный хэш-код для каждого возможного значения (обязательно должно быть как минимум два long с одинаковым хешем). String - еще один очевидный пример, вы можете создавать практически бесконечное количество разных строк, которые, очевидно, не могут иметь уникальных хешей ... и этот список можно продолжать и продолжать ...   -  person InBetween    schedule 29.11.2014

Ответы (1)


arrow_upward
21
arrow_downward

Хорошо, я лучше напишу это. Книга очень неточная. Значение для Object.GetHashCode () создается внутри среды CLR и вычисляется по запросу при каждом первом вызове GetHashCode (). Я процитирую код из дистрибутива SSCLI20, clr / src / vm / thread.h имеет функцию, которая производит число, это выглядит так (отредактировано для удобства чтения):

inline DWORD GetNewHashCode()
{
    // 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 = m_ThreadId*4 + 5;
    m_dwHashCodeSeed = m_dwHashCodeSeed*multiplier + 1;
    return m_dwHashCodeSeed;
}

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

Присутствие переменной m_ThreadId в этом коде требует объяснения. Начальное значение генератора случайных чисел сохраняется для каждого отдельного потока. Уловка, позволяющая избежать блокировки.

M_dwHashCodeSeed инициализируется в конструкторе Thread следующим образом:

   // Initialize this variable to a very different start value for each thread
   // Using linear congruential generator from Knuth Vol. 2, p. 102, line 24
   dwHashCodeSeed = dwHashCodeSeed * 1566083941 + 1;
   m_dwHashCodeSeed = dwHashCodeSeed;

с участием:

   static  DWORD dwHashCodeSeed = 123456789;
person Hans Passant    schedule 28.11.2014
comment
Спасибо за ответ. Из этого кода кажется, что GetNewHashCode - это функция, которая зависит только от m_ThreadId, поэтому для одного и того же потока она генерирует один и тот же хэш-код при каждом вызове. Что мне здесь не хватает? - person Belgi; 29.11.2014
comment
Нет, это зависит от m_dwHashCodeSeed, обновляемого каждый раз, когда создается новый хэш-код. Каждый поток начинается с другого начального, нижнего фрагмента. m_ThreadId просто добавляет дополнительный уровень случайности, с этим помог Дональд Кнут. Не сосредотачивайтесь слишком на потоках, участвующих в этом, это просто трюк с кодом без блокировки. Замки дорогие. Есть некоторая хитрость, связанная с двумя потоками, вызывающими GetHashCode одновременно, я оставил это, чтобы сделать его полупонятным. - person Hans Passant; 29.11.2014
comment
Я понимаю, как это работает, и благодарю вас за написанное, но почему, черт возьми, это работает так? Надеяться на отсутствие конфликтов, как они, не нужно, верно? Почему бы не сгенерировать хеш для объекта на основе уникального идентификатора этого объекта? Или, если его нет, использовать UID, который увеличивается на 1 каждый раз, и сохранять его в блоке SYNC? Это то же самое, что и вышеупомянутое решение, только с абсолютным минимальным количеством возможных конфликтов (конфликтует только при переполнении UID) - person Slight; 28.02.2021