• Author / Uploaded
• Alex Navez Mariños

Citation preview

A los profesores de la Universidad Nacional de Trujillo que nos han inculcado conocimiento para ser buenos profesionales.

AGRADECIMIENTOS

A Dios primeramente por darnos la vida, la oportunidad de estudiar y superarnos cada día más, y a las personas que nos apoyaron con este trabajo. Al docente Lourdes Díaz Amaya por contribuir con valiosas sugerencias, correcciones y críticas constructivas.

RESUMEN

En este Informe se dará uno de los accesos más directos o rápidos en ficheros es decir estamos hablando de FICHEROS DISPERSOS O TAMBIEN LLAMADO HASHING.

El tema se encuentra dentro del área conocida como METODOS DE ACCESO A FICHEROS, un subcampo del ORGANIZACIÓN DE ARCHIVOS.

Para implementar la aplicación se utilizará el entorno de programación DEV C++, también se usarán funciones del propio IDE y algunas creadas por nosotros mismos para la Intersección de palabras y cuando se compile nos vaya dando imágenes formadas

ABSTRACT

This report will be one of the most direct and rapid access to files is talking about hash files or also called hashing.

The issue is within the area known as methods of file access, a subfield of file organization.

To deploy the application will use the programming environment DEV C + +, also used the IDE itself functions and some created by ourselves for the intersection of words and when we go giving compile images formed

INTRODUCCION

Una técnica de búsqueda completamente diferente de las basadas en estructuras de arboles de comparación es de la DISPERSION un método que permite hacer directamente referencia a los registros de una tabla por medio de transformaciones aritméticas sobre las claves para obtener direcciones de la tabla. Si se sabe que las claves son enteros distintos entre 1 y N, entonces se puede almacenar un registro con clave i en la posición i de la tabla preparado para que se acceda a el de forma inmediata con el valor de la clave. La DISPERSION es una generalización de este método trivial en aplicaciones de búsqueda típicas donde no se tienen ningún conocimiento concreto sobre los valores de las claves.

En primer paso en una búsqueda por dispersión consiste en evaluar una FUNCION DE DISPERSION que transforma la clave de búsqueda en direcciones de la tabla. Idealmente, diferentes claves deben dar diferentes direcciones , pero ninguna función de dispersión es perfecta y dos o más claves diferentes a pueden dar la misma dirección de la tabla. La segunda parte de una búsqueda por dispersión es pues un proceso de RESOLUCION DE COLISIONES que permite tratar este tipo de claves.

La Dispersión es un buen ejemplo del compromiso ESPACIO-TIEMPO, si no hubiera limitación de memoria, se podrá hacer cualquier búsqueda con un solo acceso a la memoria, utilizando simplemente la clave de cómo una dirección de memoria. Si no hubiera limitaciones de tiempo se podría hacer con un mínimo de memoria utilizando un método secuencial de búsqueda. La dispersión proporciona una forma de utilizar razonablemente la memoria y el tiempo para obtener un equilibrio entre estos dos extremos. El empleo eficaz de la memoria disponible y un rápido acceso a la memoria son los objetivos básicos de cualquier método de dispersión.

FICHEROS DISPERSOS DEFINCION: Los archivos directos explotan la capacidad de los discos para acceder directamente a cualquier bloque de dirección conocida. Como en los archivos secuenciales y secuenciales indexados, se requiere un campo clave en cada registro. Sin embargo, aquí no hay concepto de ordenamiento secuencial. Dirección de cada registro: se calcula aplicando cierta función sobre uno de sus campos, el campo de dispersión. Acceso a los datos: muy rápido sólo si se busca con la condición de igualdad sobre el Campo de dispersión. La dispersión se puede utilizar a nivel interno (RAM), como una estructura de datos de un programa, o bien a nivel externo para ficheros en disco.

Dispersión Interna Funciones más comunes:  h(K) = K mod M ---  Partir el campo en trozos y sumarlos o aplicar función lógica.  Extraer ciertos dígitos del campo.

Resolución de colisiones:

 Direccionamiento abierto.  Encadenamiento. ---



Dispersión múltiple.

DISPERSION ESTATICA La función de dispersión produce un número de bloque relativo. En una tabla que se guarda en la cabecera del fichero se convierte ese número relativo en una dirección efectiva del disco (bloque o cluster).

Manejo de colisiones mediante encadenamiento: cada bloque con colisiones tiene un puntero a una lista de registros de desbordamiento (overflow). Los registros de esta lista están encadenados (enlazados por punteros).

Buscar:

Por el campo de dispersión: muy eficiente. Por otro campo: búsqueda lineal.

Leer ordenadamente: Caro (las funciones de dispersión no suelen mantener los registros en un orden). Insertar:

Aplicar la función de dispersión y si hay colisión aplicar el algoritmo correspondiente.

Eliminar:

Encontrar registro y borrarlo. Si hay lista de desbordamiento, mover un registro de la lista al bloque. Encontrar y modificar. Si se modifica el campo de dispersión: cambiar el registro de lugar (borrar e insertar).

Modificar:

Gran inconveniente de la dispersión estática: el espacio de almacenamiento es fijo.  Si hay menos de registros de los que caben: hay espacio no utilizado.



Si hay más de registros de los que caben: habrá largas listas de desbordamiento --> acceso muy lento.

Técnicas que permiten la expansión dinámica del fichero

Resultado de la función de dispersión -> número entero no negativo -> se puede representaren binario. Los registros se distribuyen teniendo en cuenta los primeros bits de este número, al que se Denomina valor de dispersión.

DISPERSION EXTENSIBLE

Ejemplo

TABLA DE HASH "Hashing" es una técnica que busca realizar las operaciones de inserción, eliminación y búsqueda en tiempo constante. Esa característica es muy importante cuando se traba con almacenamiento secundario en disco, donde el acceso a una determinada dirección es bastante lenta. Algunas aplicaciones que son beneficiadas por el uso de tablas hash son diccionarios y tablas de palabras reservadas de un compilador. En vez de organizar la tabla según el valor relativo de cada llave en relación a las demás, la tabla hash toma encuentra solamente su valor absoluto, interpretado como un valor numérico.

Si consiguiésemos asociar a cada elemento a ser almacenado un número como en el ejemplo anterior, podremos realizar las

operaciones de inserción, eliminación y búsqueda en tiempo constante. La función que asocia a cada elemento de un conjunto U un número que sirva de índice en una tabla (array) es llamada de función hash. Una función hash debe satisfacer las siguientes condiciones: 1. Ser simple de calcular 2. Asegurar que elementos distintos posean índices distintos. 3. Generar una distribución equilibrada para los elementos dentro del array.

Funciones Hash Crear una función hash satisfaciendo las condiciones anteriores no siempre es una tarea fácil. Existen mucho modelos de creación para funciones hash. A continuación se presentan apenas dos formas de creación de funciones hash. en "Cormen,T.H. Leiserson C.E., Rivest R.L. Introduction to Algorithms" pueden ser encontraod varios ejemplos afines hash. Una buena función hash es aquella en que toda entrada (slot) del array posee la misma probabilida de ser alcanzado por la función.

Método da División El método de la división consiste en los siguiente: suponga que los elementos x que deben ser almacenados sean números enteros, una función hash que puede ser utilizada para distribuir tales números en un array (tabla hash) es: h(x)=x% (tamaño de la tabla)

Implementación

La siguiente función describe la implementación de la función hash descrita anteriormente para el caso de strings. int Hash(char *a, int stringsize) { int hashval, j; hashval = (int) a[0]; for (j = 1; j < stringsize; j++) hashval += (int) a[j]; return(hashval % tablesize); /* suponiendo que tablesize es global */ }

Método del Doblado En este método, las llaves son interpretadas como una secuencia de dígitos escritos en un pedazo de papel. Ello consiste en "doblar" ese papel, de manera que los dígitos se superpongan sin llevar en consideración el "se lleva uno" como se muestra en la siguiente figura.

El proceso es repetido hasta que los dígitos formen un número menor al del tamaño de la tabla hash. Es importante resaltar que el metodo de doblar también puede ser usado con números binarios. En este caso, en vez de la suma, se debe realizar una operación de "OR exclusivo", pues operaciones de "AND" y de "OR" tienden a producir direcciones-base concentrados al final o al inicio de la tabla.

COLISIONES Por más que se intente encontrar una función hash eficiente, en aplicaciones prácticas es difícil conseguir evitar el problema de colisiones de llaves. Así, se vuelve necesario estudiar alternativas para este problema.

Existen varias formas de resolver el problema de colisiones, dentro de ellas destacamos: Encadenamiento Separado o Externo (Separate Chaining) En el encadenamiento separado colocamos los elementos que poseen llaves iguales en una listas encadenada.

Utilizando esta estrategia, no es difícil percibir que en el peor de los casos el tiempo para insertar un nuevo elemento en la tabla es de O(1). La búsqueda por un elemento, toma el tiempo proporcional al tamaño de la lista almacenada en cada slot. Encadenamiento Interno Encadenamiento interno es un método para resolver problemas de colisiones mediante el empleo de listas encadenadas que comparten el mismo espacio de memoria al de la tabla de distribución.

El encadenamiento interno prevee la división de la tabla T en dos zonas, una de dirección-base, de tamaño p, y otra reservada para colisiones, de tamaño s. Naturalmente, p+s = m, donde m corresponde al tamaño de la tabla hash.

Un problema de esta técnica es que ella puede provocar colisiones secundaria, eso quiere decir, que puede provocar colisiones provenientes de la coincidencia de direcciones para llaves que no son sinónimas. Este fue el caso ocurrido en al figura anterior cuando se intentó insertar el número 02. En la dirección base de este número ya se encontraba el número 14, el cual no es sinónimo de 02. Otra dificultad de esta técnica se encuentra en la función de eliminación de un elemento. Es necesario tomar cuidado en este procedimiento para que la llamada de búsqueda y eliminación futuras no retornen falsos resultados.