Как Object.GetHashCode () реализован в CLR & JVM? - PullRequest
Новая
       35

Как Object.GetHashCode () реализован в CLR & JVM?

12 голосов
/ 07 апреля 2011

Я размышлял об этом в течение некоторого времени: как именно Object.GetHashCode реализован в CLR или Java? Контракт для этого метода заключается в том, что если он вызывается для одного экземпляра объекта, он всегда должен возвращать одно и то же значение.

Обратите внимание, что я говорю о реализации по умолчанию GetHashCode (). Производные классы не обязаны переопределять этот метод. Если они решат не делать этого, они, по сути, будут иметь ссылочную семантику: равенство равно «равенству указателя» по умолчанию при использовании в хеш-таблицах & c. Это означает, что каким-то образом среда выполнения должна предоставлять постоянный хеш-код для объекта в течение всего времени его жизни.

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

Тем не менее, этот подход несовершенен, среди прочего, потому что:

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

  • В 64-битной системе адрес объекта слишком широк, чтобы поместиться в Int32.

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

В .NET System.Object состоит из блока синхронизации и дескриптора типа и ничего более, поэтому хеш-код нельзя кэшировать в самом экземпляре. Каким-то образом среда выполнения может предоставить постоянный хэш-код. Как? И как Java, Mono и другие среды выполнения делают это?

Ответы [ 3 ]

9 голосов
/ 07 апреля 2011

Нет, не адрес, который не может работать с движущимися объектами сборщика мусора. Это интуитивно просто, это может быть случайное число до тех пор, пока оно сохраняется после его генерации. Это делает сохраненным в объекте syncblk. В этом поле хранится более одного свойства объекта, оно заменяется индексом для выделенного syncblk, если требуется сохранить более одного такого свойства.

Алгоритм .NET использует идентификатор управляемого потока, поэтому потоки вряд ли будут генерировать одну и ту же последовательность: 

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

Семя сохраняется для каждой нити, поэтому блокировка не требуется. По крайней мере, это то, что используется в версии SSCLI20. Понятия не имею о Java, я думаю, что это похоже.

4 голосов
/ 08 апреля 2011

Как разработчик JVM, я могу сказать, что базовый хэш-код обычно связан с адресом объекта.Обычно это не адрес, а некоторые искажения его разумными способами.Мы делаем магию, чтобы гарантировать, что hashCode стабилен в течение всего срока службы объекта (даже через GC, даже если объект перемещается и т. Д.)

Я настоятельно рекомендую реализовать хороший специфичный для типа hashCode () для всехобъекты, которые вы собираетесь хэшировать.Этот объект реализует его, но это не значит, что он идеально подходит для вашего использования.

0 голосов
/ 07 апреля 2011

Я не уверен, что вы имеете в виду, "как именно Object.GetHashCode реализован в CLR или Java?". Java 'public int hashCode () "имеет контракт, согласно которому автор класса должен определить для него реализацию hashCode (). Другими словами, это может широко варьироваться между классами. Я подозреваю, что это будет верно и для платформ .Net.

Javadoc for Object описывает подход, похожий на вашу идею: http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Object.html#hashCode()

Насколько разумно, метод hashCode, определенный классом Объект возвращает различные целые числа для отдельных объектов. (Это обычно реализуется путем преобразования внутренний адрес объекта в целое число, но это Техника реализации не требуется для программирования JavaTM язык.)

Этот подход не подходит, если вы определили равенство для своего класса, основанное на чем-то отличном от идентичности.

...