Una función hash es cualquier función que se puede utilizar para asignar datos de tamaño arbitrario a valores de tamaño fijo, aunque existen algunas funciones hash que admiten salidas 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 generalmente para indexar una tabla de tamaño fijo llamada tabla hash . El uso de una función hash para indexar una tabla hash se denomina direccionamiento de almacenamiento disperso o hash .
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 sólo una fracción mayor que el espacio total requerido para los datos o registros mismos. El hashing es una forma de acceso a datos eficiente desde el punto de vista computacional y de almacenamiento que evita el tiempo de acceso no constante de listas ordenadas y desordenadas y árboles estructurados, y los requisitos de almacenamiento, a menudo exponenciales, del acceso directo a espacios de estado de claves grandes o de longitud variable.
El uso de funciones hash se basa en propiedades estadísticas de la interacción entre claves y funciones: el comportamiento en el peor de los casos es intolerablemente malo pero raro, y el comportamiento en el caso promedio puede ser casi óptimo ( colisión mínima ). [3] : 527
Las funciones hash están relacionadas (y a menudo se confunden con) sumas de verificación , dígitos de verificación , 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 los datos .
Una función hash toma una clave como entrada, que se asocia con un dato o registro y se utiliza para identificarlo en 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 propio dato. El resultado es un código hash que se utiliza para indexar una tabla hash que contiene 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: 1) debería ser muy rápida de calcular; 2) debería minimizar la duplicación de valores de salida (colisiones). Las funciones hash dependen de generar distribuciones de probabilidad favorables para su efectividad, lo que reduce el tiempo de acceso a un nivel casi constante. Los altos factores de carga de la tabla, los conjuntos de claves patológicos y las funciones hash mal diseñadas pueden hacer que los tiempos de acceso se acerquen a la linealidad en el número de elementos de la tabla. Las funciones hash se pueden diseñar para ofrecer el mejor rendimiento en el peor de los casos, [Notas 1] un buen rendimiento con factores de carga de tabla elevados y, en casos especiales, una asignación perfecta (sin colisiones) de claves en códigos hash. La implementación se basa en operaciones de bits que preservan la paridad (XOR y ADD), multiplicar o dividir. Un complemento necesario de 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 un espacio vacío.
Las funciones hash se utilizan junto con 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 va a agregar un elemento a la tabla, el código hash puede indexar una ranura vacía (también llamada depósito), en cuyo caso el elemento se agrega a la tabla allí. Si el código hash indexa una ranura completa, 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 antiguo, o puede agregarse a la tabla en alguna otra ubicación mediante un procedimiento especificado. Ese procedimiento depende de la estructura de la tabla hash: en el hash encadenado , cada ranura es el encabezado de una lista o cadena enlazada, y los elementos que chocan en la ranura se agregan a la cadena. Las cadenas se pueden mantener en orden aleatorio y buscar linealmente, 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 localiza una ranura abierta o se sondea toda la tabla (desbordamiento). La búsqueda del elemento sigue el mismo procedimiento hasta que se localiza el elemento, se encuentra un espacio abierto 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 reescribiendo el más antiguo de los dos elementos en colisión. [4]
Las funciones hash son un ingrediente esencial del filtro Bloom , una estructura de datos probabilística eficiente en el espacio 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 suele ser una matriz con dos o más índices (llamada 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 por 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 asignar 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 debe generarse aproximadamente con la misma probabilidad . La razón de este último requisito es que el costo de los métodos basados en hash aumenta considerablemente a medida que aumenta el número de colisiones (pares de entradas que se asignan al mismo valor de hash). Si es más probable que se produzcan algunos valores hash que otros, una fracción mayor de las operaciones de búsqueda tendrá que buscar en un conjunto mayor de entradas de tablas en conflicto.
Este criterio solo requiere que el valor esté distribuido uniformemente , no aleatorio en ningún sentido. Una buena función de aleatorización es (salvo preocupaciones de eficiencia computacional) generalmente una buena opción como función hash, pero lo contrario no tiene por qué ser cierto.
Las tablas hash a menudo contienen solo un pequeño subconjunto de entradas válidas. Por ejemplo, la lista de miembros de un club puede contener sólo un centenar de nombres de miembros, del gran conjunto de todos los nombres posibles. En estos casos, el criterio de uniformidad debería ser válido para casi todos los subconjuntos típicos de entradas que puedan encontrarse en la tabla, no sólo para el conjunto global de todas las entradas posibles.
En otras palabras, si un conjunto típico de m registros se aplica mediante hash a n espacios de tabla, la probabilidad de que un depósito reciba muchos más que m / n registros debería ser extremadamente pequeña. En particular, si m es menor que n , muy pocos depósitos deberían tener más de uno o dos registros. Un pequeño número 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 logra una uniformidad absoluta (o sin colisiones). Se dice que esta función hash es perfecta . No existe una forma algorítmica de construir tal función: buscar una es una función factorial del número de claves que se asignarán versus la cantidad de espacios de la tabla a los que se accede. Encontrar una función hash perfecta en 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 desde el punto de vista computacional que una función hash estándar y proporciona sólo una ventaja marginal sobre una función con buenas propiedades estadísticas que produce un número mínimo de colisiones. Ver 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 elementos en depósitos versus la distribución esperada (o uniforme) de elementos. La fórmula es:
donde: es el número de claves, es el número de depósitos, es el número de elementos en el depósito
Una proporción dentro de un intervalo de confianza (0,95 - 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 más probable que tengan una distribución uniforme cuando se apliquen. Uno es el estricto criterio de avalancha : cada vez que se complementa un único bit de entrada, cada uno de los bits de salida cambia con una probabilidad del 50%. El motivo de esta propiedad es que los subconjuntos seleccionados del espacio de claves pueden tener una baja variabilidad. Para que la salida se distribuya uniformemente, una cantidad baja de variabilidad, incluso un bit, debe traducirse en una gran cantidad de variabilidad (es decir, distribución en el espacio de tabla) en la salida. Cada bit debería cambiar con una probabilidad del 50% porque si algunos bits son reacios a cambiar, las claves se agrupan alrededor de esos valores. Si los bits quieren cambiar con demasiada facilidad, el mapeo se acerca a una función XOR fija de un solo bit. En la literatura se han descrito pruebas estándar para esta propiedad. [6] Aquí se evalúa la relevancia del criterio para una función hash multiplicativa. [7]
En aplicaciones de almacenamiento y recuperación de datos, el uso de una función hash es una compensación entre el tiempo de búsqueda y el espacio de almacenamiento de datos. Si el tiempo de búsqueda fuera ilimitado, el mejor medio sería una lista lineal desordenada muy compacta; Si el espacio de almacenamiento fuera ilimitado, una estructura accesible aleatoriamente indexable por clave-valor sería muy grande, muy escasa, pero muy rápida. Una función hash necesita una cantidad de tiempo finita para asignar un espacio de claves potencialmente grande a una cantidad factible de espacio de almacenamiento que se pueda buscar en un período de tiempo limitado, independientemente de la cantidad de claves. En la mayoría de las aplicaciones, la función hash debe ser computable con una latencia mínima y, secundariamente, 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, siendo los más simples los métodos bit a bit (plegado), seguidos de los métodos multiplicativos, y los más complejos (más lentos) son los métodos basados en división.
Debido a que las colisiones deberían ser poco frecuentes y causar un retraso marginal pero, por lo demás, son inofensivas, generalmente es preferible elegir una función hash más rápida que una que necesita más cálculo pero evita algunas colisiones.
Las implementaciones basadas en divisiones pueden ser motivo de especial 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 la constante. Esto lo puede hacer el programador o el compilador. La división también se puede reducir directamente a una serie de restas y sumas por turnos, aunque minimizar el número de operaciones requeridas es un problema desalentador; el número de instrucciones de montaje resultantes puede ser más de una docena, e inundar la tubería. Si la arquitectura tiene unidades funcionales múltiples de hardware, la multiplicación por inversa probablemente sea 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 división o resto, 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 (clave) que es uniforme en el intervalo [0, 2 b − 1] . Una función hash uniforme en el intervalo [0, n -1] es n P (clave)/2 b . Podemos reemplazar la división por un desplazamiento de bit a la derecha (posiblemente más rápido) : nP (tecla) >> 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. Es casi seguro que hacer coincidir códigos hash 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 de 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 de hash distintos. deseado, independientemente de las dos teclas. 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 permite solo ciertos tamaños de tabla, cadenas solo hasta una cierta longitud o que no puede aceptar una semilla (es decir, permitir doble hash) no es tan útil como una que sí lo hace. [ cita necesaria ]
Una función hash es aplicable en una variedad de situaciones. Particularmente dentro de la criptografía, las aplicaciones notables incluyen: [8]
Un procedimiento hash debe ser determinista , lo que significa que para un valor de entrada determinado siempre debe generar el mismo valor hash. En otras palabras, debe ser una función de los datos que se van a aplicar hash, en el sentido matemático del término. Este requisito excluye las funciones hash que dependen de parámetros variables externos, como generadores de números pseudoaleatorios o la hora del día. También excluye funciones que dependen de la dirección de memoria del objeto que se está procesando en los casos en que la dirección pueda cambiar durante la ejecución (como puede suceder en sistemas que usan ciertos métodos de recolección de basura ), aunque a veces es posible repetir el elemento.
El determinismo está en el contexto de la reutilización de la función. Por ejemplo, Python agrega la característica de que las funciones hash utilizan una semilla aleatoria que se genera una vez cuando se inicia el proceso de Python, además de la entrada que se va a aplicar hash. [9] El hash de Python ( SipHash ) sigue siendo una función hash válida cuando se utiliza en una sola ejecución. Pero si los valores persisten (por ejemplo, se escriben en el disco), ya no pueden tratarse como valores hash válidos, ya que en la siguiente ejecución el valor aleatorio puede diferir.
A menudo es deseable que la salida de una función hash tenga un tamaño fijo (pero consulte a continuación). Si, por ejemplo, la salida está restringida a valores enteros de 32 bits, los valores hash se pueden usar para indexar en una matriz. Este tipo de hash se utiliza habitualmente para acelerar las búsquedas de datos. [10] Se puede producir una salida de longitud fija a partir de una entrada de longitud variable dividiendo los datos de entrada en fragmentos de tamaño específico. Las funciones hash utilizadas para búsquedas de datos utilizan alguna expresión aritmética que procesa iterativamente fragmentos de la entrada (como los caracteres de 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 a lo largo de la misma ejecución (por ejemplo, cuando es necesario expandir una tabla hash). En esas situaciones, se necesita una función hash que tome dos parámetros: los datos de entrada z y el número n de valores hash permitidos.
Una solución común es calcular una función hash fija con un rango muy grande (digamos, 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 manera 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 sólo para ciertos valores de n , por ejemplo, números primos o impares .
Cuando la función hash se utiliza para almacenar valores en una tabla hash que sobrevive a la ejecución del programa y es necesario expandir o reducir la tabla hash, la tabla hash se denomina tabla hash dinámica.
Es deseable una función hash que reubique el número mínimo de registros cuando se cambie el tamaño de la tabla. Lo que se necesita es una función hash H ( z , n ) , donde z es la clave que se está procesando y n es el número de valores hash permitidos, tal que H ( z , n + 1) = H ( z , n ) con probabilidad cerca de n /( n + 1) .
El hash lineal y el hash en espiral son ejemplos de funciones hash dinámicas que se ejecutan en tiempo constante pero 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 preservan la propiedad de uniformidad pero requieren un tiempo proporcional a n para calcular el valor de H ( z , n ) . [ se necesita aclaración ]
Una función hash con movimiento mínimo es especialmente útil en tablas hash distribuidas .
En algunas aplicaciones, los datos de entrada pueden contener características que son irrelevantes a efectos 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 utiliza: es decir, dos entradas cualesquiera que se consideren equivalentes deben producir el mismo valor hash. Esto se puede lograr normalizando la entrada antes de aplicar hash, como poner todas las letras en mayúsculas.
Existen varios algoritmos comunes para 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 aplicar hash son lo suficientemente pequeños, se pueden usar los datos mismos (reinterpretados como un número entero) como valor hash. El costo de calcular esta función hash de identidad es efectivamente 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 número 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 el entero de 64 bits Longy el punto flotante de 64 bits Doubleno pueden utilizar este método.
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 número entero, para indexar una tabla que proporcione la forma alternativa de ese carácter ("A" para "a", " 8" por "8", etc.). Si cada carácter se almacena en 8 bits (como en ASCII extendido [Notas 2] o ISO Latin 1 ), la tabla tiene sólo 2 8 = 256 entradas; en el caso de caracteres Unicode , la tabla tendría 17×2 16 =1.114.112 entradas . _
Se puede utilizar la misma técnica para asignar códigos de país de dos letras como "nosotros" 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 sean esencialmente aleatorios, se puede considerar que ya están "en hash". En este caso, se puede extraer cualquier número 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 índice en una tabla hash de tamaño 2 m .
Un código hash plegable se produce dividiendo la entrada en n secciones de m bits, donde 2 m es el tamaño de la tabla, y utilizando una operación bit a bit que preserva la paridad, como ADD o XOR, para combinar las secciones, seguida de una máscara o cambios a recorte cualquier exceso de bits en el extremo alto o bajo. Por ejemplo, para un tamaño de tabla de 15 bits y un valor clave de 0x0123456789ABCDEF, hay cinco secciones que constan de 0x4DEF, 0x1357, 0x159E, 0x091A y 0x8. Sumando obtenemos 0x7AA4, un valor de 15 bits.
Un código hash de cuadrados medios se produce elevando al cuadrado la entrada y extrayendo un número apropiado de dígitos o bits centrales. Por ejemplo, si la entrada es 123.456.789 y el tamaño de la tabla hash es 10.000, elevar al cuadrado la clave produce 15.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 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 tan buena porque una clave arbitraria no es un buen multiplicador.
Una técnica estándar es utilizar una función de módulo en la clave, seleccionando un divisor que sea un número primo cercano al tamaño de la tabla, por lo que . El tamaño de la tabla suele ser una potencia de 2. Esto da una distribución de . Esto da buenos resultados en una gran cantidad de conjuntos de claves. Un inconveniente importante del hash de división es que la división está microprogramada en la mayoría de las arquitecturas modernas, incluida x86, y puede ser 10 veces más lenta que la multiplicación. Un segundo inconveniente es que no dividirá 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 de hash que utiliza la división por un polinomio módulo 2 en lugar de un número entero para asignar n bits a m bits. [3] : 512–513 En este enfoque, postulamos un polinomio de ésimo grado . Una clave puede considerarse como el polinomio . El resto usando aritmética polinomial módulo 2 es . Entonces . Si está construido para tener o menos coeficientes distintos de cero, entonces se garantiza que las claves que comparten menos de bits no colisionarán.
una función de , y , un divisor de , se construye a partir del campo. Knuth da un ejemplo: para n=15, m=10 y t=7, . La derivación es la siguiente:
Sea el conjunto más pequeño de números enteros tal que y . [Notas 3]
Defina dónde y dónde se calculan los coeficientes de en este campo. Entonces el grado de . Dado que es una raíz de siempre es una raíz, se deduce que los coeficientes de satisfacen , por lo que todos son 0 o 1. Si hay cualquier polinomio módulo 2 distinto de cero con como máximo coeficientes distintos de cero, entonces no es un múltiplo de módulo 2. [Notas 4 ] De ello se deduce que la función hash correspondiente asignará claves con menos de bits en común a índices únicos. [3] : 542–543
El resultado habitual es que cualquiera de los dos se hará grande, o se hará grande, o ambas cosas, para que el esquema sea computacionalmente factible. Por lo tanto, es más adecuado para la implementación de hardware o microcódigo. [3] : 542–543
Véase también hash de permutación único, que tiene garantizado un mejor tiempo de inserción en el peor de los casos. [11]
El hash multiplicativo estándar utiliza la fórmula que produce un valor hash en . El valor es un valor elegido apropiadamente que debe ser primo relativo a ; debe ser grande [ se necesita aclaración ] y su representación binaria una mezcla aleatoria [ se necesita aclaración ] de unos y ceros. Un caso especial práctico importante ocurre cuando y son potencias de 2 y es el tamaño de la palabra de la máquina . En este caso esta fórmula se convierte en . Esto es especial porque el módulo aritmético se realiza de forma predeterminada en los lenguajes de programación de bajo nivel y la división de enteros 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 firmar (K sin firmar){ retorno (a*K) >> (wm);}y para fijo y esto se traduce en una multiplicación de un solo número entero 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 mala difusión: 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 los bits superiores retenidos y los XOR o AGREGA a la clave antes de que el paso de multiplicación corrija esto. Entonces la función resultante se ve así: [7]
hash sin firmar (K sin firmar){ K ^= K >> (wm); retorno (a*K) >> (wm);}El hash de Fibonacci es una forma de hash multiplicativo en el que el multiplicador es , donde es la longitud de la palabra de la máquina y (phi) es la proporción áurea (aproximadamente 5/3). Una propiedad de este multiplicador es que distribuye uniformemente sobre el espacio de tabla bloques de claves consecutivas con respecto a cualquier bloque de bits de 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 palabras son:
El multiplicador debe ser impar, por lo que el bit menos significativo de la salida es módulo invertible . Los dos últimos valores indicados anteriormente se redondean (hacia arriba y hacia abajo, respectivamente) en más de la mitad del bit menos significativo para lograrlo.
El hash de tabulación, más generalmente conocido como hash Zobrist en honor a Albert Zobrist , un científico informático estadounidense, es un método para construir familias universales de funciones hash combinando la búsqueda de tablas con operaciones XOR. Este algoritmo ha demostrado ser muy rápido y de alta calidad para fines de hash (especialmente hash de claves de números enteros). [13]
El hash Zobrist se introdujo originalmente como un medio para representar de forma compacta las posiciones de ajedrez en programas de juegos de computadora. Se asignó un número aleatorio único para representar cada tipo de pieza (seis para blanco y negro) en cada espacio del tablero. Por lo tanto, al inicio del programa se inicializa una tabla de 64×12 de dichos números. Los números aleatorios podían tener cualquier longitud, pero 64 bits eran naturales debido a los 64 cuadrados del tablero. Una posición se transcribía recorriendo las piezas de una posición, indexando los números aleatorios correspondientes (los espacios vacíos no se incluyeron en el cálculo) y aplicando XOR juntos (el valor inicial podría ser 0, el valor de identidad para XOR o un valor aleatorio). semilla). El valor resultante se redujo mediante módulo, plegado o alguna otra operación para producir un índice de tabla hash. El hash Zobrist original se almacenó en la tabla como representación de la posición.
Más tarde, el método se amplió al hash de números enteros representando cada byte en cada una de las 4 posiciones posibles de la palabra mediante un número aleatorio único de 32 bits. Por tanto, se construye una tabla de 2 8 ×4 de dichos números aleatorios. Un entero con hash de 32 bits se transcribe indexando sucesivamente la tabla con el valor de cada byte del entero de texto sin formato y aplicando XOR los valores cargados juntos (nuevamente, 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 números aleatorios de 8 × 8 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 es igualmente probable que cada 3 tupla de claves se asigne a cualquier 3 tupla de valores hash.
Se puede diseñar una función hash para explotar 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 generalmente varían poco, entonces enmascarar solo los bits volátiles y aplicar hash a ellos 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 de caracteres y pares de caracteres muy no uniformes , característicos del idioma. Para dichos datos, es prudente utilizar una función hash que dependa de todos los caracteres de la cadena y dependa de cada carácter de forma diferente. [ se necesita aclaración ]
Las funciones hash simplistas pueden agregar los primeros y ú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 iterar sobre la cadena (potencialmente larga), pero las funciones hash que no hacen hash en todos los caracteres de una cadena pueden volverse lineales fácilmente debido a redundancias, agrupaciones u otras patologías en el conjunto de claves. Dichas estrategias pueden ser efectivas como una función hash personalizada si la estructura de las claves es tal que los campos intermedios, finales u otros son cero o alguna otra constante invariante que no diferencia las claves; entonces se pueden ignorar las partes invariantes de las claves.
El ejemplo paradigmático de plegar 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, generalmente un número primo considerable, antes de agregar el siguiente carácter, ignorando el desbordamiento. Usar 'o' exclusivo en lugar de agregar 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, agrupación que permanecerá en el resultado hash y causará 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 (códigos de 95 bytes) se agrupa en los bits restantes de una manera no obvia.
El enfoque clásico denominado PJW hash basado en el trabajo de Peter. J. Weinberger en ATT Bell Labs en la década de 1970, fue diseñado originalmente para codificar identificadores en tablas de símbolos del compilador como se indica en el "Libro del Dragón" . [14] Esta función hash compensa los bytes 4 bits antes de AGREGARLOS. Cuando la cantidad se ajusta, los 4 bits superiores se desplazan hacia afuera y, si no son cero, se vuelven a realizar XOR en el 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 reductora para producir el índice hash final.
Hoy en día, especialmente con la llegada de tamaños de palabras de 64 bits, está disponible un hash de cadenas de longitud variable por fragmentos de palabras mucho más eficiente.
Los microprocesadores modernos permitirán un procesamiento mucho más rápido si las cadenas de caracteres de 8 bits no se procesan mediante hash procesando un carácter a la vez, sino interpretando la cadena como una matriz de enteros de 32 o 64 bits y aplicando hash/acumulación de estas "palabras anchas". valores enteros mediante operaciones aritméticas (p. ej. multiplicación por constante y desplazamiento de bits). La última palabra, que puede tener posiciones de bytes desocupadas, se completa con ceros o un valor "aleatorizado" específico 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 calcular, una cadena de longitud variable se puede convertir como ( x 0 a k −1 + x 1 a k −2 +...+ x k −2 a + x k −1 ) . 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 código hash o se le puede aplicar una función hash para asignar el valor potencialmente grande al tamaño de la tabla hash. El valor de a suele ser un número primo al menos 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 Radix 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 aplicar hash con este método. Por ejemplo, una palabra de doble longitud de 128 bits procesará solo una cadena alfabética de 26 caracteres (ignorando mayúsculas y minúsculas) con una base de 29; una cadena ASCII imprimible está limitada a 9 caracteres utilizando base 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 base 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 de n caracteres determinada avanzando una ventana de k caracteres de ancho a lo largo de la cadena; donde k es un número entero fijo y n es mayor que k . La solución sencilla, que consiste en extraer dicha subcadena en cada posición de carácter en el texto y calcular h por separado, requiere una cantidad de operaciones proporcional a k · n . Sin embargo, con la elección adecuada de h , se puede utilizar la técnica de rodar hash para calcular todos esos hashes con un esfuerzo proporcional a mk + n donde m es el número de apariciones de la subcadena. [ cita necesaria ] [ ¿ cuál es la elección de h? ]
El algoritmo más familiar de este tipo es Rabin-Karp con el mejor y promedio rendimiento de caso O ( n + mk ) y el peor caso O ( n · k ) (para ser justos, el peor caso aquí es gravemente patológico: tanto la cadena de texto como La subcadena se compone de un solo carácter repetido, como t ="AAAAAAAAAAA" 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.
El peor resultado de una función hash se puede 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. En el peor de los casos prácticos se espera la secuencia de sonda más larga (función hash + método de resolución de colisiones). Este análisis considera un hash uniforme, es decir, cualquier clave se asignará a cualquier ranura particular con una probabilidad de 1/ m , característica de las funciones hash universales.
Mientras que a Knuth le preocupa el ataque adversario a sistemas en tiempo real, [23] Gonnet ha demostrado que la probabilidad de que se produzca tal caso 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 donde α es el factor de carga, n / m . [24]
El término hash ofrece una analogía natural con su significado no técnico (cortar o ensuciar algo), dada la forma en que las funciones hash codifican sus datos de entrada para derivar su salida. [25] : 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 utilizar el concepto de función hash en un memorando de enero de 1953, el término En sí mismo sólo aparecería en la literatura publicada a finales de la década de 1960, en Principios del sistema informático digital de Herbert Hellerman , aunque para entonces ya era una jerga muy extendida. [25] : 547–548
Keyless Signatures Infrastructure (KSI) es un sistema distribuido globalmente para proporcionar servicios de firma digital respaldados por servidor y sellado de tiempo. Se crean árboles hash globales por segundo y se publican sus valores hash raíz. Discutimos 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 demoras razonables y estables. Guardtime AS opera una infraestructura KSI desde hace 5 años. Resumimos cómo se construye la infraestructura KSI y las lecciones aprendidas durante el período operativo del servicio.
pHash es una biblioteca de software de código abierto publicada bajo la licencia GPLv3 que implementa varios algoritmos de hash de percepción y proporciona una API similar a C para usar esas funciones en sus propios programas.
El propio pHash está escrito en C++.
