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úemro 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 de 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
Fuente: www.algoritmia.net