Algoritmos hash

El artículo sucumbió a un borrado rápido. Ver el registro de borrado en Wikipedia

Como se sabe el hash en computación es uno de los temas más importantes debido a que se creó por la necesidad de reducir al máximo los costos de búsqueda de archivos y datos en computación. El hashing emplea funciones hash, las cuales son funciones matemáticas, en computación algunos de los más comunes son los algoritmos de división, desplazamiento, plegado, análisis de dígitos y conversión base entre otros. Cabe recalcar que cada sistema operativo puede variar en el uso de un algoritmo en particular, por ejemplo, Linux utiliza MD5 como función.

División

Se calcula la clave % N. Y consiste en tomar el residuo de la división de la clave entre el número de componentes del arreglo. La función hash queda definida por la siguiente fórmula:

               H(K)=(K % N)+1

Donde N se recomienda sea el número primo inmediato o cercano al total de datos del arreglo.

Plegado

Consiste en dividir la clave en partes de igual número de dígitos (la última puede tener menos) y operar con ellas, tomando como dirección los dígitos menos significativos. La operación entre las partes puede hacerse por medio de sumas o multiplicaciones. La función hash queda definida por la siguiente fórmula:

               H(K)= dig_men_sig((d1...di) + (di + 1...dj)...+(d1...dn)) + 1

Desplazamiento

Se desplazan los siguientes dígitos de los extremos hacia el centro en la medida de la longitud de la dirección y se suman.

Análisis de Dígitos

Se eliminan de la clave los dígitos que más afectan a la no homogeneidad, después se aplica cualquier otro tipo de técnica.

Conversión Base

Se supone la clave escrita en una base (normalmente un número primo) y se pasa a base 10, después se eliminan.

División Polinómica

Se utiliza una constante que no sea cero, a!=1, y se calcula:

                (x0 a^(k-1) + x1 a^(k-2)+...+xk-1)

Esto es un polinomio simple en a que toma los componentes (x0, x1,...,xk-1) como caracteres de la cadena de entrada de longitud k. El valor de a es generalmente un número primo.

Centro de Cuadrados

Consiste en elevar al cuadrado la clave y tomar los dígitos centrales como dirección. El número de dígitos a tomar queda determinado por el rango del índice. La función hash queda definida por la siguiente fórmula:

                 H(K)=digitos_centrales(K^2)+1

Función Truncamiento

Consiste en tomar algunos dígitos de la clave y formar con ellos una dirección. La función hash queda definida por la siguiente fórmula:

                 H(K)=elegir_dígitos(d1, d2,..., dn)+1

Restas Sucesivas

Esta función se emplea con claves numéricas entre las que existen huecos de tamaño conocido, obteniéndose direcciones consecutivas. Un ejemplo serían los alumnos de ingeniería en sistemas que entraron en el año 2005 sus números de control son consecutivos y está definido el número de alumnos.

05210800 -05210800 → 0

05210801 -05210800 → 1

05210802 -05210800 → 2

…

05210899 -05210800 → 99

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 dos o más elementos pueden producir el mismo residuo y un índice puede ser señalado por varios elementos. A este fenómeno se le llama colisión. Si el número N es el 7, los números siguientes quedan transformados en:

1679 → 6

4567 → 3

8471 → 1

0435 → 1

5033 → 0

Mientras más grande sea número de elementos es mejor escoger un número primo mayor para seccionar el arreglo en más partes. El número elegido da el número de partes en que se secciona el arreglo, y las cada sección está compuesta por todos los elementos que arrojen el mismo residuo, y mientras más pequeñas sean las secciones la búsqueda se agilizara más que es lo que nos interesa.

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.

709^2=502681 → 26

456^2=207936 → 79

105^2=011025 → 10

879^2=772641 → 26

619^2=383161 → 31

Nota: en caso de que la cifra resultante tenga un número de dígitos impar, se toma el valor número y el anterior.