mono - ¿Cómo se implementa Object.GetHashCode() en CLR y JVM?

low-level

Question

Hace tiempo que reflexiono sobre esto: ¿cómo se implementa Object.GetHashCode en CLR o Java? El contrato para este método es que si se invoca en la misma instancia de objeto, siempre debe devolver el mismo valor.

Tenga en cuenta que estoy hablando de la implementación predeterminada de GetHashCode (). Las clases derivadas no son necesarias para anular este método. Si eligen no hacerlo, en esencia tendrán una semántica de referencia: la igualdad es igual a "igualdad de puntero" por defecto cuando se usa en tablas hash & c. Esto significa que, de alguna manera, el tiempo de ejecución debe proporcionar un código hash constante para el objeto a lo largo de su vida útil.

Si la máquina en la que estoy ejecutando es de 32 bits, y si la instancia del objeto nunca se movió en la memoria, teóricamente podría devolver la dirección del objeto, reinterpretada como Int32. Eso sería bueno, ya que todos los objetos distintos tienen direcciones distintas y, por lo tanto, tendrían diferentes códigos hash.

Sin embargo, este enfoque es defectuoso, entre otras cosas porque:

• si el recolector de basura mueve el objeto en la memoria, su dirección cambia, y también su código hash en violación del contrato que el código hash debe ser el mismo durante la vida del objeto.

• En un sistema de 64 bits, la dirección del objeto es demasiado amplia para caber en Int32.

• Debido a que los objetos gestionados tienden a estar alineados con alguna potencia par de 2, los bits más bajos siempre serán cero. Esto puede causar malos patrones de distribución cuando los códigos hash se usan para indexar en una tabla hash.

En .NET, un objeto System.Object consta de un bloque de sincronización y un manejador de tipo y nada más, por lo que el código hash no se puede almacenar en caché en la instancia en sí. De alguna manera, el tiempo de ejecución puede proporcionar un hashcode persistente. ¿Cómo? ¿Y cómo lo hacen Java, Mono y otros tiempos de ejecución?

Answer 1

No estoy seguro de lo que quiere decir con "¿cómo exactamente se implementa Object.GetHashCode en CLR o Java?". "Public int hashCode ()" de Java tiene el contrato de que el autor de una clase debe definir la implementación de hashCode () para él. En otras palabras, podría variar ampliamente entre clases. Sospecho que esto también sería cierto para las plataformas .Net.

El Javadoc para Object describe un enfoque similar a su idea: http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Object.html#hashCode ()

Tanto como sea razonablemente práctico, el método hashCode definido por el objeto de clase devuelve enteros distintos para objetos distintos. (Esto generalmente se implementa convirtiendo la dirección interna del objeto en un entero, pero esta técnica de implementación no es requerida por el lenguaje de programación JavaTM).

Este enfoque no es apropiado si ha definido la igualdad para su clase basada en algo que no sea la identidad.

Answer 2

No, no la dirección, que no puede funcionar con un recolector de basura moviendo objetos. Es intuitivamente simple, puede ser un número aleatorio siempre que se guarde después de generarse. Se almacena en el objeto, syncblk. Ese campo almacena más de una propiedad del objeto, se reemplaza por un índice para una syncblk asignada si es necesario almacenar más de una de dichas propiedades.

El algoritmo .NET usa la identificación de subprocesos administrados para que los subprocesos no generen la misma secuencia:

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

La semilla se almacena por hilo por lo que no se requiere bloqueo. Al menos eso es lo que se usa en la versión SSCLI20. No tengo idea de Java, me imagino que es similar.

Answer 3

Como implementador de JVM, puedo decir que el hashcode base IS generalmente está relacionado con la dirección del objeto. Por lo general, no es exactamente la dirección, pero se trata de modificarla de manera razonable. Hacemos magia para asegurar que hashCode sea estable a lo largo de la vida del objeto (incluso a través de GC, incluso si el objeto se mueve, etc.)

Recomiendo encarecidamente implementar un buen hashCode () específico de tipo para todos los objetos que va a ser hashing. Ese Objeto lo implementa, no significa que sea ideal para su uso.