Hashing
El hash es una técnica para convertir un rango de valores clave en un rango de índices de una matriz. Vamos a utilizar el operador de módulo para obtener un rango de valores clave.
Como un ejemplo simple del uso de hashing en bases de datos, un grupo de personas podría organizarse en una base de datos como esta:
Abernath, Sara Epperdingle, Roscoe Moore, Wlfred Smith, David (y muchos más ordenados alfabéticamente)
Cada uno de estos nombres sería la clave en la base de datos para los datos de esa persona. Un mecanismo de búsqueda en la base de datos primero tendría que comenzar a buscar coincidencias carácter por carácter en el nombre hasta encontrar la coincidencia (o descartar las otras entradas). Pero si cada uno de los nombres se dividiera en hash, podría ser posible (dependiendo del número de nombres en la base de datos) generar una clave única de cuatro dígitos para cada nombre. Por ejemplo:
7864 Abernath, Sara 9802 Epperdingle, Roscoe 1990 Moore, Wlfred 8822 Smith, David (y así sucesivamente)
La búsqueda de cualquier nombre consistiría primero en calcular el valor hash (utilizando la misma función hash utilizada para almacenar el elemento) y luego comparar una coincidencia utilizando ese valor. En general, sería mucho más rápido encontrar una coincidencia en cuatro dígitos, cada uno con solo 10 posibilidades, que en una longitud de valor impredecible donde cada personaje tenía 26 posibilidades.
Además de una recuperación de datos más rápida, el hash también se usa para cifrar y descifrar firmas digitales (usado para autenticar a los remitentes y receptores de mensajes). La firma digital se transforma con la función hash y luego tanto el valor hash (conocido como resumen de mensaje) como la firma se envían en transmisiones separadas al receptor. Usando la misma función hash que el remitente, el receptor deriva un resumen de mensaje de la firma y lo compara con el resumen de mensaje que también recibió. (Deberían ser iguales.)
Sondeo lineal
Como podemos ver, puede suceder que la técnica de hashing utilizada cree un índice ya utilizado de la matriz. En tal caso, podemos buscar la siguiente ubicación vacía en la matriz buscando en la siguiente celda hasta que encontremos una celda vacía. Esta técnica se llama sondeo lineal.
Aquí hay algunas funciones hash relativamente simples que se han utilizado:
- Método de división-resto: se calcula el tamaño del número de elementos en la tabla. Ese número se utiliza como divisor en cada valor o clave original para extraer un cociente y un resto. El resto es el valor hash. (Dado que este método puede producir una serie de colisiones, cualquier mecanismo de búsqueda debería ser capaz de reconocer una colisión y ofrecer un mecanismo de búsqueda alternativo).
- Método de plegado: este método divide el valor original (dígitos en este caso) en varias partes, suma las partes y luego usa los últimos cuatro dígitos (o algún otro número arbitrario de dígitos que funcionará) como valor o clave hash.
- Método de transformación de radix: cuando el valor o la clave es digital, la base numérica (o radix) se puede cambiar, dando como resultado una secuencia diferente de dígitos. (Por ejemplo, una clave numerada decimal podría transformarse en una clave numerada hexadecimal). Los dígitos de alto orden podrían descartarse para ajustarse a un valor hash de longitud uniforme.
- Método de reordenación de dígitos: Esto simplemente toma parte del valor original o clave, como dígitos en las posiciones 3 a 6, invierte su orden y luego usa esa secuencia de dígitos como el valor hash o clave.
Hash Table, también conocido como Hash Map, es una estructura de datos que utiliza la función hash para generar la clave correspondiente al valor asociado.
Veamos algunas funciones hash de muestra para cadenas
Método de plegado: –
int h (Cadena x, int D)
{
int i, sum;
para (suma = 0, i = 0; i suma + = (int) x.charAt (i);
retorno (suma% D);
}
Cambio cíclico: –
static hashCode largo (clave de cadena, int D)
{
int h = 0;
para (int i = 0, i {
h = (h << 4) | (h >> 27);
h + = (int) key.charAt (i);
}
retorno h% D;
}
Hashing estático
- Un depósito es una unidad de almacenamiento que contiene uno o más registros (un depósito suele ser un bloque de disco).
- Los bloques de archivos se dividen en M cubos del mismo tamaño, cubos numerados0, cubeta1 … cubetaM-1. Típicamente, una cubeta corresponde a un bloque de disco (o un número fijo).
- En una organización de archivos hash obtenemos el depósito de un registro directamente de su valor de clave de búsqueda utilizando una función hash, h (K).
- El registro con el valor de la clave hash K se almacena en el depósito, donde i = h (K).
- La función hash se utiliza para ubicar registros para acceso, inserción y eliminación.
- Los registros con diferentes valores de clave de búsqueda pueden asignarse al mismo depósito; por lo tanto, se debe buscar secuencialmente todo el depósito para localizar un registro.
- páginas primarias fijas, asignadas secuencialmente, nunca desasignadas; páginas de desbordamiento si es necesario.
h ( K ) mod M = depósito al que pertenece la entrada de datos con la clave k . (M = # de cubos)
Hashing externo estático
- Uno de los campos del archivo está designado para ser la clave hash, K, del archivo.
- Las colisiones ocurren cuando un nuevo registro se desplaza a un depósito que ya está lleno.
- Se guarda un archivo de desbordamiento para almacenar dichos registros. Los registros de desbordamiento que se combinan con hash para cada depósito se pueden vincular entre sí.
- Para reducir los registros de desbordamiento, un archivo hash generalmente se mantiene lleno en un 70-80%.
- La función hash h debe distribuir los registros de manera uniforme entre los cubos; de lo contrario, el tiempo de búsqueda aumentará porque existirán muchos registros de desbordamiento.
Hashing estático (cont.)
- La función hash funciona en el campo clave de búsqueda del registro r. Debe distribuir valores en el rango 0 … M-1.
H ( K ) = (a * K + b) generalmente funciona bien.
ayb son constantes;
muchos conocidos sobre cómo sintonizar h .
- Las funciones hash típicas realizan el cálculo en la representación binaria interna de la clave de búsqueda.
Por ejemplo, para una clave de búsqueda de cadena, el binario
se podrían agregar representaciones de todos los caracteres en la cadena y se podría devolver el módulo de suma del número de cubos. .
- La función hash ideal es aleatoria , por lo que cada cubo tendrá
la misma cantidad de registros asignados independientemente de
La distribución real de los valores de la clave de búsqueda en el archivo.
Técnicas de hash dinámicas y extensibles
- Las técnicas de hash están adaptadas para permitir el crecimiento dinámico y la reducción del número de registros de archivos.
Estas técnicas incluyen lo siguiente:
- Hash extensible
- Hash lineal.
Estas técnicas de hashing utilizan la representación binaria del valor hash h (K).
En hashing dinámico, el directorio es un árbol binario.
En hashing extensible, el directorio es una matriz de tamaño 2d donde d se llama profundidad global.
Los directorios se pueden almacenar en el disco y se expanden o reducen dinámicamente. Las entradas de directorio apuntan a los bloques de disco que contienen los registros almacenados.
Una inserción en un bloque de disco que está lleno hace que el bloque se divida en dos bloques y los registros se redistribuyan entre los dos bloques.
El directorio se actualiza adecuadamente.
El hashing dinámico y extensible no requiere un área de desbordamiento.
El hashing lineal requiere un área de desbordamiento pero no utiliza un directorio. Los bloques se dividen en orden lineal a medida que el archivo se expande.
Hashing dinámico
- Bueno para bases de datos que crecen y se reducen de tamaño.
- Permite que la función hash se modifique dinámicamente
Hashing extensible : una forma de hashing dinámico
- La función hash genera valores en un rango amplio, típicamente enteros de b bits, con b = 32.
- En cualquier momento, use solo un prefijo de la función hash para indexar en una tabla de direcciones de depósito.
- Deje que la longitud del prefijo sea i bits, 0 _ i _ 32.
- Tamaño de la tabla de direcciones del cubo = 2i. Inicialmente i = 0
- El valor de i aumenta y disminuye a medida que aumenta y disminuye el tamaño de la base de datos.
- Múltiples entradas en la tabla de direcciones del depósito pueden apuntar a un depósito.
- Por lo tanto, el número real de cubos es <2 i
- El número de depósitos también cambia dinámicamente debido a la fusión y división de los depósitos.
Estructura de hash extensible general
Hashing lineal
- Este es otro esquema dinámico de hashing, una alternativa al Hashing extensible.
- LH maneja el problema de las cadenas de desbordamiento largas sin usar un directorio, y maneja duplicados.
- Idea : utilizar una familia de funciones hash h 0, h 1, h 2, …
h i ( clave ) = h ( clave ) mod (2iN); N = # cubos iniciales
h es alguna función hash (el rango no es de 0 a N-1)
Si N = 2 d0 , para algunos d0 , h i consiste en aplicar h y mirar los últimos di bits, donde di = d0 + i .
h i + 1 duplica el rango de h i (similar a la duplicación de directorios
Espero que esta explicación te ayude a saber tener técnica.
