Hashing de tabulación

Funciones hash calculadas por exclusivo o

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

A pesar de su simplicidad, el hash de tabulación tiene fuertes propiedades teóricas que lo distinguen de otras funciones hash. En particular, es independiente de 3 factores : cada 3-tupla de claves tiene la misma probabilidad de ser asignada a cualquier 3-tupla de valores hash. Sin embargo, no es independiente de 4 factores. Las variantes más sofisticadas pero más lentas del hash de tabulación extienden el método a mayores grados de independencia.

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

Método

La idea básica es la siguiente:

En primer lugar, divida la clave a codificar en "bloques" más pequeños de una longitud elegida. Luego, cree un conjunto de tablas de búsqueda , una para cada bloque, y llénelas con valores aleatorios. Finalmente, use las tablas para calcular un valor hash para cada bloque y combine todos estos hashes en un valor hash final utilizando la operación exclusiva bit a bit o ^{[1] .}

Más formalmente:

Sea p el número de bits de una clave a la que se aplicará el algoritmo hash, 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 de bloque controla el equilibrio entre el tiempo y el uso de memoria, por lo que debe hacerse de modo que las tablas no sean demasiado grandes, por ejemplo, de modo que 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.

Cree una matriz bidimensional de 2 ^r × t , T , y rellénela con números aleatorios de q bits. Ahora T se puede utilizar para calcular el valor hash h ( x ) de cualquier clave dada  x . Para ello, divida x en valores de r bits, donde x ₀ consiste en los r bits más bajos de x , x ₁ consiste en los r bits siguientes, etc. Por ejemplo, si r  = 8, entonces x _i es solo el i ésimo byte de x . Luego, use estos r bits y valores de posición como índices en T , y combine los resultados usando la operación o exclusiva: ^[1]

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

Nótese que no es válido utilizar la misma tabla (por ejemplo, T[0] ) para cada x _i , ya que entonces la función hash no podría distinguir entre cadenas con las mismas x _i s, pero permutadas de forma diferente.

 A continuación se muestra el código para un ejemplo típico con r  =  t  = 8 y q  =  p = 64.

// Tabla secreta de números aleatorios uint64_t T [ 8 ][ 256 ]; para ( int i = 0 ; i < 8 ; i ++ ) para ( int j = 0 ; j < 256 ; j ++ ) T [ i ][ j ] = getRandomUInt64 ();                     // Función hash de tabulación simple uint64_t hash ( uint64_t x ) { uint64_t res = 0 ; for ( int i = 0 ; i < 8 ; i ++ ) res ^= T [ i ][( char )( x >> 8 * i )]; return res ; }                       

Historia

El primer ejemplo de hash de tabulación es el hash Zobrist , un método para hashes de posiciones en juegos de mesa abstractos como el ajedrez que lleva el nombre de Albert Lindsey Zobrist , quien lo publicó en 1970. ^[3] En este método, se genera una cadena de bits aleatoria para cada característica del juego, como una combinación de una pieza de ajedrez y un cuadrado del tablero de ajedrez. Luego, para hashear cualquier posición del juego, las cadenas de bits para las características de esa posición se combinan mediante un or exclusivo bit a bit. El valor hash resultante se puede usar como índice en una tabla de transposición . Debido a que cada movimiento generalmente cambia solo una pequeña cantidad de características del juego, el valor Zobrist de la posición después de un movimiento se puede actualizar rápidamente a partir del valor de la posición antes del movimiento, sin necesidad de recorrer todas las características de la posición. ^[4]

El hash de tabulación con mayor generalidad, para valores binarios arbitrarios, fue redescubierto posteriormente por Carter y Wegman (1979) y estudiado con más detalle por Pătraşcu y Thorup (2012).

Universalidad

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

Como observan Pătraşcu y Thorup (2012), el hash de tabulación es independiente de 3 pero no de 4. Para cualquier clave x , T [ x ₀ ,0] tiene la misma probabilidad de tomar cualquier valor hash, y la operación exclusiva o de T [ x ₀ ,0] con los valores de tabla restantes no cambia esta propiedad. Para dos claves x e y , x tiene la misma probabilidad de asignarse a cualquier valor hash como antes, y hay al menos una posición i donde x _i  ≠  y _i ; el valor de tabla T [ y _i , i ] se utiliza 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 los otros dos, de modo que incluso después de que se determinen los valores de h ( x ) y h ( y ), es igualmente probable que h ( z ) sea cualquier valor hash válido. ^[5]

Sin embargo, este razonamiento no es válido para cuatro claves porque hay 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 sus 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 hash de tabulación siempre satisfarán la ecuación h ( w ) ⊕ h ( x ) ⊕ h ( y ) ⊕ h ( z ) = 0 , mientras que para un esquema de hash 4-independiente la misma ecuación solo se satisfaría con una probabilidad de 1/ m . Por lo tanto, el hash de tabulación no es 4-independiente. ^[5]

Solicitud

Debido a que el hash de tabulación es un esquema de hash universal, se puede utilizar en cualquier algoritmo basado en hash en el que la universalidad sea suficiente. Por ejemplo, en el encadenamiento de hash , 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 las funciones hash verdaderamente aleatorias, y es constante siempre que el factor de carga de la tabla hash sea constante. Por lo tanto, el hash de tabulación se puede utilizar para calcular funciones hash para el encadenamiento de hash con una garantía teórica de tiempo esperado constante por operación. ^[6]

Sin embargo, el hash universal no es lo suficientemente fuerte como para garantizar el rendimiento de algunos otros algoritmos de hash. Por ejemplo, para el sondeo lineal , las funciones hash de 5 independientes son lo suficientemente fuertes como para garantizar una operación de tiempo constante, pero hay funciones hash de 4 independientes que fallan. ^[7] Sin embargo, a pesar de ser solo 3 independientes, el hash de tabulación proporciona la misma garantía de tiempo constante para el sondeo lineal. ^[8]

El hash de cuco , 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 de cuco pueden fallar, lo que hace que se reconstruya toda la tabla, pero tales fallas son lo suficientemente improbables como para que el tiempo esperado por inserción (usando una función hash verdaderamente aleatoria o una función hash con independencia logarítmica) sea constante. Con el hash de tabulación, por otro lado, el mejor límite conocido en la probabilidad de falla es más alto, lo suficientemente alto como para que no se pueda garantizar que las inserciones tomen un tiempo esperado constante. Sin embargo, el hash de tabulación es adecuado para asegurar la construcción de tiempo esperado lineal de una tabla hash de cuco para un conjunto estático de claves que no cambia a medida que se usa la tabla. ^[8]

Extensiones

Aunque el hash de tabulación como el descrito anteriormente ("hashing de tabulación simple") es solo 3-independiente, se pueden usar variaciones de este método para obtener funciones hash con grados mucho más altos de independencia. Siegel (2004) usa la misma idea de usar operaciones o exclusivas para combinar valores aleatorios de una tabla, con un algoritmo más complicado basado en gráficos de expansores para transformar los bits clave en índices de tabla, para definir esquemas de hash que son k -independientes para cualquier valor constante o incluso logarítmico de k . Sin embargo, la cantidad de búsquedas de tabla necesarias para calcular cada valor hash usando la variación de Siegel del hash de tabulación, aunque constante, todavía es demasiado grande para ser práctica, 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 hash de tabulación que alcanza altos grados de independencia más rápidamente, de una manera más constructiva. Observa que al utilizar 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 como resultado 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 está limitada a claves de una longitud fija, porque 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 de tabulación adecuadas 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 se pueden combinar mediante una función más complicada que la función exclusiva bit a bit o. Lemire muestra que ningún esquema de este tipo puede ser 3-independiente. Sin embargo, demuestra que todavía es posible lograr la 2-independencia. En particular, un esquema de tabulación que interpreta los valores T [ x _i ] (donde x _i es, como antes, el i ésimo bloque de la entrada) como los coeficientes de un polinomio sobre un campo finito y luego toma el resto del polinomio resultante módulo otro polinomio, da una función hash 2-independiente.

Tabulación mixta

^{Dahlgaard y Thorup [9]} introdujeron el hash de tabulación mixta (y el menos general, Twisted Tabulation) como una forma de fortalecer las propiedades del hash de tabulación manteniendo casi el mismo rendimiento. La tabulación mixta puede verse como una operación XOR de una función hash de "tabulación doble" 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 hacer que la tabulación mixta sea mucho más rápida que la tabulación doble ^[10].

La idea es elegir un número y convertirlo en bits en lugar de solo . Esto genera nuevos "caracteres derivados" que se convierten en 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 para ( int j = 0 ; j < 256 ; j ++ ) { para ( int i = 0 ; i < 8 ; i ++ ) T1 [ i ][ j ] = getRandomUInt128 (); para ( int i = 0 ; i < D ; i ++ ) T2 [ i ][ j ] = getRandomUInt64 (); }                                 // Calcular 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 [11]} se demostró que la tabulación mixta tiene una fuerte concentración con respecto a las particiones k , que son útiles en algoritmos para contar elementos distintos, como el método clásico de Flajolet y Martin .

Notas

1. Morin (2014); Mitzenmacher y Upfal (2014).
2. Mitzenmacher y Upfal (2014).
3. Thorup (2013).
4. Zobrist (1970).
5. Pătraşcu y Thorup (2012); Mitzenmacher y Upfal (2014).
6. Carter y Wegman (1979).
7. Para conocer la suficiencia del algoritmo hash 5-independiente para el sondeo lineal, véase Pagh, Pagh y Ružić (2009). Para ver ejemplos de esquemas hash más débiles que fallan, véase Pătraşcu y Thorup (2010).
8. Pătraşcu y Thorup (2012).
9. Dahlgaard, Søren y Mikkel Thorup. "Independencia aproximadamente mínima con tabulación retorcida". Taller escandinavo sobre teoría de algoritmos. Springer, Cham, 2014.
10. Aamand, Anders, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, Mikkel Thorup. "Hash rápido con fuertes límites de concentración". Actas del 52º Simposio Anual ACM SIGACT sobre Teoría de la Computación. 2020.
11. Dahlgaard, Søren y col. "Hashing para estadísticas sobre k-particiones". 56º Simposio Anual del IEEE de 2015 sobre fundamentos de la informática. IEEE, 2015.

Referencias

Fuentes secundarias

• Morin, Pat (22 de febrero de 2014), "Sección 5.2.3: Hashing de tabulación", Open Data Structures (en pseudocódigo) (0.1G β  ed.), págs. 115-116 , consultado el 8 de enero de 2016.
• Mitzenmacher, Michael ; Upfal, Eli (2014), "Algunos algoritmos aleatorios prácticos y estructuras de datos", 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

• Carter, J. Lawrence; Wegman, Mark N. (1979), "Clases universales de funciones hash", Journal of Computer and System Sciences , 18 (2): 143–154, doi : 10.1016/0022-0000(79)90044-8 , MR  0532173.
• Lemire, Daniel (2012), "La universalidad del hash iterado sobre cadenas de longitud variable", Discrete Applied Mathematics , 160 : 604–617, arXiv : 1008.1715 , doi : 10.1016/j.dam.2011.11.009, MR  2876344.
• Pagh, Anna; Pagh, Rasmus ; Ružić, Milan (2009), "Sondaje lineal con independencia constante", SIAM Journal on Computing , 39 (3): 1107–1120, arXiv : cs/0612055 , doi :10.1137/070702278, MR  2538852.
• Pătraşcu, Mihai ; Thorup, Mikkel (2010), "Sobre la independencia k requerida por el sondeo lineal y la independencia minwise" (PDF) , Actas del 37.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2010), Burdeos, Francia, 6-10 de julio de 2010, Parte I , Lecture Notes in Computer Science , vol. 6198, Springer, págs. 715–726, arXiv : 1302.5127 , doi :10.1007/978-3-642-14165-2_60, MR  2734626.
• Pătraşcu, Mihai ; Thorup, Mikkel (2012), "El poder del hash de tabulación simple", Journal of the ACM , 59 (3): Art. 14, arXiv : 1011.5200 , doi :10.1145/2220357.2220361, MR  2946218.
• Siegel, Alan (2004), "Sobre clases universales de funciones hash de tiempo constante extremadamente aleatorias", SIAM Journal on Computing , 33 (3): 505–543, doi :10.1137/S0097539701386216, MR  2066640.
• Thorup, M. (2013), "Tabulación simple, expansores rápidos, doble tabulación y alta independencia", Actas del 54.° Simposio anual IEEE sobre fundamentos de la informática (FOCS 2013) , págs. 90-99, arXiv : 1311.3121 , doi : 10.1109/FOCS.2013.18, MR  3246210.
• Wegman, Mark N .; Carter, J. Lawrence (1981), "Nuevas funciones hash y su uso en autenticación e igualdad de conjuntos", Journal of Computer and System Sciences , 22 (3): 265–279, doi :10.1016/0022-0000(81)90033-7, MR  0633535.
• Zobrist, Albert L. (abril de 1970), Un nuevo método de hash con aplicación para juegos (PDF) , Tech. Rep. 88, Madison, Wisconsin: Departamento de Ciencias Informáticas, Universidad de Wisconsin.