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 -231 y +231 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 232 (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.
