tablas de hash y su relacion con las funciones GetHashCode y Equals de C# y hashCode y equals de Java

La mayoria de los lenguajes de programacion implementan tablas de hash en alguna de sus variantes (Hashtable, HashMap en Java o Hastable en C#). Un problema asociado a esta funcionalidad, es la correcta implementacion de las funciones para generar el codigo el codigo de hash de la llave, que sirve para obtener el valor asociado a la misma dentro de la tabla de hash.

Como se vio en el post hashCode y equals funcion en Java o GetHashCode y Equals en C#, una tabla de hash, se puede comparar con un diccionario. Dado que la funcion que obtiene el codigo hash de un objeto (GetHashCode para C# y hashCode para Java) puede obtener el valor entre -2³¹ y +2³¹ y si el codigo de hash, es unico, entonces, este codigo puede fungir como una "llave" adicional, sobre todo, si se define correctamente y se implementa una funcion que genere este codigo lo mas rapido posible.

Los tiempos de respuesta y uso de memoria de una tabla de hash, dependen de como se implemente, asi como de una correcta definicion de la funcion que genere el codigo de hash. El secreto del desempeño de la tabla de hash, esta el uso de la aritmetica modular, utilizada para determinar que codigos de hash son similares.

Tanto en Java, como en C# el codigo de hash, esta representado por un numero entero de 32 bits (4 bytes), esto da la posibilidad de tener 2³² (poco mas de 4 mil millones o millardos) posibles codigos de hash distintos. Como se vio en otro post, el codigo de hash, se emplea para "indexar" la informacion y realizar una busqueda ejecutando el menor numero de comparaciones posibles.


Para ver como funciona comparemos ahora la tabla de hash con un hospital, el cual tiene un archivo, donde por cuestiones de orden, se colocan los expedientes en cajones. Existen 27 cajones (utilizaremos el alfabeto ingles, el cual no tiene ñ, ch, ni acentos, dieresis u otras letras, simbolos, acentos, etc) cada cajon almacena los expedientes correspondientes a la letra inicial del nombre de la persona.

Suponiendo que el hospital es nuevo (new Hospital()), los 27 cajones estan vacios. cuando llega el primer paciente, se le genera un nuevo expediente y cuando se da de alta, se almacena su expediente en el archivo, si el paciente se llama Ricardo, el cajon que tiene una letra R al frente tendra un unico expediente y los otros 26 expedientes, seguiran vacios.

Si llega un nuevo paciente, llamado Juan, lo ideal, es que se busque si no tiene un expediente, entonces, buscando en el cajon donde se almacenan los expedientes que inician con J, nos damos cuenta de que no tiene expediente y creamos uno nuevo, para posteriormente almacenarlo.

Pero, este hospital es un poco desordenado al momento de almacenar los archivos, pues cuando llega otra persona con cuyo nombre es Ramon, el nuevo expediente, simplemente se pone encima del anterior y cuando llega Rosa, ocurre lo mismo, es decir, dentro del cada cajon, los expedientes, no se ordenan. Esto provoca que cuando llega una persona llamada Romario, se deba buscar el nombre en 3 expedientes distintos, puesto que al no estar ordenados alfabeticamente, hay que comparar el nombre para verificar que no es el expediente buscado. Por lo que es ligeramente mas tardado el proceso de busqueda del expediente de una persona cuyo nombre inicia con R que si inicia con J o si inicia con cualquier otra letra del abecedario. Ya se atendio Romario y se le genero un expediente. Extrañamente, viene una persona que se llama Ruperto (si, ya se, muchas R), esto provoca que el cajon donde estan estos expedientes, comienze a desbordarse y la busqueda cada vez tarde mas.

Esto que estoy describiendo, ocurre, cuando la funcion que genera el codigo de hash (la letra inicial del nombre, en este caso) esta incorrectamente definida y todos o la mayoria de los elementos que estamos almacenando tengan el mismo codigo de hash.

Para evitar esta situacion, se suelen definir funciones, en ocasiones extrañamente complejas, imaginemos por un momento, que cambiase las reglas para almacenar la informacion, ahora tendre las mismas 27 cajas, pero para determinar el cajon donde se almacenara el expediente, se sumara el valor ASCII de cada letra del nombre de la persona, el resultado se multiplicara por 13 (un numero primo por cierto) y se realizara la operacion modulo 27, al resultado de este, se le sumara 1, el resultado de esto, se convertira a una letra, 1 por A, 2 por B  ... y 27 por Z ... Despues de realizar todas estas operaciones , no duden que probablemente haya uno y solo un expediente por cajon,  pero ahora la generacion del codigo de hash se volvio costosa en tiempo.

Ahora, que ocurre cuando se agregan mas letras al abecedario, por ejemplo acentos y dieresis, asi como la letra ñ, pero sin agregar cajones a nuestro sistema de almacenamiento. La solucion es buscar similitudes o equivalencias, por ejemplo n es parecida a la letra ñ y las letras acentuadas o con dieresis a las mismas sin el acento o la dieresis. Esto es buscar similitudes o equivalencias. Para realizar estas operaciones de "equivalencias" las tablas de hash, utilizan aritmetica modular, es decir, dado que el universo para la generacion del codigo de hash, es basto, se emplea este tipo de aritmetica, para determinar que codigos de hash son similares y almacenarlos conjuntamente.

generics en C#, implementando GetHashCode, Equals y Comparable

A continuacion, la manera de utilizar generics en C#, para implementar las funciones GetHashCode y Equals, asi como la implementacion de IComparable. Este ejemplo es equivalente al ejemplo de java

01: using System;
02: using System.Collections.Generic;
03: 
04: namespace Test
05: {
06:     public abstract class GenericClass<T>
07:     {
08:         internal T id;
09: 
10:         public T Id
11:         {
12:             get
13:             {
14:                 return id;
15:             }
16:             set
17:             {
18:                 id = value;
19:             }
20:         }
21:         public override int GetHashCode()
22:         {
23:             return id.GetHashCode();
24:         }
25:         public override bool Equals(object obj)
26:         {
27:             return this == obj
28:                 || (((object)(id as GenericClass<T>) == null)
29:                     && Equals0((GenericClass<T>)obj));
30:         }
31:         public bool Equals(GenericClass<T> obj)
32:         {
33:             return this == obj || Equals0(obj);
34:         }
35:         private bool Equals0(GenericClass<T> obj)
36:         {
37:             return id.Equals(obj.id);
38:         }
39:     }
40: 
41:     public abstract class GenericClassComparable<T> : GenericClass<T>,
42:         IComparable<GenericClassComparable<T>> where T : IComparable<T>
43:     {
44:         public int CompareTo(GenericClassComparable<T> o)
45:         {
46:             return id.CompareTo(o.id);
47:         }
48:     }
49: }
50: 

Explicacion:
06-06: Declaracion de utilizacion del uso de generics
08-08: Declaracion del id.
10-20: Declaracion de los accesors para el id.
21-24: Definicion de la funcion GetHashCode, empleando las funciones propias del atributo id.
25-38: Definicion de multiples funciones Equals.
41-42: Declaracion del uso de IComparable
44-47: Definicion de la funcion CompareTo

Optimizacion:

• El uso de esta clase, permite utilizar automaticamente las funciones Sort y BinarySearch, de la clase Array, asi como la clase Hashtable
  

hashCode y equals funcion en Java o GetHashCode y Equals en C#

¿Cual es la relacion de las funciones que obtienen el codigo hash de un objeto, la funcion que determina la igualdad entre 2 objetos?

La respuesta, la dan las tablas de hash o hashtables en ingles. Para explicar el funcionamiento de estas empleare una analogia con los diccionarios (los libros). Un diccionario es un conjunto de palabras con su respectivo significado y las tablas de hash, son un conjunto de llaves asociadas con un valor. Comparando el diccionario con la tabla de hash, las llaves son las palabras y los significados, son los valores.

Para explicar el funcionamiento de la tabla de hash en terminos del diccionario, explicare primero la organizacion de este ultimo.

1. Las palabras estan ordenadas en orden alfabetico estricto
2. Las palabras que inician con la misma letra, estan agrupadas bajo esa letra, existiendo un indice de letras (este puede ser un indice o una serie de marcas en la orilla del mismo)

Bajo estas reglas, si yo necesito buscar el significado de la palabra "idioma" primero determino donde estan las palabras que inician con la letra I y posteriormente ubico la palabra dentro de esta seccion. Como nota, si la palabra no esta dentro de esta seccion (palabras que inician con I), no continuo buscando en las palabras que inician con J o H o cualquier otra letra del abecedario (claro, si se como emplear el diccionario).

Comparado con una tabla de hash, el codigo hash se emplea de la misma manera que nosotros empleamos la primer letra de la palabra a buscar en el diccionario, es decir, se emplea, para determinar un rango de busqueda y posteriormente se emplea la funcion que determina igualdad, para determinar la misma. Cabe aclarar que es importante, tanto para la busqueda en el diccionario, como la busqueda en la tabla de hash, que el algoritmo para generar el codigo hash debe ser eficiente (minimizar el tiempo de respuesta), ademas de que dado un valor, siempre debe regresar el mismo codigo.

Con respecto a la funcion equals, se utiliza para saber cual llave del conjunto (o palabra en caso del diccionario) tiene el valor (definicion en el diccionario) que estamos buscando.

Derivado de esto, se observa, que como en la vida real, tanto la funcion para obtener el codigo hash como la funcion para validad la igualdad, deben tener tiempos de respuesta minimos, particularmente la de igualdad, dado que es la que mas se emplea cuando se busca.

Nota: No es mi intencion ahondar en el funcionamiento de las tablas de hash, dado que existen multiples referencias a su funcionamiento en internet e implica conocimiento sobre teoria de colisiones, algunas formulas y conceptos matematicos, estructuras de datos y por supuesto las variantes de cada lenguaje de programacion. En la wikipedia, asi como en las materias relacionadas con estructuras de datos de muchas carreras relacionadas a sistemas se explica ampliamente su funcionamiento e implementacion.

Si lo muesto en este blog, es precisamente por la importancia que tiene definir correctamente las funciones y que ademas, sean eficazes y eficientes (optimas), pues el uso de tablas de hash esta amplamente extendido.

En java existen 2 clases que se emplean ampliamente Hashtable y HashMap. En C# la clase que se emplea normalmente es Hashtable.

Actualmente solo he implementado esta funcionalidad en java, en estas entradas:

• implementando las funciones hashCode y equals en java
• implementando las funciones hashCode y equals con generics en java

Pronto realizare las implementaciones respectivas para C#

implementando las funciones hashCode y equals con generics en java

En la entrada anterior, se mostro como implementar la funcion equals y hashCode, utilizando una clase especifica (String), sin embago, es posible implementar la funcionalidad anteriormente descrita, utilizando generics de java, funcionalidad introducida en la version 1.5 (5.0).

01: package test;
02: 
03: public abstract class GenericsBean<T> {
04: 
05:         T id;
06: 
07:         @Override
08:         public int hashCode() {
09:                 return id.hashCode();
10:         }
11: 
12:         @SuppressWarnings("unchecked")
13:         @Override
14:         public boolean equals(Object obj) {
15:                 return this == obj
16:                                 || (obj instanceof GenericsBean && equals0((GenericsBean<T>) obj));
17:         }
18: 
19:         public boolean equals(GenericsBean other) {
20:                 return this == other || equals0(other);
21:         }
22: 
23:         protected boolean equals0(GenericsBean other) {
24:                 return this.id.equals(other.id);
25:         }
26: 
27:         public T getId() {
28:                 return id;
29:         }
30: 
31:         public void setId(T id) {
32:                 this.id = id;
33:         }
34: 
35: }
36: 

Explicacion:

03-03: Se define la clase "parametrizada" que se empleara para definir el id del bean. Esta clase del id, puede ser incluso un id compuesto (un bean) y no solo un tipo nativo (Integer, Long, String, etc).
07-10: Se define el hashCode, utiilzando el hashCode del objeto id. A esta funcion se le agrega la anotacion @SuppressWarnings("unchecked"), para que el compilador no muestre mensajes de alerta debido a la conversion de un tipo "Generico".
19-21: Definicion de equals, para comparar contra un objeto cualquiera.
23-25: Definicion de la funcion equals0, la cual utiliza el equals del id.

Optimizacion:

1. La utilizacion de este codigo, ayuda a no definir estas funciones en cada ocasion. La mayor desventaja, radica en que no es posible cambiarle el nombre al atributo id.

Actualizacion:

• Se suprime el private en el id, para permitir acceso "friend"

implementando las funciones hashCode y equals en java

Creando una clase bean, necesita implementar las funciones equals y hashCode, no es necesario recurrir a algoritmos complejos y cripticos. El ejemplo siguiente implementa las funciones equals y hashCode, haciendolas simples, aprovechando funciones existentes.

01: package test;
02: 
03: public class Bean {
04: 
05:         private String key;
06: 
07:         @Override
08:         public int hashCode() {
09:                 return key.hashCode();
10:         }
11: 
12:         protected boolean equals0(Bean bean) {
13:                 return key.equals(bean.key);
14:         }
15: 
16:         @Override
17:         public boolean equals(Object obj) {
18:                 return this == obj || (obj instanceof Bean && equals0((Bean) obj));
19:         }
20: 
21:         public boolean equals(Bean bean) {
22:                 return this == bean || equals0(bean);
23:         }
24: 
25:         public String getKey() {
26:                 return key;
27:         }
28: 
29:         public void setKey(String key) {
30:                 this.key = key;
31:         }
32: 
33: }
34: 

En este ejemplo en particular, se utilizan las funciones existentes hashCode de la clase String y equals de la misma clase.

Explicacion:

07-10: Se emplea la funcion hashCode de la clase String, para generar el hashCode de la clase Bean.
12-14: Se implementa una funcion equals0, utilizando la funcion equals de la clase String. Esta clase define la funcionalidad basica de la funcion equals de la clase Object.
16-19: En la implementacion de la funcion equals, se emplea la funcion equals0 definida previamente y verificando el caso en que se trata del mismo objeto.
21-23: Esta funcion se define, para verificar la igualdad entre objetos del mismo tipo
25- 31: Definicion de getters y setters propios de la clase.

Optimizacion:

1. Uso de las funciones propias de String. Particularmente al definir la funcion hashCode. Esto mismo se puede implementar utilizando las funciones equivalentes de las clases Integer, Float, Double o cualquier otra que encapsule a un tipo nativo dentro del paquete java.lang
2. Las funciones equals primero determinan si se trata del mismo objeto, antes de intentar comparar cualquier propiedad o atributo.
3. Evitar la ejecucion del operador instanceof, en la medida de lo posible, al implementar 2 funciones equals, una generica, que recibe un parametro del tipo Object (linea 17) y una funcion especifica para objetos de la misma clase (linea 21). El mayor problema de estas funciones, radica en su resolucion, pues solo es posible optimizar en tiempo de ejecucion o por medio del uso de Reflection