HASHING

 HASHING
¿Qué es?
Método que mejora la eficiencia obtenida con árboles balanceados, asegurando en promedio un acceso a recuperar la información.
Hay 3 definiciones para este método:
Técnica para generar una dirección base única para una clave dada. La dispersión se usa cuando se requiere acceso rápido mediante una clave.
Técnica que convierte la clave asociada a un registro de datos en unnumero aleatorio, el cual posteriormente es utilizado para determinar donde se almacena dicho registro.
Técnica de almacenamiento y recuperación que usa una función para mapear registros en direcciones de almacenamiento en memoria secundaria.
Atributos:
No se requiere almacenamiento adicional. El archivo de datos resulta disperso al elegir hashing como método de organización de archivos. Se generaa partir de la clave o llave primaria del archivo, y el registro que contiene la información relacionada con la clave es ubicado en el espacio resultante de aplicar la función de hash. No necesario soporte auxiliar para acceder directamente a la información.
Facilita la inserción y eliminación rápida de registros en el archivo. Con un solo acceso a disco, un registro puede ser insertado oeliminado desde el archivo. (MAYOR VENTAJA)
Localiza registros dentro del archivo con un solo acceso a disco. OTRA VENTAJA, consiste en ubicar cada elemento de datos, en promedio, con un acceso a disco.
Limitaciones:
No es posible aplicar la técnica de dispersión en archivos con registros de longitud variable.
No es posible obtener un orden lógico de los datos. USA INDICES.
No es posible tratar conclaves duplicadas, ya que al poseer más de una clave secundaria, al aplicar este método, tendrían como resultado la misma dirección de memoria.
Tipos de Dispersión:
Hashing con espacio de direccionamiento estático: Aquella política donde el espacio disponible para dispersar los registros de un archivo de datos está fijado previamente.
Hashing con espacio de direccionamiento dinámico: Aquella políticadonde el espacio disponible para dispersar los registros de un archivo de datos aumenta o disminuye en función de las necesidades de espacio que en cada momento tiene el archivo.




Parámetros de Dispersión:
Función de hash: Función que transforma un valor, que representa una llave primaria de un registro, en otro calor dentro de un determinado rango, que se utiliza como dirección física deacceso para insertar un registro en un archivo de datos.
Claves sinónimas: Claves que deben almacenarse en la misma dirección de memoria. Esto no se permite dado al problema de los desbordes, por lo que hay dos soluciones:
Elegir un algoritmo de dispersión perfecto, que no genere colisiones.
Minimizar el número de colisiones a una cantidad aceptable y de esta manera tratar dichas colisiones comouna condición excepcional. Posee tres alternativas:
Distribuir los registros de la forma más aleatoria posible: Cuando dos claves compiten por la misma dirección de memoria.
Utilizar más espacio de disco: Su desventaja es el desperdicio de espacio.
Ubicar o almacenar más de un registro por cada dirección física del archivo.
Tamaño de cada nodo de almacenamiento: Su capacidad queda determinada por laposibilidad de transferencia de información en cada operación de entrada/salida desde RAM hacia disco.
Densidad de empaquetamiento: Relación entre el espacio disponible para el archivo de datos y la cantidad de registros que integran dicho archivo. Mayor DE, mayor posibilidad de colisiones debido a que disminuye el espacio en memoria. No es constante, al principio es baja (si se mantiene asídesperdicia espacio en el disco) y luego va en aumento.

DE= r
RPN * n

r es la cantidad de registros a dispersar.
RPN es la cantidad de registros por nodo.
n es la cantidad de nodos direccionales.
Métodos de tratamiento de desbordes (overflow): Ocurre cuando un registro es direccionado a un nodo que no dispone capacidad para almacenarlo. Cuando esto ocurre, se busca el lugar...