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

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

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

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

Однако этот подход является ошибочным, среди прочего, потому что:

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

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

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

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

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

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