Una función hash es cualquier función que se puede utilizar para mapear datos de tamaño arbitrario a valores de tamaño fijo, aunque hay algunas funciones hash que admiten salida de longitud variable. [1] Los valores devueltos por una función hash se denominan valores hash , códigos hash , resúmenes hash , resúmenes o simplemente hashes . [2] Los valores se utilizan normalmente para indexar una tabla de tamaño fijo denominada tabla hash . El uso de una función hash para indexar una tabla hash se denomina hash o direccionamiento de almacenamiento disperso .
Las funciones hash y sus tablas hash asociadas se utilizan en aplicaciones de almacenamiento y recuperación de datos para acceder a los datos en un tiempo pequeño y casi constante por recuperación. Requieren una cantidad de espacio de almacenamiento solo una fracción mayor que el espacio total requerido para los datos o registros en sí. El hash es una forma de acceso a los datos eficiente en términos de espacio de almacenamiento y computacional que evita el tiempo de acceso no constante de las listas ordenadas y desordenadas y los árboles estructurados, y los requisitos de almacenamiento a menudo exponenciales del acceso directo a espacios de estados de claves grandes o de longitud variable.
El uso de funciones hash se basa en propiedades estadísticas de la interacción de la clave y la función: el comportamiento en el peor de los casos es intolerablemente malo pero poco común, y el comportamiento en el caso promedio puede ser casi óptimo ( colisión mínima ). [3] : 527
Las funciones hash están relacionadas con (y a menudo se confunden con) sumas de comprobación , dígitos de control , huellas dactilares , compresión con pérdida , funciones de aleatorización , códigos de corrección de errores y cifrados . Aunque los conceptos se superponen hasta cierto punto, cada uno tiene sus propios usos y requisitos y está diseñado y optimizado de manera diferente. La función hash se diferencia de estos conceptos principalmente en términos de integridad de datos . Las tablas hash pueden utilizar funciones hash no criptográficas , mientras que las funciones hash criptográficas se utilizan en ciberseguridad para proteger datos confidenciales como contraseñas.
En una tabla hash, una función hash toma una clave como entrada, que está asociada con un dato o registro y se utiliza para identificarlo ante la aplicación de almacenamiento y recuperación de datos. Las claves pueden tener una longitud fija, como un número entero, o una longitud variable, como un nombre. En algunos casos, la clave es el dato en sí. La salida es un código hash utilizado para indexar una tabla hash que contiene los datos o registros, o punteros a ellos.
Se puede considerar que una función hash realiza tres funciones:
Una buena función hash satisface dos propiedades básicas: debe ser muy rápida de calcular y debe minimizar la duplicación de valores de salida ( colisiones ). Las funciones hash se basan en la generación de distribuciones de probabilidad favorables para su efectividad, reduciendo el tiempo de acceso a casi constante. Los factores de carga de tabla altos, los conjuntos de claves patológicos y las funciones hash mal diseñadas pueden dar como resultado tiempos de acceso que se acerquen a la linealidad en el número de elementos de la tabla. Las funciones hash se pueden diseñar para brindar el mejor rendimiento en el peor de los casos, [Notas 1] un buen rendimiento con factores de carga de tabla altos y, en casos especiales, un mapeo perfecto (sin colisiones) de claves en códigos hash. La implementación se basa en operaciones de bits que preservan la paridad (XOR y ADD), multiplicación o división. Un complemento necesario para la función hash es un método de resolución de colisiones que emplea una estructura de datos auxiliar como listas enlazadas o un sondeo sistemático de la tabla para encontrar una ranura vacía.
Las funciones hash se utilizan junto con las tablas hash para almacenar y recuperar elementos de datos o registros de datos. La función hash traduce la clave asociada con cada dato o registro en un código hash, que se utiliza para indexar la tabla hash. Cuando se agrega un elemento a la tabla, el código hash puede indexar una ranura vacía (también llamada contenedor), en cuyo caso el elemento se agrega a la tabla allí. Si el código hash indexa una ranura llena, entonces se requiere algún tipo de resolución de colisión: el nuevo elemento puede omitirse (no agregarse a la tabla), o reemplazar el elemento anterior, o agregarse a la tabla en alguna otra ubicación mediante un procedimiento específico. Ese procedimiento depende de la estructura de la tabla hash. En el hash encadenado , cada ranura es la cabeza de una lista o cadena enlazada, y los elementos que colisionan en la ranura se agregan a la cadena. Las cadenas pueden mantenerse en orden aleatorio y buscarse linealmente, o en orden serial, o como una lista autoordenada por frecuencia para acelerar el acceso. En el hash de direcciones abiertas , la tabla se sondea comenzando desde la ranura ocupada de una manera específica, generalmente mediante sondeo lineal , sondeo cuadrático o hash doble hasta que se encuentra una ranura abierta o se sondea toda la tabla (desbordamiento). La búsqueda del elemento sigue el mismo procedimiento hasta que se encuentra el elemento, se encuentra una ranura abierta o se ha buscado en toda la tabla (elemento que no está en la tabla).
Las funciones hash también se utilizan para crear cachés para grandes conjuntos de datos almacenados en medios lentos. Un caché es generalmente más simple que una tabla de búsqueda hash, ya que cualquier colisión se puede resolver descartando o volviendo a escribir el elemento más antiguo de los dos elementos en conflicto. [4]
Las funciones hash son un ingrediente esencial del filtro Bloom , una estructura de datos probabilística que aprovecha el espacio y que se utiliza para probar si un elemento es miembro de un conjunto .
Un caso especial de hash se conoce como hash geométrico o método de cuadrícula . En estas aplicaciones, el conjunto de todas las entradas es una especie de espacio métrico , y la función hash se puede interpretar como una partición de ese espacio en una cuadrícula de celdas . La tabla es a menudo una matriz con dos o más índices (llamados archivo de cuadrícula , índice de cuadrícula , cuadrícula de cubo y nombres similares), y la función hash devuelve una tupla de índice . Este principio se usa ampliamente en gráficos de computadora , geometría computacional y muchas otras disciplinas, para resolver muchos problemas de proximidad en el plano o en el espacio tridimensional , como encontrar pares más cercanos en un conjunto de puntos, formas similares en una lista de formas, imágenes similares en una base de datos de imágenes , etc.
Las tablas hash también se utilizan para implementar matrices asociativas y conjuntos dinámicos . [5]
Una buena función hash debería mapear las entradas esperadas de la manera más uniforme posible en su rango de salida. Es decir, cada valor hash en el rango de salida debería generarse con aproximadamente la misma probabilidad . La razón de este último requisito es que el costo de los métodos basados en hash aumenta drásticamente a medida que aumenta el número de colisiones (pares de entradas que se asignan al mismo valor hash). Si es más probable que ocurran algunos valores hash que otros, entonces una fracción mayor de las operaciones de búsqueda tendrán que buscar en un conjunto más grande de entradas de tabla en colisión.
Este criterio solo requiere que el valor esté distribuido de manera uniforme , no que sea aleatorio en ningún sentido. Una buena función de aleatorización es (salvo por cuestiones de eficiencia computacional) generalmente una buena opción como función hash, pero lo inverso no necesariamente es cierto.
Las tablas hash suelen contener solo un pequeño subconjunto de las entradas válidas. Por ejemplo, una lista de miembros de un club puede contener solo unos cien nombres de miembros, de un conjunto muy grande de todos los nombres posibles. En estos casos, el criterio de uniformidad debería cumplirse para casi todos los subconjuntos típicos de entradas que se pueden encontrar en la tabla, no solo para el conjunto global de todas las entradas posibles.
En otras palabras, si un conjunto típico de m registros se codifica en n espacios de tabla, entonces la probabilidad de que un contenedor reciba muchos más de m / n registros debería ser extremadamente pequeña. En particular, si m < n , entonces muy pocos contenedores deberían tener más de uno o dos registros. Una pequeña cantidad de colisiones es prácticamente inevitable, incluso si n es mucho mayor que m (consulte el problema del cumpleaños ) .
En casos especiales, cuando las claves se conocen de antemano y el conjunto de claves es estático, se puede encontrar una función hash que logre una uniformidad absoluta (o sin colisiones). Se dice que una función hash de este tipo es perfecta . No existe una forma algorítmica de construir una función de este tipo: la búsqueda de una es una función factorial del número de claves que se van a mapear en función del número de ranuras de tabla en las que se mapean. Encontrar una función hash perfecta sobre más de un conjunto muy pequeño de claves suele ser computacionalmente inviable; es probable que la función resultante sea más compleja computacionalmente que una función hash estándar y proporcione solo una ventaja marginal sobre una función con buenas propiedades estadísticas que produzca un número mínimo de colisiones. Véase función hash universal .
Al probar una función hash, la uniformidad de la distribución de los valores hash se puede evaluar mediante la prueba de chi-cuadrado . Esta prueba es una medida de bondad de ajuste: es la distribución real de los elementos en los grupos frente a la distribución esperada (o uniforme) de los elementos. La fórmula es
donde n es el número de claves, m es el número de depósitos y b j es el número de elementos en el depósito j .
Una relación dentro de un intervalo de confianza (por ejemplo, 0,95 a 1,05) es indicativa de que la función hash evaluada tiene una distribución uniforme esperada.
Las funciones hash pueden tener algunas propiedades técnicas que hacen que sea más probable que tengan una distribución uniforme cuando se aplican. Una es el criterio de avalancha estricto : siempre que se complementa un solo bit de entrada, cada uno de los bits de salida cambia con una probabilidad del 50%. La razón de esta propiedad es que los subconjuntos seleccionados del espacio de claves pueden tener una variabilidad baja. Para que la salida se distribuya uniformemente, una cantidad baja de variabilidad, incluso un bit, debe traducirse en una cantidad alta de variabilidad (es decir, distribución sobre el espacio de tablas) en la salida. Cada bit debe cambiar con una probabilidad del 50% porque, si algunos bits son reacios a cambiar, entonces las claves se agrupan alrededor de esos valores. Si los bits quieren cambiar demasiado fácilmente, entonces el mapeo se está aproximando a una función XOR fija de un solo bit. Se han descrito pruebas estándar para esta propiedad en la literatura. [6] Aquí se evalúa la relevancia del criterio para una función hash multiplicativa. [7]
En las aplicaciones de almacenamiento y recuperación de datos, el uso de una función hash es un equilibrio entre el tiempo de búsqueda y el espacio de almacenamiento de datos. Si el tiempo de búsqueda no tuviera límites, el mejor medio sería una lista lineal desordenada muy compacta; si el espacio de almacenamiento no tuviera límites, una estructura de acceso aleatorio indexable por el valor-clave sería muy grande y muy dispersa, pero muy rápida. Una función hash necesita una cantidad finita de tiempo para mapear un espacio de claves potencialmente grande a una cantidad factible de espacio de almacenamiento que se pueda buscar en una cantidad de tiempo limitada, independientemente del número de claves. En la mayoría de las aplicaciones, la función hash debería ser computable con una latencia mínima y, en segundo lugar, en un número mínimo de instrucciones.
La complejidad computacional varía según la cantidad de instrucciones requeridas y la latencia de las instrucciones individuales; los más simples son los métodos bit a bit (plegado), seguidos por los métodos multiplicativos, y los más complejos (más lentos) son los métodos basados en división.
Dado que las colisiones deberían ser poco frecuentes y causar un retraso marginal, pero por lo demás son inofensivas, suele ser preferible elegir una función hash más rápida en lugar de una que necesita más cálculos pero ahorra algunas colisiones.
Las implementaciones basadas en división pueden ser de particular preocupación porque la división está microprogramada en casi todas las arquitecturas de chips. La división ( módulo ) por una constante se puede invertir para convertirse en una multiplicación por el inverso multiplicativo del tamaño de una palabra de esa constante. Esto lo puede hacer el programador o el compilador. La división también se puede reducir directamente a una serie de operaciones de desplazamiento-sustracción y desplazamiento-adición, aunque minimizar el número de tales operaciones requeridas es un problema abrumador; el número de instrucciones de ensamblaje resultantes puede ser más de una docena y saturar el proceso. Si la arquitectura tiene unidades funcionales de multiplicación de hardware , entonces la multiplicación por inversa es probablemente un mejor enfoque.
Podemos permitir que el tamaño de la tabla n no sea una potencia de 2 y aún así no tener que realizar ninguna operación de resto o división, ya que estos cálculos a veces son costosos. Por ejemplo, sea n significativamente menor que 2 b . Considere una función generadora de números pseudoaleatorios P (key) que sea uniforme en el intervalo [0, 2 b − 1] . Una función hash uniforme en el intervalo [0, n − 1] es n P (key) / 2 b . Podemos reemplazar la división por un desplazamiento de bit a la derecha (posiblemente más rápido) : n P (key) >> b .
Si las claves se procesan repetidamente y la función hash es costosa, se puede ahorrar tiempo de cálculo calculando previamente los códigos hash y almacenándolos con las claves. La coincidencia de los códigos hash casi con certeza significa que las claves son idénticas. Esta técnica se utiliza para la tabla de transposición en programas de juegos, que almacena una representación hash de 64 bits de la posición del tablero.
Un esquema de hash universal es un algoritmo aleatorio que selecciona una función hash h entre una familia de tales funciones, de tal manera que la probabilidad de una colisión de dos claves distintas sea 1/ m , donde m es el número de valores hash distintos deseados, independientemente de las dos claves. El hash universal garantiza (en un sentido probabilístico) que la aplicación de la función hash se comportará tan bien como si estuviera usando una función aleatoria, para cualquier distribución de los datos de entrada. Sin embargo, tendrá más colisiones que el hash perfecto y puede requerir más operaciones que una función hash de propósito especial.
Una función hash que sólo permite ciertos tamaños de tabla o cadenas sólo hasta una cierta longitud, o que no puede aceptar una semilla (es decir, permite doble hash) es menos útil que una que sí lo hace. [ cita requerida ]
Una función hash se puede aplicar en diversas situaciones. En particular, en el ámbito de la criptografía, las aplicaciones más destacadas son las siguientes: [8]
Un procedimiento hash debe ser determinista : para un valor de entrada dado, siempre debe generar el mismo valor hash. En otras palabras, debe ser una función de los datos a los que se les aplicará el hash, en el sentido matemático del término. Este requisito excluye las funciones hash que dependen de parámetros variables externos, como los generadores de números pseudoaleatorios o la hora del día. También excluye las funciones que dependen de la dirección de memoria del objeto que se va a someter al hash, porque la dirección puede cambiar durante la ejecución (como puede suceder en sistemas que utilizan ciertos métodos de recolección de basura ), aunque a veces es posible volver a realizar el hash del elemento.
El determinismo se encuentra en el contexto de la reutilización de la función. Por ejemplo, Python agrega la característica de que las funciones hash hacen uso de una semilla aleatoria que se genera una vez cuando se inicia el proceso de Python además de la entrada a la que se le aplicará el hash. [9] El hash de Python ( SipHash ) sigue siendo una función hash válida cuando se usa dentro de una sola ejecución, pero si los valores se conservan (por ejemplo, se escriben en el disco), ya no se pueden tratar como valores hash válidos, ya que en la próxima ejecución el valor aleatorio podría diferir.
A menudo es deseable que la salida de una función hash tenga un tamaño fijo (pero vea más abajo). Si, por ejemplo, la salida está restringida a valores enteros de 32 bits, entonces los valores hash se pueden usar para indexar en una matriz. Este tipo de hash se usa comúnmente para acelerar las búsquedas de datos. [10] La producción de una salida de longitud fija a partir de una entrada de longitud variable se puede lograr dividiendo los datos de entrada en fragmentos de un tamaño específico. Las funciones hash utilizadas para búsquedas de datos usan alguna expresión aritmética que procesa iterativamente fragmentos de la entrada (como los caracteres en una cadena) para producir el valor hash. [10]
En muchas aplicaciones, el rango de valores hash puede ser diferente para cada ejecución del programa o puede cambiar durante la misma ejecución (por ejemplo, cuando se necesita expandir una tabla hash). En esas situaciones, se necesita una función hash que tome dos parámetros: los datos de entrada z y la cantidad n de valores hash permitidos.
Una solución común es calcular una función hash fija con un rango muy grande (por ejemplo, 0 a 2 32 − 1 ), dividir el resultado por n y usar el resto de la división . Si n es en sí mismo una potencia de 2 , esto se puede hacer mediante enmascaramiento de bits y desplazamiento de bits . Cuando se utiliza este enfoque, la función hash debe elegirse de modo que el resultado tenga una distribución bastante uniforme entre 0 y n − 1 , para cualquier valor de n que pueda ocurrir en la aplicación. Dependiendo de la función, el resto puede ser uniforme solo para ciertos valores de n , por ejemplo, números impares o primos .
Cuando se utiliza la función hash para almacenar valores en una tabla hash que sobrevive a la ejecución del programa, y es necesario ampliar o reducir la tabla hash, se la denomina tabla hash dinámica.
Es deseable una función hash que reubique la cantidad mínima de registros cuando se redimensiona la tabla. Lo que se necesita es una función hash H ( z , n ) (donde z es la clave que se va a codificar y n es la cantidad de valores hash permitidos) tal que H ( z , n + 1) = H ( z , n ) con una probabilidad cercana a n /( n + 1) .
El hash lineal y el hash espiral son ejemplos de funciones hash dinámicas que se ejecutan en tiempo constante pero que relajan la propiedad de uniformidad para lograr la propiedad de movimiento mínimo. El hash extensible utiliza una función hash dinámica que requiere un espacio proporcional a n para calcular la función hash, y se convierte en una función de las claves anteriores que se han insertado. Se han inventado varios algoritmos que conservan la propiedad de uniformidad pero requieren un tiempo proporcional a n para calcular el valor de H ( z , n ) . [ aclaración necesaria ]
Una función hash con un movimiento mínimo es especialmente útil en tablas hash distribuidas .
En algunas aplicaciones, los datos de entrada pueden contener características que no son relevantes para fines de comparación. Por ejemplo, al buscar un nombre personal, puede ser conveniente ignorar la distinción entre letras mayúsculas y minúsculas. Para tales datos, se debe utilizar una función hash que sea compatible con el criterio de equivalencia de datos que se esté utilizando: es decir, dos entradas cualesquiera que se consideren equivalentes deben producir el mismo valor hash. Esto se puede lograr normalizando la entrada antes de aplicarle el hash, por ejemplo, convirtiendo todas las letras en mayúsculas.
Existen varios algoritmos comunes para realizar el hash de números enteros. El método que ofrece la mejor distribución depende de los datos. Uno de los métodos más simples y comunes en la práctica es el método de división de módulo.
Si los datos que se van a convertir en hash son lo suficientemente pequeños, se pueden utilizar los datos en sí (reinterpretados como un entero) como valor hash. El coste de calcular esta función hash de identidad es prácticamente cero. Esta función hash es perfecta , ya que asigna cada entrada a un valor hash distinto.
El significado de "suficientemente pequeño" depende del tamaño del tipo que se utiliza como valor hash. Por ejemplo, en Java , el código hash es un entero de 32 bits. Por lo tanto, los objetos enteros de 32 bits Integery de punto flotante de 32 bits Floatpueden simplemente usar el valor directamente, mientras que los objetos enteros de 64 bits Longy de punto flotante de 64 bits Doubleno pueden hacerlo.
Otros tipos de datos también pueden utilizar este esquema de hash. Por ejemplo, al asignar cadenas de caracteres entre mayúsculas y minúsculas , se puede utilizar la codificación binaria de cada carácter, interpretada como un entero, para indexar una tabla que proporcione la forma alternativa de ese carácter ("A" para "a", "8" para "8", etc.). Si cada carácter se almacena en 8 bits (como en ASCII extendido [Notas 2] o ISO Latin 1 ), la tabla tiene solo 2 8 = 256 entradas; en el caso de caracteres Unicode , la tabla tendría 17 × 2 16 =1 114 112 entradas.
La misma técnica se puede utilizar para asignar códigos de país de dos letras como "us" o "za" a nombres de países (26 2 = 676 entradas de tabla), códigos postales de 5 dígitos como 13083 a nombres de ciudades (100 000 entradas), etc. Los valores de datos no válidos (como el código de país "xx" o el código postal 00000) pueden dejarse sin definir en la tabla o asignarse a algún valor "nulo" apropiado.
Si las claves están distribuidas de manera uniforme o suficientemente uniforme en el espacio de claves, de modo que los valores de las claves son esencialmente aleatorios, entonces se puede considerar que ya están "codificadas". En este caso, se puede extraer cualquier cantidad de bits de la clave y cotejarlos como un índice en la tabla hash. Por ejemplo, una función hash simple podría enmascarar los m bits menos significativos y usar el resultado como un índice en una tabla hash de tamaño 2 m .
Un código hash plegable se produce dividiendo la entrada en secciones de m bits, donde 2 m es el tamaño de la tabla, y utilizando una operación bit a bit que preserve la paridad, como ADD o XOR, para combinar las secciones, seguida de una máscara o desplazamientos para recortar los bits sobrantes en el extremo superior o inferior. Por ejemplo, para un tamaño de tabla de 15 bits y un valor de clave de 64 bits de 0x0123456789ABCDEF, hay cinco secciones que constan de 0x4DEF, 0x1357, 0x159E, 0x091A y 0x0. Al sumar, se obtiene 0x7FFE, un valor de 15 bits.
Un código hash de cuadrados medios se produce elevando al cuadrado la entrada y extrayendo una cantidad adecuada de dígitos o bits medios. Por ejemplo, si la entrada es123 456 789 y el tamaño de la tabla hash10 000 , luego elevando al cuadrado la clave se obtiene15 241 578 750 190 521 , por lo que el código hash se toma como los 4 dígitos centrales del número de 17 dígitos (ignorando el dígito alto) 8750. El método de cuadrados medios produce un código hash razonable si no hay muchos ceros iniciales o finales en la clave. Esta es una variante del hash multiplicativo, pero no es tan buena porque una clave arbitraria no es un buen multiplicador.
Una técnica estándar es usar una función módulo en la clave, seleccionando un divisor M que sea un número primo cercano al tamaño de la tabla, de modo que h ( K ) ≡ K (mod M ) . El tamaño de la tabla suele ser una potencia de 2. Esto da una distribución de {0, M − 1} . Esto da buenos resultados en una gran cantidad de conjuntos de claves. Una desventaja significativa del hashing de división es que la división está microprogramada en la mayoría de las arquitecturas modernas (incluida la x86 ) y puede ser 10 veces más lenta que la multiplicación. Una segunda desventaja es que no descompondrá las claves agrupadas. Por ejemplo, las claves 123000, 456000, 789000, etc. módulo 1000 se asignan todas a la misma dirección. Esta técnica funciona bien en la práctica porque muchos conjuntos de claves ya son suficientemente aleatorios y la probabilidad de que un conjunto de claves sea cíclico por un número primo grande es pequeña.
La codificación algebraica es una variante del método de división del hash que utiliza la división por un polinomio módulo 2 en lugar de un entero para mapear n bits a m bits. [3] : 512–513 En este enfoque, M = 2 m , y postulamos un polinomio de grado m Z ( x ) = x m + ζ m −1 x m −1 + ⋯ + ζ 0 . Una clave K = ( k n −1 … k 1 k 0 ) 2 puede considerarse como el polinomio K ( x ) = k n −1 x n −1 + ⋯ + k 1 x + k 0 . El resto usando aritmética polinómica módulo 2 es K ( x ) mod Z ( x ) = h m −1 x m −1 + ⋯ h 1 x + h 0 . Entonces h ( K ) = ( h m −1 … h 1 h 0 ) 2 . Si Z ( x ) se construye para tener t o menos coeficientes distintos de cero, entonces se garantiza que las claves que comparten menos de t bits no colisionarán.
Z es una función de k , t y n (la última de las cuales es divisor de 2 k − 1 ) y se construye a partir del cuerpo finito GF(2 k ) . Knuth da un ejemplo: tomando ( n , m , t ) = ( 15,10,7) se obtiene Z ( x ) = x10 + x8 + x5 + x4 + x2 + x + 1. La derivación es la siguiente :
Sea S el conjunto más pequeño de números enteros tales que {1,2,…, t } ⊆ S y (2 j mod n ) ∈ S ∀ j ∈ S . [Notas 3]
Definamos donde α ∈ n GF(2 k ) y donde se calculan los coeficientes de P ( x ) en este cuerpo. Entonces el grado de P ( x ) = | S | . Como α 2 j es una raíz de P ( x ) siempre que α j sea una raíz, se deduce que los coeficientes p i de P ( x ) satisfacen p2
yo= p i , por lo que todos son 0 o 1. Si R ( x ) = r n −1 x n −1 + ⋯ + r 1 x + r 0 es cualquier polinomio distinto de cero módulo 2 con como máximo t coeficientes distintos de cero, entonces R ( x ) no es un múltiplo de P ( x ) módulo 2. [Notas 4] De ello se deduce que la función hash correspondiente asignará claves con menos de t bits en común a índices únicos. [3] : 542–543
El resultado habitual es que n sea grande, o t sea grande, o ambos, para que el esquema sea computacionalmente factible. Por lo tanto, es más adecuado para la implementación en hardware o microcódigo. [3] : 542–543
El hash de permutación única tiene un tiempo de inserción garantizado en el mejor caso posible. [11]
El hash multiplicativo estándar utiliza la fórmula h a ( K ) = ⌊ ( aK mod W ) / ( W / M ) ⌋ , que produce un valor hash en {0, …, M − 1} . El valor a es un valor elegido apropiadamente que debería ser primo relativo a W ; debería ser grande, [ aclaración necesaria ] y su representación binaria una mezcla aleatoria [ aclaración necesaria ] de 1s y 0s. Un caso especial práctico importante ocurre cuando W = 2 w y M = 2 m son potencias de 2 y w es el tamaño de la palabra de máquina . En este caso, esta fórmula se convierte en h a ( K ) = ⌊ ( aK mod 2 w ) / 2 w − m ⌋ . Esto es especial porque la aritmética módulo 2 w se realiza por defecto en lenguajes de programación de bajo nivel y la división entera por una potencia de 2 es simplemente un desplazamiento a la derecha, por lo que, en C , por ejemplo, esta función se convierte en
hash sin signo (K sin signo) { devuelve (a*K) >> (wm);}y para m y w fijos esto se traduce en una única multiplicación de enteros y desplazamiento a la derecha, lo que la convierte en una de las funciones hash más rápidas de calcular.
El hash multiplicativo es susceptible a un "error común" que conduce a una difusión deficiente: los bits de entrada de mayor valor no afectan a los bits de salida de menor valor. [12] Una transmutación en la entrada que desplaza hacia abajo el intervalo de bits superiores retenidos y los combina o suma a la clave antes del paso de multiplicación corrige esto. La función resultante se ve así: [7]
hash sin signo (K sin signo) { K ^= K >> (wm); devuelve (a*K) >> (wm);}El hash de Fibonacci es una forma de hash multiplicativo en el que el multiplicador es 2 w / ϕ , donde w es la longitud de la palabra de la máquina y ϕ (phi) es la proporción áurea (aproximadamente 1,618). Una propiedad de este multiplicador es que distribuye uniformemente sobre el espacio de tablas bloques de claves consecutivas con respecto a cualquier bloque de bits en la clave. Las claves consecutivas dentro de los bits altos o bajos de la clave (o algún otro campo) son relativamente comunes. Los multiplicadores para varias longitudes de palabra son:
El multiplicador debe ser impar, de modo que el bit menos significativo de la salida sea invertible módulo 2 w . Los dos últimos valores dados anteriormente se redondean (hacia arriba y hacia abajo, respectivamente) por más de la mitad del bit menos significativo para lograr esto.
El algoritmo de hash de tabulación, más conocido como algoritmo de hash Zobrist en honor a Albert Zobrist , es un método para construir familias universales de funciones hash mediante la combinación de búsquedas en tablas con operaciones XOR. Este algoritmo ha demostrado ser muy rápido y de alta calidad para fines de hash (especialmente el algoritmo de hash de claves de números enteros). [13]
El algoritmo de hashing Zobrist se introdujo originalmente como un medio para representar de forma compacta las posiciones de ajedrez en los programas de juegos de ordenador. Se asignaba un número aleatorio único para representar cada tipo de pieza (seis para las negras y seis para las blancas) en cada espacio del tablero. De este modo, al comienzo del programa se inicializa una tabla de 64×12 números de este tipo. Los números aleatorios podían tener cualquier longitud, pero 64 bits era natural debido a las 64 casillas del tablero. Se transcribía una posición recorriendo las piezas de una posición, indexando los números aleatorios correspondientes (los espacios vacíos no se incluían en el cálculo) y uniéndolos mediante la operación XOR (el valor inicial podía ser 0 (el valor de identidad para la operación XOR) o una semilla aleatoria). El valor resultante se reducía mediante módulo, plegado o alguna otra operación para producir un índice de tabla hash. El algoritmo hash Zobrist original se almacenaba en la tabla como representación de la posición.
Más tarde, el método se extendió al hash de números enteros al representar cada byte en cada una de las 4 posiciones posibles en la palabra por un número aleatorio único de 32 bits. De este modo, se construye una tabla de 2 8 × 4 números aleatorios. Un entero hash de 32 bits se transcribe indexando sucesivamente la tabla con el valor de cada byte del entero de texto simple y uniendo los valores cargados mediante la operación XOR (de nuevo, el valor inicial puede ser el valor de identidad o una semilla aleatoria). La extensión natural a los números enteros de 64 bits es mediante el uso de una tabla de 2 8 × 8 números aleatorios de 64 bits.
Este tipo de función tiene algunas propiedades teóricas interesantes, una de las cuales se llama independencia de 3-tuplas , lo que significa que cada 3-tupla de claves tiene la misma probabilidad de asignarse a cualquier 3-tupla de valores hash.
Se puede diseñar una función hash para aprovechar la entropía existente en las claves. Si las claves tienen ceros iniciales o finales, o campos particulares que no se utilizan, siempre cero o alguna otra constante, o que generalmente varían poco, entonces enmascarar solo los bits volátiles y aplicarles el hash proporcionará una función hash mejor y posiblemente más rápida. Los divisores o multiplicadores seleccionados en los esquemas de división y multiplicación pueden generar funciones hash más uniformes si las claves son cíclicas o tienen otras redundancias.
Cuando los valores de los datos son cadenas de caracteres largas (o de longitud variable) —como nombres personales, direcciones de páginas web o mensajes de correo— su distribución suele ser muy desigual, con dependencias complicadas. Por ejemplo, el texto en cualquier lenguaje natural tiene distribuciones altamente no uniformes de caracteres y pares de caracteres , características del lenguaje. Para tales datos, es prudente utilizar una función hash que dependa de todos los caracteres de la cadena y de cada carácter de una manera diferente. [ aclaración necesaria ]
Las funciones hash simplistas pueden sumar los primeros y los últimos n caracteres de una cadena junto con la longitud, o formar un hash del tamaño de una palabra a partir de los 4 caracteres centrales de una cadena. Esto ahorra la iteración sobre la cadena (potencialmente larga), pero las funciones hash que no realizan un hash sobre todos los caracteres de una cadena pueden volverse lineales fácilmente debido a redundancias, agrupamiento u otras patologías en el conjunto de claves. Tales estrategias pueden ser efectivas como una función hash personalizada si la estructura de las claves es tal que el medio, los extremos u otros campos son cero o alguna otra constante invariante que no diferencia las claves; entonces las partes invariantes de las claves pueden ignorarse.
El ejemplo paradigmático de plegado por caracteres es sumar los valores enteros de todos los caracteres de la cadena. Una mejor idea es multiplicar el total del hash por una constante, normalmente un número primo considerable, antes de añadir el siguiente carácter, ignorando el desbordamiento. El uso de la operación exclusiva-o en lugar de la suma también es una alternativa plausible. La operación final sería un módulo, máscara u otra función para reducir el valor de la palabra a un índice del tamaño de la tabla. La debilidad de este procedimiento es que la información puede agruparse en los bits superiores o inferiores de los bytes; esta agrupación permanecerá en el resultado del hash y provocará más colisiones que un hash aleatorio adecuado. Los códigos de bytes ASCII, por ejemplo, tienen un bit superior de 0, y las cadenas imprimibles no utilizan los primeros 32 códigos de bytes, por lo que la información (95 códigos de bytes) se agrupa en los bits restantes de una manera no obvia.
El enfoque clásico, denominado hash PJW basado en el trabajo de Peter J. Weinberger en Bell Labs en la década de 1970, fue diseñado originalmente para convertir identificadores en tablas de símbolos del compilador como se indica en el "Libro del Dragón" . [14] Esta función hash desplaza los bytes 4 bits antes de sumarlos. Cuando la cantidad se completa, los 4 bits superiores se desplazan hacia afuera y, si no son cero, se vuelven a aplicar XOR al byte inferior de la cantidad acumulada. El resultado es un código hash del tamaño de una palabra al que se puede aplicar un módulo u otra operación de reducción para producir el índice hash final.
Hoy en día, especialmente con la llegada de tamaños de palabra de 64 bits, está disponible un hash de cadenas de longitud variable mucho más eficiente mediante fragmentos de palabras.
Los microprocesadores modernos permiten un procesamiento mucho más rápido si las cadenas de caracteres de 8 bits no se procesan procesando un carácter a la vez, sino interpretando la cadena como una matriz de números enteros de 32 o 64 bits y generando un hash/acumulando estos valores enteros de "palabra ancha" mediante operaciones aritméticas (por ejemplo, multiplicación por constante y desplazamiento de bits). La palabra final, que puede tener posiciones de bytes desocupadas, se llena con ceros o un valor aleatorio especificado antes de incorporarse al hash. El código hash acumulado se reduce mediante un módulo final u otra operación para generar un índice en la tabla.
De manera análoga a la forma en que una cadena de caracteres ASCII o EBCDIC que representa un número decimal se convierte en una cantidad numérica para su cálculo, una cadena de longitud variable se puede convertir como x k −1 a k −1 + x k −2 a k −2 + ⋯ + x 1 a + x 0 . Esto es simplemente un polinomio en una base a > 1 que toma los componentes ( x 0 , x 1 ,..., x k −1 ) como los caracteres de la cadena de entrada de longitud k . Se puede utilizar directamente como el código hash, o una función hash aplicada a él para mapear el valor potencialmente grande al tamaño de la tabla hash. El valor de a es usualmente un número primo lo suficientemente grande como para contener el número de caracteres diferentes en el conjunto de caracteres de claves potenciales. El hash de conversión de base de cadenas minimiza el número de colisiones. [15] Los tamaños de datos disponibles pueden restringir la longitud máxima de la cadena que se puede hash con este método. Por ejemplo, una palabra de 128 bits codificará únicamente una cadena alfabética de 26 caracteres (sin tener en cuenta mayúsculas y minúsculas) con una base de 29; una cadena ASCII imprimible está limitada a 9 caracteres utilizando una base de 97 y una palabra de 64 bits. Sin embargo, las claves alfabéticas suelen tener una longitud modesta, porque las claves deben almacenarse en la tabla hash. Las cadenas de caracteres numéricos no suelen ser un problema; 64 bits pueden contar hasta 10 19 , o 19 dígitos decimales con una base de 10.
En algunas aplicaciones, como la búsqueda de subcadenas , se puede calcular una función hash h para cada subcadena de k caracteres de una cadena dada de n caracteres haciendo avanzar una ventana de k caracteres de ancho a lo largo de la cadena, donde k es un entero fijo y n > k . La solución sencilla, que consiste en extraer dicha subcadena en cada posición de carácter del texto y calcular h por separado, requiere un número de operaciones proporcional a k · n . Sin embargo, con la elección adecuada de h , se puede utilizar la técnica de cálculo hash continuo para calcular todos esos hashes con un esfuerzo proporcional a mk + n , donde m es el número de ocurrencias de la subcadena. [16] [ ¿Cuál es la elección de h? ]
El algoritmo más conocido de este tipo es el de Rabin-Karp, con un rendimiento en el mejor y el promedio de los casos de O ( n + mk ) y en el peor de los casos de O ( n · k ) (para ser justos, el peor de los casos aquí es gravemente patológico: tanto la cadena de texto como la subcadena están compuestas por un único carácter repetido, como t ="AAAAAAAAAA", y s ="AAA"). La función hash utilizada para el algoritmo suele ser la huella digital de Rabin , diseñada para evitar colisiones en cadenas de caracteres de 8 bits, pero también se utilizan otras funciones hash adecuadas.
Los resultados del peor caso para una función hash se pueden evaluar de dos maneras: teórica y práctica. El peor caso teórico es la probabilidad de que todas las claves se asignen a una sola ranura. El peor caso práctico es la secuencia de sondeo más larga esperada (función hash + método de resolución de colisiones). Este análisis considera el hash uniforme, es decir, cualquier clave se asignará a cualquier ranura particular con una probabilidad de 1/ m , una característica de las funciones hash universales.
Mientras que Knuth se preocupa por los ataques adversarios a los sistemas en tiempo real, [24] Gonnet ha demostrado que la probabilidad de un caso así es "ridículamente pequeña". Su representación fue que la probabilidad de que k de n claves se asignen a una sola ranura es α k / ( e α k !) , donde α es el factor de carga, n / m . [25]
El término hash ofrece una analogía natural con su significado no técnico (cortar o hacer un desastre de algo), dada la forma en que las funciones hash mezclan sus datos de entrada para derivar su salida. [26] : 514 En su investigación sobre el origen preciso del término, Donald Knuth señala que, si bien Hans Peter Luhn de IBM parece haber sido el primero en usar el concepto de una función hash en una nota fechada en enero de 1953, el término en sí no apareció en la literatura publicada hasta fines de la década de 1960, en Digital Computer System Principles de Herbert Hellerman , aunque ya era una jerga generalizada para entonces. [26] : 547–548
La Infraestructura de Firmas Sin Clave (KSI) es un sistema distribuido globalmente para proporcionar servicios de sellado de tiempo y firma digital con soporte de servidor. Se crean árboles hash globales por segundo y se publican sus valores hash raíz. Analizamos algunos problemas de calidad del servicio que surgen en la implementación práctica del servicio y presentamos soluciones para evitar puntos únicos de falla y garantizar un servicio con un retraso razonable y estable. Guardtime AS ha estado operando una Infraestructura de KSI durante 5 años. Resumimos cómo se construye la Infraestructura de KSI y las lecciones aprendidas durante el período operativo del servicio.
es una biblioteca de software de código abierto publicada bajo la licencia GPLv3 que implementa varios algoritmos de hash perceptual y proporciona una API similar a C para usar esas funciones en sus propios programas. pHash en sí está escrito en C++.
