Metodos de busqueda hash y binaria
Páginas: 4 (792 palabras)
Publicado: 15 de febrero de 2012
METODOS DE BUSQUEDA
HASH
Caracteristicas
Es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmentemenor. Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada.
Descripcion
En este método se requiere que los elementos esténordenados.
El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funcionespara transformar el elemento y el número obtenido es el índice del elemento.
La principal forma de transformar el elemento es asignarlo directamente, es decir al 0 le corresponde el índice 0, al 1 el1, y así sucesivamente pero cuando los elementos son muy grandes se desperdicia mucho espacio ya que necesitamos arreglo grandes para almacenarlos y estos quedan con muchos espacios libres, parautilizar mejor el espacio se utilizan funciones mas complejas.
Algoritmo
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 lecorresponda 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 cadaproblema 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 detamañ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úmeroidentificativo 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 =...
HASH
Caracteristicas
Es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmentemenor. Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada.
Descripcion
En este método se requiere que los elementos esténordenados.
El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funcionespara transformar el elemento y el número obtenido es el índice del elemento.
La principal forma de transformar el elemento es asignarlo directamente, es decir al 0 le corresponde el índice 0, al 1 el1, y así sucesivamente pero cuando los elementos son muy grandes se desperdicia mucho espacio ya que necesitamos arreglo grandes para almacenarlos y estos quedan con muchos espacios libres, parautilizar mejor el espacio se utilizan funciones mas complejas.
Algoritmo
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 lecorresponda 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 cadaproblema 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 detamañ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úmeroidentificativo 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 =...
Leer documento completo
Regístrate para leer el documento completo.