Ensayo Seguridad WEB: Tablas Hash
Tablas Hash
Introducción:
Este ensayo hablara a cerca de lo que son las tablas hash
como funcionan y más que nada saber cómo se usan y en que nos benefician o
ayudan para un posible mecanismo de seguridad, todas estas preguntan se responderán
a continuación, pero para empezar debemos definirlas como un diccionario, muchas
aplicaciones requieren de un mecanismo que soporte las operaciones de un
diccionario: Insert, Search, Delete. La tablas Hash son estructuras tipo vector
que ayudan asociar claves con valores o datos, pero a ello vamos a definirlo
mejor.
Desarrollo:
Como antes lo habíamos mencionado, una tabla hash es un
contenedor asociativo que permite almacenar y recuperar eficientemente
elementos, a partir de otros objetos que son las claves. Una tabla hash se
puede ver como un conjunto de entradas. Cada una de estas entradas tiene
asociada una clave única, y por lo tanto, diferentes entradas de una misma
tabla tendrán diferentes claves. Esto implica, que una clave identifica claramente
a una entrada en una tabla hash.
Las entradas de las tablas hash están compuestas por dos
componentes, la clave y la información que se almacena en dicha entrada. Una
tabla hash está formada por un array de entradas, que será la estructura que
almacene la información, y por una función de dispersión. La función de
dispersión permite asociar el elemento almacenado en una entrada con la clave
de dicha entrada
Proveen un tiempo constante de búsqueda O(1), la idea
surge de los arreglos que nos permiten acceso a sus elementos en orden O(1). Una opción sería usar un arreglo tan grande
como el rango de posibles claves. La desventaja es el espacio de memoria
requerido en tal estrategia
Cabe destacar que cuando se usan tablas hash es frecuente
que se produzcan colisiones. Las colisiones se producen cuando para dos
elementos de información distintos, la función de dispersión les asigna la
misma clave. Como se puede suponer, esta solución se debe arreglar de alguna
forma. Para ello las tablas hash cuentan con una función de resolución de
colisiones.
El aspecto más significativo de la búsqueda por hashing
es que si eficiencia depende del denominado factor de almacenamiento Ó= n/M con
n el número de items y M el tamaño de la tabla.
Por lo tanto hay dos tipos de tablas hash que se
resuelven por este método de colisiones:
|
Encadenamiento
separado(Hashing abierto)
|
Direccionamiento
abierto (Hashing cerrado)
|
|
Al número medio de
claves por lista se le llama factor de carga y habría que intentar que esté
próximo a 1.
|
Utilizamos un
vector y cuando ocurra una colisión, le reasignamos otro valor hash a la
clave hasta que haya un hueco disponible.
|
|
Las fórmulas paroximadas son:
Cuando Ó>1
|
De esta forma la
función de rehashing quedaria de la siguiente forma:
rehi(k) = (h(k)+(i-1)) mod M i=2,3,..
|
Generalmente, lo mejor es usar el encadenamiento separado
para reducir los tiempos de búsqueda cuando el número de registros a procesar
no se conoce de antemano.
Las operaciones que se presentan en esta aplicación son
las siguientes:
Insertar: Para insertar un elemento hay que introducir,
en el campo de texto del diálogo lanzado al pulsar el botón Insertar, el valor
deseado. Este valor puede ser un número entero o una cadena de caracteres.
Borrar: Si se desea borrar un nodo se debe seleccionar
dicho nodo y pulsar el botón Borrar.
Vaciar lista: Esta acción elimina todos los elementos
presentes en la tabla.
Existen varios métodos de resolución pero solo hablaremos
de 2 que considero más importantes, uno es el Hashing Abierto y Hashing Cerrado, también destacaremos las funciones Hash como por ejemplo el Método de
Multiplicación y el Método de División:
Hashing Abierto:
Es cuando cualquier elemento es igualmente probable de
caer en cualquiera de las m entradas de la tabla hash, independientemente de
cualquier otro elemento, obviamente la cantidad de tiempo requerido para una
búsqueda dependerá de la longitud de las listas y de las posiciones relativas
de las claves en ellas. En hashing abierto la búsqueda no exitosa de una clave
toma tiempo Ó(1+α),donde α es el factor de carga =número de claves en la
tabla/número de entradas en la tabla hash Análogamente la búsqueda exitosa de
una clave toma un tiempo Θ(1+α/2), la inserción de una clave toma Θ(1), la
eliminación de una clave toma un tiempo Θ(1+α). Aquí suponemos que la clave
debe ser buscada dentro de la lista, para luego ser eliminada.
Hashing Cerrado:
En este caso nos encontramos con el problema de que en el
caso de que se produzca una colisión no se pueden tener ambos elementos
formando parte de una lista para esa casilla. Para solucionar ese problema se
usa lo que se llama rehashing. El rehashing consiste en que una vez producida
una colisión al insertar un elemento se utiliza una función adicional para
determinar cuál será la casilla que le corresponde dentro de la tabla, a esta
función la llamaremos función de rehashing, rehi(k).
En Hashing cerrado todos los elementos o claves son
almacenadas en la tabla hashing misma. Es decir cada entrada de la tabla
contiene un elemento del conjunto dinámico o null. Cuando se busca, examinamos
varias entradas hasta encontrarlo o es claro que no está. No hay una lista ni elementos almacenados
fuera de la “tabla”. La tabla de podría
llenar. El factor de carga no puede exceder 1.
Método de Multiplicación:
Esta técnica trabaja
multiplicando la clave k por sí misma o por una constante, usando después alguna
porción de los bits del producto como una localización de la tabla hash.
Primero, multiplicamos la clave por una constante A en el
rango 0 < A < 1 y extraemos la parte fraccionaria de k*A.
Segundo, Multiplicamos este valor por el número de
entradas de la tabla y tomamos el piso del (o truncamos el) resultado.
Método de División:
La función se
calcula simplemente usando h(k) = k mod M donde el 0 es el primer índice de la tabla hash de
tamaño M
Una forma de hacer hash(k) dependiente de todos los bits
menos significativos es usar número primos no muy cercanos a una potencia de
dos
Conclusión:
Las tablas hash son una forma muy compleja de almacenar
datos, el mecanismo que utiliza para que funcione al menos las dos principales
que yo veo son, que tiene un almacenamiento asociativo y que al tratar de recuperar la información lo
hace de manera muy eficiente. Por lo
tanto, las tablas hash son muy útiles cuando el tiempo hay que acceder a la
información de forma crítica. La gran eficiencia que proporcionan estas tablas permite
que sean las estructuras de datos escogidas, en situaciones como la
implementación de la tabla de símbolos dentro de un compilador.
Referencias:
The Human
Communication and Interaction Research Group(18/11/2017)
Tablas Hash, obtenido de:
Universidad de Granada (18/11/2017)
Tablas Hash, obtenido de:
Benemérita Universidad Autónoma de Puebla (BUAP) (18/11/2017)
Tablas Hash y Árboles binarios, obtenido de:
Agustín J. González (2002)
Tablas Hash, ELO320: Estructura de Datos y Algoritmos,
obtenido de:
EcuRed (18/11/2017)
Tabla Hash, obtenido de:
Comentarios
Publicar un comentario