Act 6 lab de algoritmos computacionales

Introducción

En esta actividad vamos a elaborar un resumen sobre los diferentes métodos de construcción, analizaremos cómo emplear cada uno de estos y cómo nos pueden ayudar a resolver diferentes problemas de búsqueda para listas de datos de manera rápida y efectiva.

Objetivo:

Creación de tablas hash.

Procedimiento Parte 1 (Elaborar un resumen de cada método de construcción).

Las tablas hashing constituyen un TAD especialmente indicado para la

manipulación y almacenamiento de la información en memoria secundaria.

Son tablas que relacionan claves con posiciones de memoria donde se almacenan

atributos.

Método de División

Este método consiste en tomar el resto de la división por m, el número de entradas de la tabla. Así h(k) = k mod m En C sería h(k) = k % m; Usar m = una potencia de 2 no es buena idea ya que el valor de hash queda dependiendo de sólo los bits menos significativos de k.

Ejemplo:

Si la tabla hash tiene tamaño m = 12 y la llave es k = 100, entonces h(k) = 100 mod 12 = 4.

Método Plegado

Consiste en sumar las partes directamente. Para ello debemos plegar el identificador por las fronteras de las partes y sumar los dígitos coincidentes.

Para las funciones de plegado: Dividir la clave en partes iguales y sumarlas. La suma de las partes puede realizarse de dos formas

a) Plegado por desplazamiento.

b) Plegado por las fronteras.

Si la clave es una cadena de caracteres, los dígitos de cada carácter vienen determinados por el valor decimal de la secuencia de cotejo correspondiente (ASCII, EBCDIC, etc.)

Ejemplo:

a) Cadena de ocho caracteres representada por los números de orden dentro de la secuencia de cotejo correspondiente.

b) Plegado por desplazamiento.

c) Plegado en las fronteras en base decimal.

d) Plegado en las fronteras en base binaria.

e) Detalle del plegado en base binaria.

Método Compresión

Éste método consiste en Dividir la clave en componentes, traducir su número de cotejo a binario y aplicar la operación xor y al resultado la operación resto de división entera.

Método Extracción

Método de la mitad del cuadrado: Si tenemos claves numéricas (si no las transformamos), calculamos su cuadrado y nos quedamos con algún número de la zona central del resultado. Nos quedamos con tantos dígitos como necesitemos para mapear el array.

Parte 2

Redacción con propias palabras del vídeo que se encuentra en el siguiente enlace:

https://www.youtube.com/watch?v=9tZsDJ3JBUA

El vídeo trata sobre las tablas hash, qué son y cómo funcionan.

Una tabla hash es una forma de almacenar información, la principal función de estas tablas es la de resolver problemas complejos de búsqueda rápida.

Para realizar una búsqueda lineal sobre un dato se debe hacer una iteración en todos los datos para encontrar el que estamos buscando, esto funciona para listas de datos cortas de pocos elementos, pero para listas grandes de cientos o miles de elementos.

Ahí es donde sirven las funciones hash, dónde gracias a ellas podemos encontrar el dato que necesitamos exactamente en un tiempo muy breve.

La función hash actúa leyendo la clave del dato, y lo convierte en un índice, lo que hace es dividir el numero y del residuo le asigna el valor de la casilla.

Para asignarle el valor a un dato, primero debemos de colocarle el valor ASCII a cada una de las letras, después lo sumamos y utilizamos el operador de módulo entre el número de casillas que tengamos disponibles.

Si tenemos un índice para dos valores diferentes se crea una colisión. Para solucionarlo existen diferentes maneras,

...