¿Qué es una tabla hash?
Una tabla hash es una estructura de datos particular que admite una operación principal *: dado un valor, una tabla hash le permite consultar si la tabla contiene o no ese valor (es decir, implementa un conjunto matemático). Hay muchas formas de implementar dicha estructura, pero la idea básica detrás de la mayoría de las implementaciones es más o menos la misma.
Dado un valor [math] x [/ math] para consultar, una función hash [math] h [/ math] se usa para transformarlo en un valor hash [math] h (x) [/ math], que es un pequeño entero no negativo Este valor hash se utiliza como índice en una matriz. En un escenario perfecto (vea la siguiente sección), el valor [math] x [/ math] estará en esta ubicación en la matriz si y solo si está presente en la tabla hash. Para la mayoría de los algoritmos de la tabla hash, las cosas no son tan simples, y hay pasos adicionales para determinar si [math] x [/ math] está en la tabla hash (ver resolución de colisión).
- ¿Es posible hacer investigación en informática como estudiante sin un profesor?
- ¿Cuál es el equivalente moderno de lo que era Xerox PARC hace décadas?
- ¿Qué es exactamente la interacción humano-computadora (HCI)?
- ¿Cuáles son las preguntas / temas de investigación más importantes en informática hoy en día?
- ¿Cuáles son algunos de los documentos de "lectura obligatoria" en el campo de VLSI y la arquitectura de computadoras?
* Muchas implementaciones también le permiten insertar valores en la tabla hash (en lugar de requerir que todos los valores se presenten a medida que se construye la tabla) y eliminar valores de la tabla hash.
¿Qué es el hashing perfecto?
Para un conjunto dado [math] S [/ math] de valores, se dice que una función hash [math] h [/ math] es perfecta si [math] h [/ math] transforma cada valor en [math] S [/ matemáticas] en un número entero distinto. De manera equivalente, [matemáticas] h [/ matemáticas] no tiene colisiones. Las funciones hash perfectas son importantes porque las tablas hash que usan funciones hash perfectas se pueden implementar como describí anteriormente, cada valor en la tabla hash se puede almacenar en el índice de su valor hash.
¿Qué es el algoritmo de hash perfecto CHD?
Nota: Para lo siguiente, omitiré todas las matemáticas involucradas en el análisis. Para el tratamiento adecuado, vea el documento real. La descripción del algoritmo dada allí no es realmente tan difícil de entender.
El algoritmo de hash perfecto CHD describe un algoritmo para construir una función hash. El algoritmo real para el hash es como se describió anteriormente, simplemente aplique la función hash e indexe en una matriz.
Dado un conjunto [math] S [/ math] de elementos [math] n [/ math] y un número entero [math] m> n [/ math], el algoritmo de hash perfecto CHD para construir una función hash funciona de la siguiente manera.
Se elige un número entero [math] r [/ math] y una función hash [math] g [/ math] donde [math] g [/ math] transforma los valores en enteros no negativos menores que [math] r [/ math] . Esta función hash puede asignar múltiples valores en [math] S [/ math] al mismo valor hash, eso está bien.
Se elige una familia universal [math] U [/ math] de funciones hash [math] f_1, f_2, f_3, \ dots [/ math] que transforma los valores en enteros no negativos menores que [math] m [/ math]. En términos generales, una familia universal de funciones hash es una secuencia de funciones hash elegidas al azar que no tienen una relación perceptible entre sí (es decir, son independientes).
// Esto terminará siendo nuestra matriz de elementos
deje que la tabla sea una matriz vacía con m ranuras
// Esta estructura terminará describiendo nuestra función hash
deje que los índices sean una matriz vacía con ranuras r
// Esto se usa para la contabilidad. ¿Qué valores hash ya hemos usado?
dejar que used_values sea un conjunto vacío
para i = 0 a r-1
let bucket = el subconjunto de S que g se transforma en i
para j = 1 hasta el infinito
deje que los valores sean el conjunto que resulta de aplicar f_j a los elementos del depósito
si | valores | = | cubo | y (los valores y los valores_utilizados son disjuntos)
para x en el cubo
establecer tabla [f_j (x)] = x
agregar todos los elementos de valores a used_values
establecer índices [i] = j
ir a end_loop
etiqueta: end_loop
// Esta es nuestra función hash real.
define f (x) =
dejar i = g (x)
dejar j = índices [i]
devuelve f_j (x)
Esencialmente, para cada “grupo” de valores que [math] g [/ math] se asigna al mismo valor hash, elegimos una de nuestras funciones hash [math] f_j [/ math]. Nuestra función hash final [math] f [/ math] se asigna a los mismos valores que [math] f_j [/ math] en las entradas de ese segmento. Elegimos las funciones hash particulares [math] f_j [/ math] para que terminemos sin colisiones.
Resulta que cuando haces esto correctamente (en lugar de pasar por los cubos de [math] i = 0 \ text {to} r-1 [/ math], debes ir en orden descendente por tamaño del cubo), esto El algoritmo toma tiempo lineal. Además, los índices de las funciones hash que utiliza terminan siendo muy pequeños y fáciles de almacenar en formato comprimido.
