Es un método de búsqueda que aumenta la velocidad de búsqueda, pero que no requiere que los elementos estén ordenados.
Consiste en asignar a cada elemento un índice mediante una transformación del elemento. Esta correspondencia se realiza mediante una función de conversión, llamada función hash.
La correspondencia más sencilla es la identidad, esto es, al número 0 se le asigna el índice 0, al elemento 1 el índice 1, y así sucesivamente. Pero si los números a almacenar son demasiado grandes esta función es inservible.
Por ejemplo, se quiere guardar en un array la información de los 1000 usuarios de una empresa, y se elige el número de DNI como elemento identificativo. Es inviable hacer un array de 100.000.000 elementos, sobre todo porque se desaprovecha demasiado espacio. Por eso, se realiza una transformación al número de DNI para que nos dé un número menor, por ejemplo coger las 3 últimas cifras para guardar a los empleados en un array de 1000 elementos. Para buscar a uno de ellos, bastaría con realizar la transformación a su DNI y ver si está o no en el array.
La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar. La función de hash depende de cada problema y de cada finalidad, y se pueden utilizar con números o cadenas, pero las más utilizadas son:
• Restas sucesivas: Esta función se emplea con claves numéricas entre las que existen huecos de tamaño conocido, obteniéndose direcciones consecutivas. Por ejemplo, si el número de expediente de un alumno universitario está formado por el año de entrada en la universidad, seguido de un número identificativo de tres cifras, y suponiendo que entran un máximo de 400 alumnos al año, se le asignarían las claves:
1998-000 --> 0 = 1998000-1998000
1998-001 --> 1 = 1998001-1998000
1998-002 --> 2 = 1998002-1998000
...
1998-399 --> 399 = 1998399-1998000
1999-000 --> 400 = 1999000-1998000+400
...
yyyy-nnn --> n = yyyynnn-1998000+(400*(yyyy-1998))
• Aritmética modular: El índice de un número es resto de la división de ese número entre un número n prefijado, preferentemente primo. Los números se guardarán en las direcciones de memoria de 0 a n-1. Este método tiene el problema de que cuando hay n+1 elementos, al menos un índice es señalado por dos elementos (teorema del palomar). A este fenómeno se le llama colisión, y es tratado más adelante. Si el número n es el 13, los números siguientes quedan transformados en:
13000000 --> 0
12345678 --> 7
13602499 --> 1
71140205 --> 6
73062138 --> 6
• Mitad del cuadrado: Consiste en elevar al cuadrado la clave y coger las cifras centrales. Este método también presenta problemas de colisión:
123*123 = 15129 --> 51
136*136 = 18496 --> 84
730*730 = 532900 --> 29
301*301 = 90601 --> 06
625*625 = 390625 --> 06
• Truncamiento: Consiste en ignorar parte del número y utilizar los elementos restantes como índice. También se produce colisión. Por ejemplo, si un número de 8 cifras se debe ordenar en un array de 1000 elementos, se pueden coger la primer, la tercer y la última cifras para formar un nuevo número:
13000000 --> 100
12345678 --> 138
13602499 --> 169
71140205 --> 715
73162135 --> 715
• Plegamiento: Consiste en dividir el número en diferentes partes, y operar con ellas (normalmente con suma o multiplicación). También se produce colisión.
Por ejemplo, si dividimos los número de 8 cifras en 3, 3 y 2 cifras y se suman, dará otro número de tres cifras (y si no, se cogen las tres últimas cifras):
13000000 --> 130 = 130+000+00
12345678 --> 657 = 123+456+78
71140205 --> 118 --> 1118 = 711+402+05
13602499 --> 259 = 136+024+99
25000009 --> 259=250+000+09
Tratamiento de colisiones: Pero ahora se nos presenta el problema de qué hacer con las colisiones, qué pasa cuando a dos elementos diferentes les corresponde el mismo índice. Pues bien, hay tres posibles soluciones:
1. Cuando el índice correspondiente a un elemento ya está ocupada, se le asigna el primer índice libre a partir de esa posición. Este método es poco eficaz, porque al nuevo elemento se le asigna un índice que podrá estar ocupado por un elemento posterior a él, y la búsqueda se ralentiza, ya que no se sabe la posición exacta del elemento.
2. También se pueden reservar unos cuantos lugares al final del array para alojar a las colisiones. Este método también tiene un problema: ¿Cuánto espacio se debe reservar? Además, sigue la lentitud de búsqueda si el elemento a buscar es una colisión.
3. Lo más efectivo es, en vez de crear un array de número, crear un array de punteros, donde cada puntero señala el principio de una lista enlazada. Así, cada elemento que llega a un determinado índice se pone en el último lugar de la lista de ese índice. El tiempo de búsqueda se reduce considerablemente, y no hace falta poner restricciones al tamaño del array, ya que se pueden añadir nodos dinámicamente a la lista.
Implementación de la Búsqueda mediante Tablas Hash
//Implementación aplicando la aritmética modular
public class Hash {
//Atributo
Object [] th;
//Constructor
public Hash(int n){
th=new Object[n];
for(int i=0; i<n;i++){
th[i]=null;
}
}
//Métodos
public void creaTabla(Object[]a, int nmax){
int pos;
for(int i=0; i<a.length;i++){
//Genera la posición del elemento a insertar
//Haciendo uso de una función hash
pos=a[i].hashCode()%nmax;
System.out.println("Elemento :"+a[i]+ " pos = " + pos);
//cuando la función devuelve un valor negativo
if(pos<0){
pos*=-1;
}
if(th[pos]==null){
//Inserta en la tabla sin colisión
th[pos]=a[i];
}else{
while(th[pos]!=null){
pos++;
if(pos==th.length){
pos=0;
}
}
//Inserta el valor en la tabla hash despues de una colicion
th[pos]=a[i];
}
}
presenta("TABLA HASH",th);
}
public void buscarHash(Object elemb, int nmax){
int e=elemb.hashCode();
if(e<0){
e*=-1;
}
int pos=e%nmax;
if(th[pos]==null){
System.out.print("Elemento no encontrado");
}else{
if(th[pos].equals(elemb)){
System.out.print("Elemento encontrado, "+elemb+ " su posicion es : "+ pos);
}else{
int j=pos+1;
if(j==th.length){
j=0;
}
while((th[j]!=elemb)&&(th[j]!=null)&&(j!=pos)){
j++;
if(j>=th.length-1){
j=0;
}
}
if(th[j].equals(elemb)){
System.out.print("Elemento encontrado, "+elemb+ " su posicion es : "+ j);
}else{
System.out.print("Elemento no encontrado");
}
}
}
}
public void presenta(String msg,Object a[]){
System.out.print(msg+" [");
for(int i=0; i<=a.length-1;i++){
if(i<a.length-1){
System.out.print(a[i]+",");
}else{
System.out.print(a[i]+"]");
}
}
System.out.print("\n");
}
public static void main(String args[]){
Object l[]= {12,45,76,34,90,45,56,78};
Hash bh=new Hash(l.length*2);
bh.presenta("Elementos a insertar en la Tabla Hash",l);
bh.creaTabla(l,l.length);
bh.buscarHash(34,l.length);
}
}