Metodos de ordenamiento

METODOS DE ORDENAMIENTO

HASHING

Método de búsqueda hashing

Hash: se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.

Es un método debú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ónal 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.

Ventajas:

1. Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar2. Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones
3. No se requiere almacenamiento adicional para los índices.

Desventajas:

1. No pueden usarse registros de longitud variable
2. El archivo no esta clasificado
3. No permite llaves repetidas
4. Solo permite acceso por una sola llave

Costos

 Tiempode procesamiento requerido para la aplicación de la función hash
 Tiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.

La eficiencia de una función hash depende de:

1. La distribución de los valores de llave que realmente se usan
2. El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones
3. El numerode registros que pueden almacenarse en una dirección dad sin causar una colisión
4. La técnica usada para resolver el problema de las colisiones

Función Hash

Es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor. Varían en los conjuntos de partida y de llegada y en cómo afectan a lasalida similitudes o patrones de la entrada
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:

 Residuo de la división
 Medio del cuadrado
 Pliegue

 Hashing por residuo de la división

La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).Mientras que el valor calculado real de una dirección relativa, dados tanto un valor de llave como el divisor, es directo; la elección del divisor apropiado puede no ser tan simple. Existen varios factores que deben considerarse para seleccionar el divisor:

1. El rango de valores que resultan de la operación "llave % divisor", va desde cero hasta el divisor 1. Luego, el divisor determina el tamaño...