Hash de tabulación

En informática , el hash tabulado es un método para construir familias universales de funciones hash combinando la búsqueda en tablas con operaciones OR exclusivas . Se estudió inicialmente en forma de hash Zobrist para videojuegos; posteriormente, Carter y Wegman extendieron este método a claves arbitrarias de longitud fija. También se han desarrollado generalizaciones del hash tabulado que pueden manejar claves de longitud variable, como cadenas de texto.

A pesar de su simplicidad, el hashing tabulado posee sólidas propiedades teóricas que lo distinguen de otras funciones hash. En particular, es 3-independiente : cualquier tríada de claves tiene la misma probabilidad de ser mapeada a cualquier tríada de valores hash. Sin embargo, no es 4-independiente. Variantes más sofisticadas, aunque más lentas, del hashing tabulado extienden el método a grados de independencia superiores.

Debido a su alto grado de independencia, el hash por tabulación se puede utilizar con métodos de hash que requieren una función hash de alta calidad, incluidos el hash hopscotch , el hash cuckoo y la técnica MinHash para estimar el tamaño de las intersecciones de conjuntos.

La idea básica es la siguiente:

Primero, divide la clave que se va a hashear en "bloques" más pequeños de una longitud elegida. Luego, crea un conjunto de tablas de búsqueda , una para cada bloque, y llénalas con valores aleatorios. Finalmente, usa las tablas para calcular un valor hash para cada bloque y combina todos estos hashes en un valor hash final usando la operación OR exclusiva a nivel de bits . ^{[ 1 ]}

De forma más formal:

Sea p el número de bits en una clave a hashear, y q el número de bits deseados en una función hash de salida. Elija un tamaño de bloque r ≤ p ; la elección del tamaño del bloque controla el equilibrio entre el tiempo y el uso de memoria, por lo que debe hacerse de manera que las tablas no sean demasiado grandes, por ejemplo, de manera que las tablas quepan en la memoria caché de la computadora . ^{[ 2 ]} Los bloques más pequeños usan menos memoria pero ralentizan la función hash. Calcule t = ceil( p / r ), el número de bloques de r bits necesarios para representar una clave.

Create a two-dimensional 2^r × t array, T, and fill it with random q-bit numbers. Now T can be used to compute the hash value h(x) of any given key x. To do so, partition x into r-bit values, where x₀ consists of the lowest r bits of x, x₁ consists of the next r bits, etc. For example, if r = 8, then x_i is just the ith byte of x. Then, use these r-bit and position values as indices into T, and combine the results using the exclusive or operation:^[1]

h(x) = T[0][x₀] ⊕ T[1][x₁] ⊕ T[2][x₂] ⊕ ... ⊕ T[t-1][x_t-1].

Note that it is not valid to use the same table (e.g. T[0]) for each x_i, since then the hash function would not be able to distinguish between strings with the same x_is, but permuted differently.

Code for a typical example with r = t = 8 and q = p = 64 is given below.

// Secret table of random numbersuint64_tT[8][256];for(inti=0;i<8;i++)for(intj=0;j<256;j++)T[i][j]=getRandomUInt64();// Simple Tabulation Hash functionuint64_thash(uint64_tx){uint64_tres=0;for(inti=0;i<8;i++)res^=T[i][(char)(x>>8*i)];returnres;}

The first instance of tabulation hashing is Zobrist hashing, a method for hashing positions in abstract board games such as chess named after Albert Lindsey Zobrist, who published it in 1970.^[3] In this method, a random bitstring is generated for each game feature such as a combination of a chess piece and a square of the chessboard. Then, to hash any game position, the bitstrings for the features of that position are combined by a bitwise exclusive or. The resulting hash value can then be used as an index into a transposition table. Because each move typically changes only a small number of game features, the Zobrist value of the position after a move can be updated quickly from the value of the position before the move, without needing to loop over all of the features of the position.^[4]

Tabulation hashing in greater generality, for arbitrary binary values, was later rediscovered by Carter & Wegman (1979) and studied in more detail by Pătraşcu & Thorup (2012).

Carter y Wegman (1979) definen un esquema aleatorio para generar funciones hash como universal si, para cualesquiera dos claves, la probabilidad de que colisionen (es decir, que se les asigne el mismo valor) es 1/ m , donde m es el número de valores que pueden tomar las claves. En el artículo posterior de Wegman y Carter (1981) definieron una propiedad más fuerte : un esquema aleatorio para generar funciones hash es k -independiente si, para cada k - tupla de claves y cada posible k -tupla de valores, la probabilidad de que esas claves se asignen a esos valores es 1/ m ^k . Los esquemas de hash 2-independientes son automáticamente universales, y cualquier esquema de hash universal puede convertirse en un esquema 2-independiente almacenando un número aleatorio x como parte de la fase de inicialización del algoritmo y sumando x a cada valor hash. Por lo tanto, la universalidad es esencialmente lo mismo que la 2-independencia. Sin embargo, la independencia de k para valores mayores de k es una propiedad más fuerte, que poseen menos algoritmos de hash.

Como observan Pătraşcu y Thorup (2012) , el hashing tabulado es 3-independiente pero no 4-independiente. Para cualquier clave única x , T [ x0,0 ] tiene la misma probabilidad de tomar cualquier valor hash, y la operación OR exclusiva de T [ x0,0 ] con los valores restantes _de la tabla no cambia esta propiedad. Para cualesquiera dos claves x e y , x tiene la misma probabilidad de ser mapeada a cualquier valor hash como antes, y hay al menos una posición i donde x _{i ≠} y _i ; el valor de la tabla T [ y _i , i ] se usa en el cálculo de  h  ( y ) pero no en el cálculo de h ( x ), por lo que incluso después de que se haya determinado el valor de h ( x ), h ( y ) tiene la misma probabilidad de ser cualquier valor hash válido. De manera similar, para cualesquiera tres claves x , y y z , al menos una de las tres claves tiene una posición i donde su valor z _i difiere de las otras dos, de modo que incluso después de que se determinen los valores de h ( x ) y h ( y ), h ( z ) tiene la misma probabilidad de ser cualquier valor hash válido. ^{[ 5 ]}

Sin embargo, este razonamiento falla para cuatro claves porque existen conjuntos de claves w , x , y y z donde ninguna de las cuatro tiene un valor de byte que no comparta con al menos una de las otras claves. Por ejemplo, si las claves tienen dos bytes cada una, y w , x , y y z son las cuatro claves que tienen cero o uno como valores de byte, entonces cada valor de byte en cada posición es compartido por exactamente dos de las cuatro claves. Para estas cuatro claves, los valores hash calculados mediante el hashing por tabulación siempre satisfarán la ecuación h ( w ) ⊕ h ( x ) ⊕ h ( y ) ⊕ h ( z ) = 0 , mientras que para un esquema de hashing 4-independiente la misma ecuación solo se satisfaría con una probabilidad de 1/ m . Por lo tanto, el hashing por tabulación no es 4-independiente. ^{[ 5 ]}

Dado que el hash tabulado es un esquema de hash universal, puede utilizarse en cualquier algoritmo basado en hash donde la universalidad sea suficiente. Por ejemplo, en el encadenamiento de hashes , el tiempo esperado por operación es proporcional a la suma de las probabilidades de colisión, que es la misma para cualquier esquema universal que para funciones hash verdaderamente aleatorias, y es constante siempre que el factor de carga de la tabla hash sea constante. Por lo tanto, el hash tabulado puede utilizarse para calcular funciones hash para el encadenamiento de hashes con una garantía teórica de tiempo esperado constante por operación. ^{[ 6 ]}

Sin embargo, el hash universal no es lo suficientemente robusto como para garantizar el rendimiento de otros algoritmos de hash. Por ejemplo, para el sondeo lineal , las funciones hash de 5 independientes son lo suficientemente robustas como para garantizar una operación en tiempo constante, pero existen funciones hash de 4 independientes que no lo logran. ^{[ 7 ]} No obstante, a pesar de ser solo de 3 independientes, el hash de tabulación proporciona la misma garantía de tiempo constante para el sondeo lineal. ^{[ 8 ]}

El hash cuckoo , otra técnica para implementar tablas hash , garantiza un tiempo constante por búsqueda (independientemente de la función hash). Las inserciones en una tabla hash cuckoo pueden fallar, lo que provoca la reconstrucción completa de la tabla, pero tales fallos son suficientemente improbables como para que el tiempo esperado por inserción (utilizando una función hash verdaderamente aleatoria o una función hash con independencia logarítmica) sea constante. Por otro lado, con el hash por tabulación, la mejor cota conocida para la probabilidad de fallo es mayor, lo suficientemente alta como para que no se pueda garantizar que las inserciones tomen un tiempo esperado constante. Sin embargo, el hash por tabulación es adecuado para asegurar la construcción de una tabla hash cuckoo con un tiempo esperado lineal para un conjunto estático de claves que no cambia a medida que se usa la tabla. ^{[ 8 ]}

Aunque el hashing tabulado descrito anteriormente ("hashing tabulado simple") solo es 3-independiente, se pueden usar variaciones de este método para obtener funciones hash con grados de independencia mucho mayores. Siegel (2004) usa la misma idea de usar operaciones OR exclusivas para combinar valores aleatorios de una tabla, con un algoritmo más complejo basado en grafos expansores para transformar los bits de clave en índices de tabla, para definir esquemas de hashing que son k -independientes para cualquier valor constante o incluso logarítmico de k . Sin embargo, el número de búsquedas en la tabla necesarias para calcular cada valor hash usando la variación de Siegel del hashing tabulado, aunque constante, sigue siendo demasiado grande para ser práctico, y el uso de expansores en la técnica de Siegel también hace que no sea completamente constructiva. Thorup (2013) proporciona un esquema basado en el hashing tabulado que alcanza altos grados de independencia más rápidamente, de una manera más constructiva. Observa que al usar una ronda de hash de tabulación simple para expandir las claves de entrada a seis veces su longitud original, y luego una segunda ronda de hash de tabulación simple en las claves expandidas, se obtiene un esquema de hash cuyo número de independencia es exponencial en el parámetro r , el número de bits por bloque en la partición de las claves en bloques.

La tabulación simple se limita a claves de longitud fija, ya que se necesita inicializar una tabla diferente de valores aleatorios para cada posición de un bloque en las claves. Lemire (2012) estudia variaciones del hash tabulado adecuado para claves de longitud variable, como cadenas de caracteres. El tipo general de esquema de hash estudiado por Lemire utiliza una única tabla T indexada por el valor de un bloque, independientemente de su posición dentro de la clave. Sin embargo, los valores de esta tabla pueden combinarse mediante una función más compleja que la OR exclusiva bit a bit. Lemire demuestra que ningún esquema de este tipo puede ser 3-independiente. No obstante, demuestra que aún es posible lograr la 2-independencia. En particular, un esquema tabulado que interpreta los valores T [ xᵢ ] (donde xᵢ _es , como antes, el i -ésimo bloque de la entrada) como los coeficientes de un polinomio sobre un cuerpo finito y luego toma el resto del polinomio resultante módulo otro polinomio, da como resultado una función hash 2-independiente _.

El hash de tabulación mixta (y el menos general Twisted Tabulation) fue introducido por Dahlgaard y Thorup ^{[ 9 ]} como una forma de fortalecer las propiedades del hash de tabulación manteniendo prácticamente el mismo rendimiento. La tabulación mixta puede considerarse como la aplicación de una operación XOR a una función hash de "doble tabulación" de Thorup (2013) con una función hash de tabulación simple. Esto resulta tener muchas propiedades interesantes, incluso cuando se eligen parámetros para que la tabulación mixta sea mucho más rápida que la doble tabulación ^{[ 10 ].}

La idea es elegir un número y convertirlo a bits en lugar de simplemente . Esto genera nuevos "caracteres derivados" que se convierten a bits mediante una segunda función hash y los dos valores se combinan mediante XOR. Formalmente tenemos y , ambas funciones de tabulación simples. Si , entonces el hash de tabulación mixto se define como${\displaystyle d}$${\displaystyle 2^{rd+q}}$${\displaystyle 2^{q}}$${\displaystyle d}$${\displaystyle h_{1}:[2^{p}]\to [2^{rd}]\times [2^{q}]}$${\displaystyle h_{2}:[2^{rd}]\to [2^{q}]}$${\displaystyle (v_{1},v_{2})=h_{1}(x)}$${\displaystyle h(x)=h_{2}(v_{1})\oplus v_{2}.}$

El siguiente ejemplo muestra el algoritmo con , y : ${\displaystyle p=q=64}$${\displaystyle r=8}$${\displaystyle d=2}$

int D = 2 ; uint128_t T1 [ 8 ][ 256 ]; uint64_t T2 [ D ][ 256 ];// Rellenar tablas con valores aleatorios for ( int j = 0 ; j < 256 ; j ++ ) { for ( int i = 0 ; i < 8 ; i ++ ) T1 [ i ][ j ] = getRandomUInt128 (); for ( int i = 0 ; i < D ; i ++ ) T2 [ i ][ j ] = getRandomUInt64 (); }// Calcular la tabulación mixta de x con caracteres derivados de D uint64_t hash ( uint64_t x ) { uint128_t v1v2 = 0 ; for ( int i = 0 ; i < 8 ; i ++ ) v1v2 ^= T1 [ i ][( char )( x >> 8 * i )]; uint64_t v1 = v1v2 >> 64 ; // Tomar v1 de los bits bajos uint64_t h = ( uint64_t ) v1v2 ; // Tomar v2 de los bits altos for ( int i = 0 ; i < D ; i ++ ) h ^= T2 [ i ][( char )( v1 >> 8 * i )]; return h ; }

En 2016 se demostró que la tabulación mixta ^{[ 11 ]} tiene una fuerte concentración con respecto a las k -particiones, que son útiles en algoritmos para contar elementos distintos, como el método clásico de Flajolet y Martin .

Fuentes secundarias

• Morin, Pat (22 de febrero de 2014), "Sección 5.2.3: Hashing por tabulación", Estructuras de datos abiertas (en pseudocódigo) ( ed. β de 0,1 GB  ), págs.  115-116 , consultado el 8 de enero de 2016..
• Mitzenmacher, Michael ; Upfal, Eli (2014), "Algunos algoritmos y estructuras de datos aleatorios prácticos", en Tucker, Allen; Gonzalez, Teofilo ; Diaz-Herrera, Jorge (eds.), Computing Handbook: Computer Science and Software Engineering (3.ª ed.), CRC Press, pp. 11-1 – 11-23, ISBN 9781439898529. Véase en particular la Sección 11.1.1: Hashing de tabulación, págs. 11-3 – 11-4 .

Fuentes primarias