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

...