Hash modular

Universidad Tecnológica de Chile
Inacap
Concepción- Talcahuano

Función Hashing:
Aritmética Modular

Alumnos: Pedro Avaria
Eliel Videla
Docente: Pilar Pardo

Concepción, 16 de abril del 2014

Índice

Índice ................................................................................................................................ 2
Introducción..................................................................................................................... 3
¿Qué es Hashing? ........................................................................................................... 4
Métodos de búsqueda ..................................................................................................... 5
Aritmética Modular.......................................................................................................... 6
Ejemplos........................................................................................................................... 7
Colisiones ........................................................................................................................ 8
Resolución de colisiones................................................................................................ 9
Mejor caso ...................................................................................................................... 11
Caso Promedio .............................................................................................................. 11
Peor caso....................................................................................................................... 11
Ventajas .......................................................................................................................... 12
Desventajas .................................................................................................................... 12
Conclusión..................................................................................................................... 13

Introducción
Muchas actividades humanas requieren que en ellas las diferentes colecciones de
elementos utilizados se coloquen en un orden específico. Las oficinas de correo por
ejemplo ordenan cartas y los paquetes por códigos postales con el objeto de conseguir
una entrega eficiente; los anuarios o guías telefónicas ordenansus clientes por orden
alfabético de apellidos con el fin último de encontrar fácilmente el número de teléfono
deseado; los estudiantes de una clase en la universidad se ordenan por sus apellidos o
por los números de rut, etc. Por esta circunstancia una de las tareas que realizan más
frecuentemente las computadoras en el procesamiento de datos es la ordenación y la
búsqueda.
El estudio dediferentes métodos de ordenación es una tarea intrínsecamente
interesante desde un punto de vista teórico y, naturalmente, práctico. Con el presente
informe se pretende entender los principales métodos de búsqueda para tener
conocimiento a priori para su posterior aplicación en la informática.

Funciones Hashing
¿Qué es Hashing?
Ahora bien en la búsqueda binaria (como ejemplo) proporciona unmedio para reducir el
tiempo requerido para buscar en una lista. Este método, sin embargo, exige que los dato
estén ordenados. Existen otros métodos que pueden aumentar la velocidad de búsqueda
en el que los datos no necesitan estar ordenados, este método se conoce como
transformación de claves (clave – dirección) o Hashing1.
El método de transformación de claves consiste en convertir laclave dada (numérica o
alfanumérica) e una dirección (índice) dentro del arreglo. La correspondencia entre las
claves y la dirección en el medio de almacenamiento o en el arreglo se establece por una
función de conversión (función o hash).

La imagen anterior muestra el ejemplo de registro (rut o dni) que pasa a través de un
proceso de Hashing para su asignación en la tabla pequeña.

1...