Hashtables

21 de junio de 2002

P: Cuando uso un objeto como clave en una tabla hash, ¿qué debo anular en la clase Object y por qué?

R: Cuando crea su propio objeto de clave para usarlo en a Hashtable, debe anular los métodos Object.equals()y Object.hashCode(), ya que Hashtableutiliza una combinación de los métodos hashCode()y de la clave equals()para almacenar y recuperar sus entradas rápidamente. También es una regla general que cuando anula equals(), siempre anula hashCode().

Más sobre por qué

Una explicación un poco más detallada le ayudará a comprender Hashtableel mecanismo de almacenamiento y recuperación. A Hashtableinternamente contiene depósitos en los que almacena los pares clave / valor. Los Hashtableusos código hash de la clave para determinar a qué cubeta par clave / valor debe asignar.

La figura 1 muestra Hashtableay sus cubos. Cuando pasa una clave / valor al Hashtable, consulta el código hash de la clave. Los Hashtableusos que el código para determinar el cubo en el que se sitúa la clave / valor. Entonces, por ejemplo, si el código hash es igual a cero, Hashtablecoloca el valor en el Bucket 0. Del mismo modo, si el código hash es dos, Hashtablecoloca el valor en el Bucket 2. (Este es un ejemplo simplista; Hashtableprimero masajeará el código hash para que el Hashtableno intenta insertar el valor fuera del depósito).

Al usar el código hash de esta manera, Hashtabletambién puede determinar rápidamente en qué depósito ha colocado el valor cuando intenta recuperarlo.

Los códigos hash, sin embargo, representan solo la mitad de la imagen. El código hash solo le dice Hashtableen qué depósito colocar la clave / valor. A veces, sin embargo, varios objetos pueden mapearse en el mismo depósito, un evento conocido como colisión. En Java, Hashtableresponde a una colisión colocando varios valores en el mismo depósito (otras implementaciones pueden manejar las colisiones de manera diferente). La Figura 2 muestra cómo Hashtablese vería después de algunas colisiones.

Ahora imagine que llama get()con una clave que se asigna al Bucket 0. HashtableAhora tendrá que realizar una búsqueda secuencial a través de los pares clave / valor en el Bucket 0 para encontrar el valor solicitado. Para realizar esta búsqueda, Hashtableejecuta los siguientes pasos:

1. Consultar el código hash de la clave
2. Recupere la lista de claves / valores que residen en el depósito proporcionado por el código hash
3. Escanear a través de cada entrada secuencialmente hasta que una clave que es igual a la clave pasado a la get()que se encuentra

Sé una respuesta larga a una pregunta corta, pero empeora. Correctamente anulando equals()y no hashCode()es un ejercicio trivial. Debe tener sumo cuidado para garantizar los contratos de ambos métodos.

Sobre la implementación de equals ()

Según el equals()Javadoc, el método debe ajustarse a las siguientes reglas:

"El equals()método implementa una relación de equivalencia:

• Es reflexivo: para cualquier valor de referencia x, x.equals(x)debe devolver verdadero
• Es simétrico: para cualquier valor de referencia xey, x.equals(y)debe devolver verdadero si y solo si y.equals(x)devuelve verdadero
• Es transitivo: para cualquier valor de referencia x, y y z, si x.equals(y)devuelve verdadero y y.equals(z)devuelve verdadero, entonces x.equals(z)debería devolver verdadero
• Es consistente: para cualquier valor de referencia xey, múltiples invocaciones de x.equals(y)devuelven constantemente verdadero o devuelven falso constantemente, siempre que no se modifique la información utilizada en comparaciones iguales en el objeto
• Para cualquier valor de referencia no nulo x, x.equals(null)debe devolver falso "

En Effective Java, Joshua Bloch ofrece una receta de cinco pasos para escribir un equals()método eficaz . Aquí está la receta en forma de código:

clase pública EffectiveEquals {private int valueA; private int valueB; . . . public boolean equals (Object o) {if (this == o) {// Paso 1: Realizar una prueba == return true; } if (! (o instanceof EffectiveEquals)) {// Paso 2: Instancia del cheque return false; } EffectiveEquals ee = (EffectiveEquals) o; // Paso 3: Cast argumento // Paso 4: Para cada campo importante, verifique si son iguales // Para primitivas use == // Para objetos use equals () pero asegúrese de // manejar también el caso nulo primero devuelve ee.valueA == valueA && ee.valueB == valueB; }. . . }

Nota: No es necesario realizar una verificación nula, ya que null instanceof EffectiveEqualsse evaluará como falso.

Finalmente, para el Paso 5, vuelva al equals()contrato de y pregúntese si el equals()método es reflexivo, simétrico y transitivo. Si no es así, ¡arréglalo!

Sobre la implementación de hashCode ()

Para hashCode()el contrato general, el Javadoc dice:

• "Siempre que se invoca en el mismo objeto más de una vez durante la ejecución de una aplicación Java, el hashCode()método debe devolver constantemente el mismo número entero, siempre que no se modifique la información utilizada en las comparaciones iguales del objeto. Este número entero no necesita ser coherente con uno ejecución de una aplicación a otra ejecución de la misma aplicación.
• Si dos objetos son iguales según el equals(Object)método, entonces llamar al hashCode()método en cada uno de los dos objetos debe producir el mismo resultado entero.
• No es necesario que si dos objetos no son iguales según el equals(java.lang.Objectmétodo, entonces llamar al hashCode()método en cada uno de los dos objetos debe producir resultados enteros distintos. Sin embargo, el programador debe ser consciente de que producir resultados enteros distintos para objetos desiguales puede mejorar el rendimiento de las tablas hash ".

Crear un hashCode()método de trabajo adecuado resulta difícil; se vuelve aún más difícil si el objeto en cuestión no es inmutable. Puede calcular un código hash para un objeto determinado de muchas formas. El método más eficaz basa el número en los campos del objeto. Además, puede combinar estos valores de varias formas. Aquí hay dos enfoques populares:

• Puede convertir los campos del objeto en una cadena, concatenar las cadenas y devolver el código hash resultante
• Puede agregar el código hash de cada campo y devolver el resultado

Si bien existen otros enfoques más completos, los dos enfoques antes mencionados demuestran ser los más fáciles de comprender e implementar.

Tony Sintes es consultor independiente y fundador de First Class Consulting, una empresa de consultoría que se especializa en unir sistemas empresariales dispares y capacitación. Fuera de First Class Consulting, Tony es un escritor independiente activo, así como autor de Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

Más información sobre este tema

• Para el Hashtable Javadoc, vaya a

  //java.sun.com/j2se/1.4/docs/api/java/util/Hashtable.html

• "Implementar equals () y hashCode ()" de Vipan Singla proporciona una discusión en profundidad sobre cómo anular los métodos equals () y hashCode ()

  //www.vipan.com/htdocs/hashcode_help.html

• The Object.equals() Javadoc

  //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#equals(java.lang.Object)

• The Object.hashCode() Javadoc

  //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#hashCode()

• For Joshua Bloch's Effective Java Programming Language Guide (Addison Wesley Professional, 2001; ISBN0201310058), go to

  //www.amazon.com/exec/obidos/ASIN/0201310058/javaworld

• For more articles on Java classes and methods, browse the APIs section of JavaWorld's Topical Index

  //www.javaworld.com/channel_content/jw-apis-index.shtml

• Want more? See the Java Q&A index page for the full Q&A catalog

  //www.javaworld.com/columns/jw-qna-index.shtml

• Durante más de 100 consejos interesantes Java a partir de algunas de las mejores mentes en el negocio, visita JavaWorld' s Consejos de Java página de índice

  //www.javaworld.com/columns/jw-tips-index.shtml

• Aprenda los conceptos básicos de Java en nuestra discusión para principiantes de Java

  //forums.idg.net/[email protected]@.ee6b804

• Regístrese para recibir el boletín electrónico semanal gratuito de Core Java por correo electrónico

  //www.javaworld.com/subscribe

• Encontrará una gran cantidad de artículos relacionados con TI de nuestras publicaciones hermanas en .net

Esta historia, "Hashtables", fue publicada originalmente por JavaWorld.