Блог

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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