Función hash

Las funciones hash también se utilizan para crear cachés para grandes conjuntos de datos almacenados en medios lentos. Una caché suele ser más sencilla que una tabla de búsqueda hash, ya que cualquier colisión se puede resolver descartando o reescribiendo el elemento más antiguo de los dos elementos que colisionan. ^{[ 4 ]}

Las funciones hash son un ingrediente esencial del filtro de Bloom , una estructura de datos probabilística que utiliza espacio de forma eficiente y que se emplea para comprobar si un elemento pertenece a 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 de hashing puede interpretarse 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 cubetas , etc.), y la función de hashing devuelve una tupla de índice . Este principio se utiliza 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 arreglos asociativos y conjuntos dinámicos . ^{[ 5 ]}

Una buena función hash debe distribuir las entradas esperadas de la forma más uniforme posible en su rango de salida. Es decir, cada valor hash en el rango de salida debe generarse con una probabilidad aproximadamente igual . El motivo de este requisito es que el coste de los métodos basados ​​en hash aumenta considerablemente a medida que se incrementa el número de colisiones (pares de entradas que se asignan al mismo valor hash). Si algunos valores hash tienen mayor probabilidad de ocurrir que otros, una mayor proporción de las operaciones de búsqueda tendrá que examinar un conjunto mayor de entradas de la tabla que colisionan.

Este criterio solo requiere que el valor tenga una distribución uniforme , no que sea aleatorio en ningún sentido. Una buena función de aleatorización suele ser una buena opción como función hash (salvo problemas de eficiencia computacional), pero lo contrario no tiene por qué ser 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 un centenar de nombres, de un conjunto muy grande 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 puedan 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 asigna mediante hash a n ranuras de tabla, la probabilidad de que un cubo reciba muchos más de m / n registros debería ser prácticamente nula. En particular, si m < n , muy pocos cubos 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 (véase 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). Dicha función hash se denomina perfecta . No existe un método algorítmico para construir tal función; su búsqueda es una función factorial del número de claves a mapear frente al número de ranuras de la tabla en las que se mapean. Encontrar una función hash perfecta sobre un conjunto de claves mayor que uno muy pequeño suele ser computacionalmente inviable; la función resultante probablemente sea computacionalmente más compleja que una función hash estándar y solo proporciona una ventaja marginal sobre una función con buenas propiedades estadísticas que produce 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 cubos frente a la distribución esperada (o uniforme) de los elementos. La fórmula es ^{[ 6 ].}

$${\displaystyle {\frac {m}{n}}{\sum _{j=1}^{m}b_{j}^{2}}-n}$$

donde n es el número de claves, m es el número de cubetas y b _j es el número de elementos en la cubeta j .

Una proporción dentro de un intervalo de confianza (como de 0,95 a 1,05) indica que la función hash evaluada tiene una distribución uniforme esperada.

Las funciones hash pueden tener ciertas propiedades técnicas que aumentan la probabilidad de que tengan una distribución uniforme al aplicarse. Una de ellas es el criterio de avalancha estricta : cada vez que se complementa un bit de entrada, cada uno de los bits de salida cambia con una probabilidad del 50 %. La razón de esta propiedad es que subconjuntos seleccionados del espacio de claves pueden tener baja variabilidad. Para que la salida se distribuya uniformemente, una baja variabilidad, incluso de un solo bit, debería traducirse en una alta 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 alrededor de esos valores. Si los bits tienden a cambiar con demasiada facilidad, 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. ^{[ 7 ]} Aquí se evalúa la relevancia del criterio para una función hash multiplicativa. ^{[ 8 ]}

En las aplicaciones de almacenamiento y recuperación de datos, el uso de una función hash implica un compromiso entre el tiempo de búsqueda y el espacio de almacenamiento. Si el tiempo de búsqueda fuera ilimitado, una lista lineal no ordenada muy compacta sería el medio óptimo; si el espacio de almacenamiento fuera ilimitado, una estructura de acceso aleatorio indexable por clave-valor sería muy grande y dispersa, pero muy rápida. Una función hash requiere un tiempo finito para mapear un espacio de claves potencialmente grande a un espacio de almacenamiento factible, que se puede buscar en un tiempo limitado, independientemente del número de claves. En la mayoría de las aplicaciones, la función hash debe poder calcularse con una latencia mínima y, secundariamente, con un número mínimo de instrucciones.

La complejidad computacional varía según el número de instrucciones requeridas y la latencia de cada instrucción individual. Los métodos más sencillos son los basados ​​en bits (plegado), seguidos de los métodos multiplicativos, y los más complejos (más lentos) son los basados ​​en la división.

Dado que las colisiones deberían ser poco frecuentes y causar un retraso mínimo, pero por lo demás inofensivas, generalmente es preferible elegir una función hash más rápida en lugar de una que requiera más cálculos pero que evite algunas colisiones.

Las implementaciones basadas en la división pueden ser particularmente problemáticas, ya que una división requiere múltiples ciclos en casi todas las microarquitecturas de procesadores . La división ( módulo ) por una constante se puede invertir para convertirse en una multiplicación por el inverso multiplicativo de tamaño de 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 restas y sumas con desplazamiento, aunque minimizar el número de tales operaciones requeridas es un problema complejo; el número de instrucciones en lenguaje máquina resultantes puede superar la docena y saturar la tubería. Si la microarquitectura cuenta con unidades funcionales de multiplicación de hardware , entonces la multiplicación por el inverso probablemente sea un mejor enfoque.

Podemos permitir que el tamaño de la tabla n no sea una potencia de 2 y aun 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 . Consideremos 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 bits a la derecha (posiblemente más rápido) : n P (clave) >> b .

Si las claves se someten a un proceso de hash repetido y la función hash es costosa, se puede ahorrar tiempo de cálculo precalculando los códigos hash y almacenándolos junto con las claves. Si los códigos hash coinciden, casi con toda seguridad las claves son idénticas. Esta técnica se utiliza en la tabla de transposición de los 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 de entre una familia de funciones de este tipo, de manera que la probabilidad de colisión entre dos claves distintas cualesquiera 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 utilizara 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 específico.

Una función hash que solo permite ciertos tamaños de tabla o cadenas de hasta cierta longitud, o que no puede aceptar una semilla (es decir, permite el doble hash) es menos útil que una que sí lo permite.

Una función hash es aplicable en diversas situaciones. Particularmente dentro de la criptografía, las aplicaciones notables incluyen: ^{[ 9 ]}

• Verificación de integridad : Los valores hash idénticos para diferentes archivos implican igualdad, lo que proporciona un medio fiable para detectar modificaciones en los archivos.
• Derivación de claves : Pequeños cambios en la entrada dan como resultado una alteración de la salida que parece aleatoria, conocida como propiedad de difusión. Por lo tanto, las funciones hash son valiosas para las funciones de derivación de claves.
• Códigos de autenticación de mensajes (MAC): Mediante la integración de una clave confidencial con los datos de entrada, las funciones hash pueden generar MAC que garanticen la autenticidad de los datos, como en el caso de los HMAC .
• Almacenamiento de contraseñas: El valor hash de la contraseña no revela ningún detalle de la misma, lo que subraya la importancia de almacenar de forma segura las contraseñas cifradas en el servidor.
• Firmas : Se firman los hashes de los mensajes en lugar del mensaje completo.

Un procedimiento de 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 que se van a hashear, 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 las funciones que dependen de la dirección de memoria del objeto que se está hasheando, ya que la dirección puede cambiar durante la ejecución (como puede ocurrir en sistemas que utilizan ciertos métodos de recolección de basura ), aunque a veces es posible volver a hashear el elemento.

El determinismo se da en el contexto de la reutilización de la función. Por ejemplo, Python añade la característica de que las funciones hash utilizan una semilla aleatoria que se genera una sola vez al iniciar el proceso de Python, además de la entrada que se va a hashear. ^{[ 10 ]} La función hash de Python ( SipHash ) sigue siendo una función hash válida cuando se utiliza dentro de una sola ejecución, pero si los valores se persisten (por ejemplo, se escriben en el disco), ya no se pueden tratar como valores hash válidos, puesto que en la siguiente ejecución el valor aleatorio podría ser diferente.

A menudo es deseable que la salida de una función hash tenga un tamaño fijo (pero véase más adelante). Si, por ejemplo, la salida está restringida a valores enteros de 32 bits, los valores hash se pueden usar para indexar una matriz. Este tipo de hash se usa comúnmente para acelerar las búsquedas de datos. ^{[ 11 ]} 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 usan alguna expresión aritmética que procesa iterativamente fragmentos de la entrada (como los caracteres de una cadena) para producir el valor hash. ^{[ 11 ]}

En muchas aplicaciones, el rango de valores hash puede variar en cada ejecución del programa o cambiar durante la misma ejecución (por ejemplo, cuando se necesita expandir una tabla hash). En esos casos, se requiere una función hash que acepte dos parámetros: los datos de entrada z y el número n de valores hash permitidos.

Una solución común consiste en calcular una función hash fija con un rango muy amplio (por ejemplo, ^de 0 a 2³² − 1   ), dividir el resultado por n y utilizar el resto de la división . Si n es una potencia de 2 , esto se puede lograr mediante enmascaramiento y desplazamiento de bits . Al utilizar este método, 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 aparecer 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 perdura más allá de 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 el número mínimo 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 está hasheando y n es el número 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 esta se convierte en una función de las claves previamente insertadas. Se han inventado varios algoritmos que preservan la propiedad de uniformidad, pero que requieren un tiempo proporcional a n para calcular el valor de H ( z , 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 irrelevantes para la comparación. Por ejemplo, al buscar un nombre, puede ser conveniente ignorar la distinción entre mayúsculas y minúsculas. Para este tipo de datos, se debe utilizar una función hash compatible con el criterio de equivalencia de datos empleado: es decir, dos entradas consideradas equivalentes deben generar el mismo valor hash. Esto se puede lograr normalizando la entrada antes de aplicar la función hash, por ejemplo, convirtiendo todas las letras a mayúsculas.

Si los datos a procesar 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 prácticamente cero. Esta función hash es perfecta , ya que asigna a cada entrada un valor hash distinto.

El significado de "suficientemente pequeño" depende del tamaño del tipo de dato utilizado como valor hash. Por ejemplo, en Java , el código hash es un entero de 32 bits. Por lo tanto, los objetos enteros Integery de punto flotante de 32 bits Floatpueden usar el valor directamente, mientras que los enteros Longy de punto flotante de 64 bits Doubleno pueden.

Otros tipos de datos también pueden usar este esquema de 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 entero, para indexar una tabla que da 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 latín ISO 1 ), la tabla tiene solo 2⁸ ⁼ 256 entradas; en el caso de caracteres Unicode , la tabla tendría 17 × ^2¹⁶ =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 sean esencialmente aleatorios, entonces se puede considerar que ya están "hasheadas". En este caso, cualquier cantidad de bits cualesquiera de la clave se puede extraer y cotejar 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 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 es123 456 789 y el tamaño de la tabla hash10 000 , luego elevar al cuadrado la clave produce15 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 más alto) 8750. El método de cuadrados centrales 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 consiste en utilizar una función módulo sobre 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 proporciona una distribución de {0, M − 1} . Esto ofrece buenos resultados sobre un gran número de conjuntos de claves. Una desventaja significativa del hash por división es que la división requiere múltiples ciclos en la mayoría de las arquitecturas modernas (incluida x86 ) y puede ser 10 veces más lenta que la multiplicación. Otra desventaja es que no separará las claves agrupadas. Por ejemplo, las claves 123000, 456000, 789000, etc., módulo 1000, se asignan 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 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} + ⋯ + ζ ₀ . Una clave K = ( k _{n − 1} … k ₁ k ₀ ) ₂ puede considerarse como el polinomio K ( x ) = k _{n − 1} x ^{n − 1} + ⋯ + k ₁ x + k ₀ . El resto usando aritmética polinomial módulo 2 es K ( x ) mod Z ( x ) = h _{m − 1} x ^{m − 1} + ⋯ h ₁ x + h ₀ . Entonces h ( K ) = ( h _{m − 1} … h ₁ h ₀ ) ₂ . Si Z ( x ) se construye para tener t o menos coeficientes distintos de cero, entonces las claves que comparten menos de t bits tienen garantizado que no colisionarán.

Z es una función de k , t y n (el último de los cuales es un divisor de 2k − 1 ) y se construye a partir del cuerpo finito GF(2k ⁾ . 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 enteros tal que {1,2, … , t } ⊆ S y (2 j mod n ) ∈ S ∀ j ∈ S . ^{[ Notas 3 ]}

Definir${\displaystyle P(x)=\prod _{j\in S}(x-\alpha ^{j})}$donde α ∈ ⁿ GF(2 ^k ) y donde los coeficientes de P ( x ) se calculan en este campo. Entonces el grado de P ( x ) = | S | . Dado que α ^{2 j} es una raíz de P ( x ) siempre que α ^j sea una raíz, se deduce que los coeficientes p ⁱ de P ( x ) satisfacen p ² _i = p _i , por lo que todos son 0 o 1. Si R ( x ) = r _{n − 1} x ^{n − 1} + ⋯ + r ₁ x + r ₀ es cualquier polinomio no nulo módulo 2 con como máximo t coeficientes no nulos, entonces R ( x ) no es un múltiplo de P ( x ) módulo 2. ^{[ Notas 4 ]} Si 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, para que el esquema sea computacionalmente factible, n o t aumenten considerablemente, o ambos. Por lo tanto, es más adecuado para su implementación en hardware o microcódigo. ^{[ 3 ] : 542–543}

El hash de permutación única tiene garantizado un tiempo de inserción en el peor de los casos óptimo. ^{[ 12 ]}

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 debe ser relativamente primo con W ; debe ser grande y su representación binaria una mezcla aleatoria 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 palabra de la 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 los 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 ) { return ( a * K ) >> ( w - m ); }

y para valores fijos de m y w, esto se traduce en una sola multiplicación entera y un 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. ^{[ 13 ]} Una transmutación en la entrada que desplaza el rango de los bits superiores retenidos hacia abajo y los combina mediante XOR o ADD a la clave antes del paso de multiplicación corrige esto. La función resultante se ve así: ^{[ 8 ]}

hash sin signo ( K ​​sin signo ) { K ^= K >> ( w - m ); return ( a * K ) >> ( w - m ); }

^{El hash de} Fibonacci es una forma de hash multiplicativo en la que el multiplicador es 2w / ϕ , 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 la tabla 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:

• 16: a = 9E37 ₁₆ =40 503 ₁₀
• 32: a = 9E37 79B9 ₁₆ =2 654 435 769 ₁₀
• 48: a = 9E37 79B9 7F4B ₁₆ =173 961 102 589 771 ₁₀ ^{[ Notas 5 ]}
• 64: a = 9E37 79B9 7F4A 7C15 ₁₆ =11 400 714 819 323 198 485 ₁₀

El multiplicador debe ser impar, de modo que el bit menos significativo de la salida sea invertible módulo ^2w . Los dos últimos valores dados anteriormente se redondean (hacia arriba y hacia abajo, respectivamente) en más de la mitad de un bit menos significativo para lograr esto.

El hash de Zobrist , que recibe su nombre de Albert Zobrist , es una forma de hash tabulado , un método para construir familias universales de funciones hash combinando la búsqueda en tablas con operaciones XOR. Este algoritmo ha demostrado ser muy rápido y de alta calidad para fines de hash (especialmente para el hash de claves numéricas enteras). ^{[ 14 ]}

El hash Zobrist se introdujo originalmente como un método para representar de forma compacta las posiciones de ajedrez en programas de juegos de ordenador. Se asignaba un número aleatorio único a cada tipo de pieza (seis para las blancas y seis para las negras) en cada casilla del tablero. Así, al inicio del programa, se inicializaba una tabla de 64 × 12 de estos números. Los números aleatorios podían tener cualquier longitud, pero 64 bits era lo más adecuado debido a las 64 casillas del tablero. Una posición se transcribía recorriendo las piezas, indexando los números aleatorios correspondientes (las casillas vacías no se incluían en el cálculo) y aplicando la operación XOR (el valor inicial podía ser 0, el valor neutro de XOR, o una semilla aleatoria ). El valor resultante se reducía mediante módulo, plegado u otra operación para generar un índice en la tabla hash. El hash Zobrist original se almacenaba en la tabla como la representación de la posición.

Posteriormente, el método se extendió al hash de enteros representando cada byte en cada una de las 4 posiciones posibles de la palabra con un número aleatorio único de 32 bits. De esta forma, se construye una tabla de 2⁸ ^× 4 números aleatorios. Un entero hash de 32 bits se transcribe indexando sucesivamente la tabla con el valor de cada byte del entero en texto plano y aplicando la operación XOR a los valores cargados (el valor inicial puede ser el valor de identidad o una semilla aleatoria). La extensión natural a enteros de 64 bits se realiza mediante una tabla de 2⁸ ^× 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 cualquier 3-tupla de claves tiene la misma probabilidad de ser asignada a cualquier 3-tupla de valores hash.

Se puede diseñar una función hash para aprovechar la entropía presente en las claves. Si las claves tienen ceros iniciales o finales, o campos específicos que no se utilizan, que siempre son cero o constantes, o que 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. La selección de divisores o multiplicadores en los esquemas de división y multiplicación puede generar funciones hash más uniformes si las claves son cíclicas o presentan otras redundancias.

Las funciones hash simples pueden sumar los primeros y los últimos n caracteres de una cadena junto con su longitud, o generar un hash del tamaño de una palabra a partir de los 4 caracteres centrales de la cadena. Esto evita iterar sobre la cadena (potencialmente larga), pero las funciones hash que no aplican hash a todos los caracteres de una cadena pueden volverse lineales fácilmente debido a redundancias, agrupamiento u otras anomalías en el conjunto de claves. Estas estrategias pueden ser efectivas como función hash personalizada si la estructura de las claves es tal que los campos centrales, finales 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 consiste en 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. Utilizar la operación OR exclusiva en lugar de la suma también es una alternativa plausible. La operación final sería un módulo, una 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 el último código de byte ni la mayoría de los primeros 32 códigos de bytes, por lo que la información, que utiliza los códigos de bytes restantes, se agrupa en los bits restantes de una manera poco evidente.

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 generar hashes de identificadores en tablas de símbolos del compilador, como se indica en el "Libro del Dragón" . ^{[ 15 ]} Esta función hash desplaza los bytes 4 bits antes de sumarlos. Cuando la cantidad se reinicia, los 4 bits superiores se desplazan hacia afuera y, si no son cero, se combinan mediante XOR con el byte inferior de la cantidad acumulada. El resultado es un código hash de tamaño de 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, se dispone de un método mucho más eficiente de hash de cadenas de longitud variable 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 carácter por carácter, sino que se interpretan como una matriz de enteros de 32 o 64 bits y se acumulan estos valores enteros de "palabra ancha" mediante operaciones aritméticas (por ejemplo, multiplicación por una constante y desplazamiento de bits). La palabra final, que puede tener posiciones de bytes sin ocupar, se rellena con ceros o un valor aleatorio específico antes de incorporarse al hash. El código hash acumulado se reduce mediante una operación de módulo u otra operación para generar un índice en la tabla.

Análogamente a cómo 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 ₁ a + x ₀ . Esto es simplemente un polinomio en una base a > 1   que toma los componentes ( x ₀ , x ₁ ,..., x _{k −1} ) como los caracteres de la cadena de entrada de longitud k . Se puede usar directamente como código hash, o una función hash aplicada para mapear el valor potencialmente grande al tamaño de la tabla hash. El valor de a suele ser un número primo lo suficientemente grande como para contener la cantidad de caracteres diferentes en el conjunto de caracteres de las claves potenciales. El hash de conversión de base de cadenas minimiza la cantidad de colisiones. ^{[ 16 ]} Los tamaños de datos disponibles pueden restringir la longitud máxima de la cadena que se puede hashear con este método. Por ejemplo, una palabra de 128 bits solo procesará una cadena alfabética de 26 caracteres (sin tener en cuenta mayúsculas ni minúsculas) con una base de 29; una cadena ASCII imprimible se limita a 9 caracteres con una base de 97 y una palabra de 64 bits. Sin embargo, las claves alfabéticas suelen ser de longitud moderada, ya que deben almacenarse en la tabla hash. Las cadenas de caracteres numéricos no suelen presentar problemas; 64 bits pueden contar hasta ^10¹⁹ , 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 dada de n caracteres, avanzando una ventana de ancho k caracteres a lo largo de la cadena, donde k es un entero fijo y n > k . La solución directa, 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 hash rodante para calcular todos esos hashes con un esfuerzo proporcional a mk + n, donde m es el número de ocurrencias de la subcadena. ^{[ 17 ]}  

El algoritmo más conocido de este tipo es Rabin-Karp, con un rendimiento en el mejor y promedio caso de O ( n + mk ) y en el peor caso de O ( n · k ) (para ser justos, el peor caso aquí es gravemente patológico: tanto la cadena de texto como la subcadena están compuestas por 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.