Función hash

Una función de hash que mapea nombres a enteros de 0 a 15. Hay una colisión entre las llaves "John Smith" y "Sandra Dee".

Una función hash es cualquier función que se puede usar para asignar datos de tamaño arbitrario a valores de tamaño fijo. Los valores devueltos por una función hash se denominan valores hash, códigos hash, resúmenes o simplemente hashes. Los valores generalmente se usan 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 hashing 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 mismos. Hashing es una forma de acceso a datos que utiliza el espacio de almacenamiento y la computación de manera eficiente 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 las propiedades estadísticas de la interacción entre clave y función: el comportamiento en el peor de los casos es intolerablemente malo con una probabilidad muy pequeña, y el comportamiento en el caso promedio puede ser casi óptimo (colisión mínima).

Las funciones hash están relacionadas (y a menudo se confunden) con sumas de control, 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 difiere de estos conceptos principalmente en términos de integridad de datos.

Resumen

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 ser de longitud fija, como un número entero, o de longitud variable, como un nombre. En algunos casos, la clave es el propio dato. La salida es un código hash que se usa 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:

• Convertir teclas de longitud variable en valores de longitud fija (normalmente longitud de la palabra de la máquina o menos), doblandolas por palabras u otras unidades utilizando un operador de conservación de paridad como ADD o XOR.
• Revuelva los bits de la clave para que los valores resultantes se distribuyan uniformemente sobre el espacio clave.
• Mapa de los valores clave en menos o igual al tamaño de la tabla

Una buena función hash satisface dos propiedades básicas: 1) debe ser muy rápida de calcular; 2) debe minimizar la duplicación de valores de salida (colisiones). Las funciones hash se basan en generar distribuciones de probabilidad favorables para su efectividad, lo que reduce el tiempo de acceso a casi constante. Los altos factores de carga de la tabla, los conjuntos de claves patológicos y las funciones hash mal diseñadas pueden dar como resultado que los tiempos de acceso se acerquen a la linealidad en la cantidad de elementos de la tabla. Las funciones hash se pueden diseñar para brindar el mejor rendimiento en el peor de los casos, 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), 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.

Tablas hash

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 a 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 un espacio vacío (también llamado depósito), en cuyo caso el elemento se agrega allí a la tabla. Si el código hash indexa un espacio completo, se requiere algún tipo de resolución de colisión: el elemento nuevo puede omitirse (no agregarse a la tabla) o reemplazar el elemento anterior, 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 hashing encadenado, cada ranura es el encabezado de una lista o cadena vinculada, y los elementos que chocan en la ranura se agregan a la cadena. Las cadenas pueden mantenerse en orden aleatorio y buscarse de forma lineal, en orden de serie o como una lista autoordenada por frecuencia para acelerar el acceso. En hashing de dirección abierta, la tabla se sondea a partir del espacio ocupado de una manera específica, generalmente mediante sondeo lineal, sondeo cuadrático o hash doble hasta que se encuentra un espacio abierto o se sondea toda la tabla (Desbordamiento). La búsqueda del artículo sigue el mismo procedimiento hasta que se encuentra el artículo, se encuentra un espacio libre o se ha buscado en toda la tabla (artículo que no está en la tabla).

Usos especializados

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 con hash, ya que cualquier colisión se puede resolver descartando o escribiendo de nuevo el más antiguo de los dos elementos en colisión.

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 hashing se conoce como hashing 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 (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 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 los 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, y así sucesivamente.

Las tablas hash también se utilizan para implementar matrices asociativas y conjuntos dinámicos.

Propiedades

Uniformidad

Una buena función hash debe 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 con aproximadamente la misma probabilidad. El motivo de este último requisito es que el costo de los métodos basados en hash aumenta considerablemente a medida que aumenta la cantidad de colisiones (pares de entradas que se asignan al mismo valor de hash). Si es más probable que ocurran algunos valores hash que otros, una fracción más grande de las operaciones de búsqueda tendrá que buscar a través de un conjunto más grande de entradas de tablas en conflicto.

Tenga en cuenta que 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 problemas de eficiencia computacional) generalmente una buena elecció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 las entradas válidas. Por ejemplo, la lista de miembros de un club puede contener solo un centenar de nombres de miembros, del gran conjunto de todos los nombres posibles. En estos casos, el criterio de uniformidad debe 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 convierte en n ranuras de tabla, la probabilidad de que un depósito reciba muchos más de m/n registros debe ser evanescentemente pequeño. En particular, si m es menor que n, muy pocos los cubos deben 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: vea 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 una función hash de este tipo es perfecta. No existe una forma algorítmica de construir una función de este tipo: buscar una es una función factorial de la cantidad de teclas que se asignarán frente a la cantidad de ranuras de la tabla en las que se aprovechan. 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 proporcione solo 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.

Pruebas y mediciones

Al probar una función de hash, la uniformidad de la distribución de los valores de hash puede ser evaluada por la prueba chi-squared. Esta prueba es una medida de bondad de beneficio: es la distribución real de artículos en cubos frente a la distribución esperada (o uniforme) de elementos. La fórmula es: ${displaystyle {frac {sum _{j=0}{m-1}(b_{j})(b_{j}+1)/2}{(n/2m)(n+2m-1)}}}$

Donde: ${displaystyle n}$ es el número de llaves, ${displaystyle m}$ es el número de cubos, ${displaystyle B_{j}$ es el número de elementos en cubo ${displaystyle j}$

Una relación dentro de un intervalo de confianza (0,95 - 1,05) indica 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 apliquen. Uno es el criterio estricto de avalancha: cada vez que se complementa un solo 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 pequeña cantidad de variabilidad, incluso un bit, debe traducirse en una gran cantidad de variabilidad (es decir, distribución en el espacio de tablas) 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 en torno a esos valores. Si los bits quieren cambiar demasiado rápido, el mapeo se aproxima a una función XOR fija de un solo bit. En la literatura se han descrito pruebas estándar para esta propiedad. Aquí se evalúa la relevancia del criterio para una función hash multiplicativa.

Eficiencia

En las aplicaciones de recuperación y almacenamiento 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, una lista lineal desordenada muy compacta sería el mejor medio; si el espacio de almacenamiento fuera ilimitado, una estructura de acceso aleatorio indexable por el valor-clave sería muy grande, muy escasa, pero muy rápida. Una función hash tarda una cantidad finita de tiempo en asignar un espacio de claves potencialmente grande a una cantidad factible de espacio de almacenamiento que se puede buscar en una cantidad de tiempo limitada, independientemente de la cantidad de claves. En la mayoría de las aplicaciones, la función hash debería 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 por 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 deben ser poco frecuentes y causar un retraso marginal, pero por lo demás son inofensivas, por lo general es preferible elegir una función hash más rápida que una que necesite más cómputo pero ahorre 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 un multiplicador 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 turnos-restas y turnos-adiciones, aunque minimizar el número de tales operaciones requeridas es un problema abrumador; 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 de multiplicación de hardware, 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 aun así no tiene que realizar ninguna operación de resto o división, ya que estos cálculos a veces son costosos. Por ejemplo, deje que n sea 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(tecla)/2^b. Podemos reemplazar la división por un desplazamiento de bit a la derecha (posiblemente más rápido): nP(key) >> b.

Si las claves se procesan repetidamente y la función de 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 los códigos hash coincidentes significan que las claves son idénticas. Esta técnica se utiliza para la tabla de transposición en los programas de juegos, que almacena una representación hash de 64 bits de la posición del tablero.

Universalidad

Un esquema hashing 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 cualquiera es 1/m, donde m es el número de valores hash distintos deseados, independientemente de las dos claves. El hashing universal asegura (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 un hash perfecto y puede requerir más operaciones que una función hash de propósito especial.

Aplicabilidad

Una función hash es aplicable en una variedad de situaciones. 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 hashing) no es tan útil como una que sí lo hace.

Determinista

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 a procesar, en el sentido matemático del término. Este requisito excluye las funciones hash que dependen de parámetros de variables externas, como 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 está fragmentando en los casos en que la dirección puede cambiar durante la ejecución (como puede suceder en los sistemas que usan ciertos métodos de recolección de elementos no utilizados), aunque a veces es posible volver a generar el algoritmo.

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 que se inicia el proceso de Python además de la entrada que se va a codificar. El hash de Python (SipHash) sigue siendo una función hash válida cuando se usa en 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 puede diferir.

Rango definido

A menudo es deseable que la salida de una función hash tenga un tamaño fijo (pero vea 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. Tal hashing se usa comúnmente para acelerar las búsquedas de datos. 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 tamaño específico. Las funciones hash utilizadas para búsquedas de datos utilizan alguna expresión aritmética que procesa de forma iterativa fragmentos de la entrada (como los caracteres de una cadena) para producir el valor hash.

Rango de variables

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 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 el número < i>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}), divida el resultado entre n y use el resto de la división. Si n es en sí mismo una potencia de 2, esto se puede hacer enmascarando y cambiando 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, p. números impares o primos.

Rango variable con movimiento mínimo (función hash dinámica)

Cuando la función hash se usa para almacenar valores en una tabla hash que sobrevive a la ejecución del programa, y la tabla hash necesita expandirse o reducirse, la tabla hash se denomina tabla hash dinámica.

Es deseable una función hash que reubique la cantidad mínima 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á codificando y n es la cantidad de hash permitido valores: tales que H(z,n + 1) = H (z,n) con probabilidad cercana a n/(n< /i> + 1).

El hash lineal y el almacenamiento 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 hashing 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. Varios algoritmos que conservan la propiedad de uniformidad pero requieren un tiempo proporcional a n para calcular el valor de H< /i>(z,n) han sido inventados.

Una función hash con un movimiento mínimo es especialmente útil en tablas hash distribuidas.

Normalización de datos

En algunas aplicaciones, los datos de entrada pueden contener características que son irrelevantes para propósitos 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 usar una función hash que sea compatible con el criterio de equivalencia de datos que se usa: es decir, dos entradas cualesquiera que se consideren equivalentes deben producir el mismo valor hash. Esto se puede lograr normalizando la entrada antes de convertirla en hash, como si todas las letras estuvieran en mayúsculas.

Hashing de tipos de datos enteros

Hay varios algoritmos comunes para cifrar enteros. El método que proporciona 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.

Función hash de identidad

Si los datos que se van a codificar son lo suficientemente pequeños, se pueden usar los datos mismos (reinterpretados como un número entero) como el valor cifrado. 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 "lo 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 Integer enteros de 32 bits y Float de coma flotante de 32 bits pueden simplemente usar el valor directamente; mientras que el entero de 64 bits Long y el Double de coma flotante de 64 bits no pueden usar este método.

Otros tipos de datos también pueden usar este esquema hash. Por ejemplo, al mapear cadenas de caracteres entre mayúsculas y minúsculas, se puede usar 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 o ISO Latin 1), la tabla tiene solo 2⁸ = 256 entradas; en el caso de los caracteres Unicode, la tabla tendría 17×2¹⁶ = 1< span style="margin-left:.25em;">114112 entradas.

Se puede usar la misma técnica para mapear códigos de países de dos letras como "nosotros" o "za" a nombres de países (26² = 676 entradas de tabla), códigos postales de 5 dígitos como 13083 a nombres de ciudades (100000 entradas), etc. Valores de datos no válidos (como el código de país "xx" o el código postal 00000) puede dejarse sin definir en la tabla o asignarse a algún código "null" valor.

Función hash trivial

Si las claves se distribuyen de manera uniforme o lo suficientemente uniforme en el espacio de claves, de modo que los valores de clave sean esencialmente aleatorios, se puede considerar que ya están 'hash'. En este caso, cualquier número de bits en la clave se puede marcar y cotejar como un índice en la tabla hash. Por ejemplo, una función hash simple podría enmascarar los bits m menos significativos y usar el resultado como un índice en una tabla hash de tamaño 2^m.

Plegado

Se produce un código hash plegable dividiendo la entrada en n secciones de m bits, donde 2^m es el tamaño de la tabla, y usando una operación bit a bit que conserva la paridad como ADD o XOR para combinar las secciones, seguido de una máscara o desplazamientos para eliminar cualquier exceso de bits en el extremo superior o inferior. Por ejemplo, para un tamaño de tabla de 15 bits y un valor de clave de 0x0123456789ABCDEF, hay cinco secciones que consisten en 0x4DEF, 0x1357, 0x159E, 0x091A y 0x8. Sumando, obtenemos 0x7AA4, un valor de 15 bits.

Cuadrados medios

Un código hash de cuadrados medios se produce elevando al cuadrado la entrada y extrayendo una cantidad adecuada de dígitos o bits intermedios. Por ejemplo, si la entrada es 123 456 789 y el tamaño de la tabla hash es 10 000, al elevar al cuadrado la clave se obtiene 15 241 578 750 190 521, por lo que el código hash se toma como los 4 dígitos del medio del número de 17 dígitos (ignorando el dígito alto) 8750. Los 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 tan buena porque una clave arbitraria no es un buen multiplicador.

Hashing de división

Una técnica estándar es utilizar una función de modulo en la clave, seleccionando un divisor ${displaystyle M}$ que es un número primo cerca del tamaño de la tabla, por lo que ${displaystyle h(K)=K{bmod {M}}$. El tamaño de la tabla es generalmente un poder de 2. Esto da una distribución ${displaystyle {0,M-1}$. Esto da buenos resultados sobre un gran número de conjuntos clave. Un importante inconveniente de la división es que la división está microprogramada en la mayoría de las arquitecturas modernas, incluyendo x86 y puede ser 10 veces más lento que multiplicarse. Un segundo inconveniente es que no romperá las llaves agrupadas. Por ejemplo, las teclas 123000, 456000, 789000, etc. modulo 1000 todo el mapa a la misma dirección. Esta técnica funciona bien en la práctica porque muchos conjuntos clave ya son suficientemente aleatorios, y la probabilidad de que un conjunto clave sea cíclico por un gran número primo es pequeña.

Codificación algebraica

Codificación algebraica es una variante del método de división de la piratería que utiliza la división por un modulo polinomio 2 en lugar de un entero a mapa n bits a m bits. En este enfoque, ${displaystyle M=2^{m}$ y postulamos un ${displaystyle m}$polinomio de grado ${displaystyle mathrm {Z} (x)=x^{m}+zeta ################################################################################################################################################################################################################################################################ ¿Qué?$. Una llave ${displaystyle K=(k_{n-1}...k_{1}k_{0}_{2}$ puede considerarse como el polinomio ${displaystyle K(x)=k_{n-1}x^{n-1}+k_{1}x+k_{0}$. El resto usando el modulo aritmético polinomio 2 es ${displaystyle K(x){bmod {Z}(x)=h_{m-1}x^{m-1}+h_{1}x+h_{0}$. Entonces... ${displaystyle h(K)=(h_{m-1}h_{1}h_{0}_{2}}$. Si ${displaystyle Z(x)}$ se construye para tener t o menos coeficientes no cero, entonces las claves que comparten menos de t bits están garantizados para no collide.

Z una función de k, t y n, un divisor de 2^k-1, se construye desde el GF(2^kCampo. Knuth da un ejemplo: para n=15, m=10 y t=7, ${displaystyle Z(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$. La derivación es la siguiente:

Vamos ${displaystyle S.$ ser el conjunto más pequeño de enteros tal que ${displaystyle {1,2,...,t}subseteq S}$ y ${displaystyle (2j{bmod {n})in Squadforall jin S}$.

Define ${displaystyle P(x)=prod _{jin S}(x-alpha ^{j}}$ Donde ${displaystyle alpha in ^{n}GF(2^{k}}$ y donde los coeficientes de ${displaystyle P(x)}$ están computados en este campo. Luego el grado de ${displaystyle P(x)=fortS habit}$. Desde ${displaystyle alpha ^{2j}$ es una raíz de ${displaystyle P(x)}$ siempre ${displaystyle alpha ^{j}$ es una raíz, sigue que los coeficientes ${displaystyle p^{i}$ de ${displaystyle P(x)}$ satisfacer satisfacción ${displaystyle ¿Qué?$ así que son todos 0 o 1. Si ${displaystyle R(x)=r_{(n-1)}x^{n-1}+r_{1}x+r_{0}$ es cualquier modulo polinomio no cero 2 con la mayoría de los coeficientes no cero, entonces ${displaystyle R(x)}$ no es un múltiple ${displaystyle P(x)}$ modulo 2. Si sigue que la función de hash correspondiente mapa las claves con menos de t bits en común a índices únicos.

El resultado habitual es que n será grande, twill será grande, o ambos, para que el esquema sea computacionalmente factible. Por lo tanto, es más adecuado para la implementación de hardware o microcódigo.

hash de permutación única

unsigned hash(unsigned K)
{}
retorno (a*K) " título " (w-m);
}

unsigned hash(unsigned K)
{}
K ^= K ≤ (w-m);
retorno (a*K) " título " (w-m);
}

Hashing de datos de longitud variable

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 idioma natural tiene distribuciones de caracteres y pares de caracteres muy no uniformes, característicos del idioma. Para tales datos, es prudente utilizar una función hash que dependa de todos los caracteres de la cadena y que dependa de cada carácter de forma diferente.

Medios y puntas

Las funciones hash simples pueden agregar el primero y el último n caracteres de una cadena junto con la longitud, o formar un hash del tamaño de una palabra a partir de la 4 caracteres del medio de una cadena. Esto ahorra iterar sobre la cadena (potencialmente larga), pero las funciones hash que no generan hash en todos los caracteres de una cadena pueden volverse lineales fácilmente debido a redundancias, agrupamientos 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 invariable que no diferencia las claves; entonces las partes invariantes de las claves pueden ignorarse.

Plegado de personajes

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 hash por una constante, generalmente un número primo considerable, antes de agregar el siguiente carácter, ignorando el desbordamiento. Uso exclusivo de 'o' 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, cuya agrupación permanecerá en el resultado del hash y causará más colisiones que un hash de aleatorización adecuado. Los códigos de bytes ASCII, por ejemplo, tienen un bit superior de 0 y las cadenas imprimibles no usan los primeros códigos de 32 bytes, por lo que la información (códigos de 95 bytes) se agrupa en los bits restantes de manera no obvia.

El enfoque clásico denominado hash PJW 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 "Dragon Book". Esta función hash compensa los bytes 4 bits antes de SUMARLOS. Cuando la cantidad termina, los 4 bits altos se desplazan hacia fuera y, si no son cero, se vuelven a aplicar XOR al byte bajo de la cantidad acumulada. El resultado es un código hash del tamaño de una palabra al que se le 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 los tamaños de palabra de 64 bits, está disponible un hashing de cadenas de longitud variable mucho más eficiente por fragmentos de palabras.

Plegado de longitud de palabra

Análisis

El resultado del peor de los casos para una función hash se puede evaluar de dos maneras: teórica y práctica. El peor de los casos teóricos es la probabilidad de que todas las claves se asignen a una única ranura. En el peor de los casos prácticos se espera la secuencia de sondeo más larga (función hash + método de resolución de colisiones). Este análisis considera hash uniforme, es decir, cualquier clave se asignará a cualquier ranura en particular con probabilidad 1/m, característica de las funciones hash universales.

Mientras que Knuth se preocupa por el ataque contra los sistemas de tiempo real, Gonnet ha demostrado que la probabilidad de tal caso es "rídicamente pequeña". Su representación era que la probabilidad de k de n asignación de claves a una sola ranura es ${displaystyle {frac {fnMicrosoft Sans Serif} ¡Alpha!$ Donde α es el factor de carga, n/m.

Historia

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. 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í solo aparecería en publicó literatura a fines de la década de 1960, en Principios de sistemas informáticos digitales de Herbert Hellerman, aunque ya era una jerga generalizada para entonces.