En informática , se dice que una familia de funciones hash es k -independiente , k -wise independiente o k -universal [1] si la selección de una función al azar de la familia garantiza que los códigos hash de cualquier clave k designada sean aleatorios independientes variables (consulte las definiciones matemáticas precisas a continuación). Estas familias permiten un buen desempeño promedio de casos en algoritmos o estructuras de datos aleatorizados, incluso si los datos de entrada los elige un adversario. Las compensaciones entre el grado de independencia y la eficiencia de evaluar la función hash están bien estudiadas, y muchos k-Se han propuesto familias independientes.
Fondo
El objetivo del hash es normalmente asignar claves de algún dominio grande (universo) en un rango más pequeño, como contenedores (etiquetados ). En el análisis de estructuras de datos y algoritmos aleatorizados, a menudo es deseable que los códigos hash de varias claves se "comporten de forma aleatoria". Por ejemplo, si el código hash de cada clave fuera una elección aleatoria independiente en, el número de llaves por contenedor podría analizarse utilizando el límite de Chernoff . Una función hash determinista no puede ofrecer ninguna garantía de este tipo en un entorno adversario, ya que el adversario puede elegir las claves para que sean precisamente la preimagen de un contenedor. Además, una función hash determinista no permite la repetición : a veces los datos de entrada resultan ser malos para la función hash (por ejemplo, hay demasiadas colisiones), por lo que a uno le gustaría cambiar la función hash.
La solución a estos problemas es elegir una función al azar de una gran familia de funciones hash. La aleatoriedad en la elección de la función hash se puede utilizar para garantizar un comportamiento aleatorio deseado de los códigos hash de cualquier clave de interés. La primera definición en este sentido fue el hash universal , que garantiza una baja probabilidad de colisión para dos claves designadas. El concepto de-Hashing independiente, introducido por Wegman y Carter en 1981, [2] refuerza las garantías de comportamiento aleatorio para las familias de claves designadas, y agrega una garantía sobre la distribución uniforme de códigos hash.
Definiciones
La definición más estricta, introducida por Wegman y Carter [2] bajo el nombre "fuertemente universal hash family ", es la siguiente. Una familia de funciones hash es -independiente si para alguno claves distintas y cualquier códigos hash (no necesariamente distintos) , tenemos:
Esta definición es equivalente a las siguientes dos condiciones:
- para cualquier fijo , como se extrae al azar de , se distribuye uniformemente en .
- para cualquier clave fija y distinta , como se extrae al azar de , son variables aleatorias independientes.
A menudo es inconveniente lograr la probabilidad conjunta perfecta de debido a problemas de redondeo. A continuación, [3] se puede definir un-familia independiente para satisfacer:
- distinto y ,
Observa eso, incluso si está cerca de 1, ya no son variables aleatorias independientes, lo que a menudo es un problema en el análisis de algoritmos aleatorizados. Por lo tanto, una alternativa más común para lidiar con problemas de redondeo es demostrar que la familia hash está cerca en distancia estadística de un-familia independiente, que permite el uso de caja negra de las propiedades de independencia.
Técnicas
Polinomios con coeficientes aleatorios
La técnica original para construir funciones hash independientes de k , dada por Carter y Wegman, era seleccionar un número primo grande p , elegir k números aleatorios módulo p , y usar estos números como coeficientes de un polinomio de grado k - 1 cuyos valores módulo p se utilizan como el valor de la función hash. Todos los polinomios del grado dado módulo p son igualmente probables, y cualquier polinomio está determinado de manera única por cualquier k -tupla de pares argumento-valor con argumentos distintos, de lo cual se sigue que cualquier k -tupla de argumentos distintos tiene la misma probabilidad de ser mapeada a cualquier k -tupla de valores hash. [2]
En general, el polinomio se puede evaluar en cualquier campo finito . Además de los campos módulo principal, una opción popular es el campo de tamaño, que admite aritmética rápida de campos finitos en computadoras modernas. Este fue el enfoque adoptado por Daniel Lemire y Owen Kaser para CLHash [4] .
Hash de tabulación
El hash de tabulación es una técnica para asignar claves a valores hash dividiendo cada clave en bytes , usando cada byte como índice en una tabla de números aleatorios (con una tabla diferente para cada posición de byte) y combinando los resultados de estas búsquedas de tablas por una operación o exclusiva bit a bit . Por lo tanto, requiere más aleatoriedad en su inicialización que el método polinomial, pero evita operaciones de multiplicación posiblemente lentas. Es 3-independiente pero no 4-independiente. [5] Las variaciones del hash de tabulación pueden lograr mayores grados de independencia al realizar búsquedas de tablas basadas en combinaciones superpuestas de bits de la clave de entrada, o al aplicar un hash de tabulación simple de forma iterativa. [6] [7]
Independencia necesaria para diferentes tipos de resolución de colisiones
La noción de k -independencia se puede utilizar para diferenciar entre diferentes resoluciones de colisiones en tablas hash, de acuerdo con el nivel de independencia requerido para garantizar un tiempo esperado constante por operación.
Por ejemplo, el encadenamiento de hash toma un tiempo esperado constante incluso con una función hash independiente de 2 , porque el tiempo esperado para realizar una búsqueda de una clave dada está limitado por el número esperado de colisiones en las que está involucrada la clave. Por linealidad de expectativa, esto El número esperado es igual a la suma, sobre todas las demás claves en la tabla hash, de la probabilidad de que la clave dada y la otra clave colisionen. Debido a que los términos de esta suma solo involucran eventos probabilísticos que involucran dos claves, la independencia 2 es suficiente para asegurar que esta suma tenga el mismo valor que tendría para una función hash verdaderamente aleatoria. [2]
El hash doble es otro método de hash que requiere un bajo grado de independencia. Es una forma de direccionamiento abierto que utiliza dos funciones hash: una para determinar el inicio de una secuencia de la sonda y la otra para determinar el tamaño del paso entre posiciones en la secuencia de la sonda. Siempre que ambos sean independientes de 2, este método proporciona un tiempo esperado constante por operación. [8]
Por otro lado, el sondeo lineal , una forma más simple de direccionamiento abierto donde el tamaño de paso es siempre uno, requiere independencia de 5 . Se puede garantizar que funcione en un tiempo esperado constante por operación con una función hash independiente de 5, [9] y existen funciones hash independientes de 4 para las cuales toma un tiempo logarítmico por operación. [10]
Para el hash de Cuckoo, la independencia k requerida no se conoce a partir de 2021. En 2009 se demostró [11] que-La independencia es suficiente y se necesita al menos 6-independencia . Otro enfoque es utilizar el hash de tabulación , que no es independiente de 6, pero se demostró en 2012 [12] que tiene otras propiedades suficientes para el hash de Cuckoo. Un tercer enfoque de 2014 [13] es modificar ligeramente la tabla hash de cuco con un llamado alijo, que hace posible utilizar nada más que 2 funciones hash independientes.
Otras aplicaciones
Kane , Nelson y Woodruff mejoraron el algoritmo Flajolet-Martin para el problema de elementos distintos en 2010 [14] . Para dar un aproximación a la respuesta correcta, necesitan una -función hash independiente .
El algoritmo Count sketch para la reducción de dimensionalidad requiere dos funciones hash, una independiente de 2 y una independiente de 4 .
El algoritmo de Karloff-Zwick para el problema MAX-3SAT se puede implementar con 3 variables aleatorias independientes .
Referencias
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.
- ^ a b c d Wegman, Mark N .; Carter, J. Lawrence (1981). "Nuevas funciones hash y su uso en autenticación e igualdad de conjuntos" (PDF) . Revista de Ciencias de la Computación y Sistemas . 22 (3): 265-279. doi : 10.1016 / 0022-0000 (81) 90033-7 . Versión conferencia en FOCS'79 . Consultado el 9 de febrero de 2011 .
- ^ Siegel, Alan (2004). "Sobre clases universales de funciones hash de tiempo constante extremadamente aleatorias y su compensación espacio-temporal" (PDF) . Revista SIAM de Computación . 33 (3): 505–543. doi : 10.1137 / S0097539701386216 . Versión conferencia en FOCS'89.
- ^ Lemire, Daniel y Owen Kaser. "Hash universal de 64 bits más rápido utilizando multiplicaciones sin acarreo". Revista de ingeniería criptográfica 6.3 (2016): 171-185.
- ^ Pătraşcu, Mihai ; Thorup, Mikkel (2012), "El poder del hash de tabulación simple", Revista de la ACM , 59 (3): Art. 14, arXiv : 1011.5200 , doi : 10.1145 / 2,220,357.2220361 , MR 2946218
- ^ Siegel, Alan (2004), "Sobre clases universales de funciones hash de tiempo constante extremadamente aleatorias" (PDF) , SIAM Journal on Computing , 33 (3): 505–543, doi : 10.1137 / S0097539701386216 , MR 2066640 , archivado desde el original (PDF) en 2019-02-17
- ^ Thorup, M. (2013), "Tabulación simple, expansores rápidos, doble tabulación y alta independencia", Actas del 54º Simposio Anual de IEEE sobre Fundamentos de la Ciencia de la Computación (FOCS 2013) , págs. 90–99, arXiv : 1311.3121 , doi : 10.1109 / FOCS.2013.18 , ISBN 978-0-7695-5135-7, MR 3246210
- ^ Bradford, Phillip G .; Katehakis, Michael N. (2007), "Un estudio probabilístico sobre expansores combinatorios y hash" (PDF) , SIAM Journal on Computing , 37 (1): 83-111, doi : 10.1137 / S009753970444630X , MR 2306284 , archivado del original (PDF) el 25 de enero de 2016 , consultado el 19 de enero de 2016
- ^ Pagh, Anna; Pagh, Rasmus ; Ružić, Milán (2009), "Sondeo 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 k -independencia requerida por el sondeo lineal y la independencia mínima" (PDF) , Autómatas, lenguajes y programación, 37 ° Coloquio Internacional, ICALP 2010, Burdeos, Francia, 6 al 10 de julio de 2010, Actas , Parte I , Lecture Notes in Computer Science , 6198 , Springer, págs. 715–726, arXiv : 1302.5127 , doi : 10.1007 / 978-3-642-14165-2_60 , ISBN 978-3-642-14164-5
- ^ Cohen, Jeffrey S. y Daniel M. Kane. "Limita la independencia requerida para el hash de cuco". Transacciones ACM sobre algoritmos (2009).
- ^ Pǎtraşcu, Mihai y Mikkel Thorup. "El poder del simple hash de tabulación". Revista de la ACM (JACM) 59.3 (2012): 1-50.
- ^ Aumüller, Martin, Martin Dietzfelbinger y Philipp Woelfel. "Las familias de hachís explícitas y eficientes son suficientes para el hash de cuco con un alijo". Algorithmica 70.3 (2014): 428-456.
- ^ Kane, Daniel M., Jelani Nelson y David P. Woodruff. "Un algoritmo óptimo para el problema de los distintos elementos". Actas del vigésimo noveno simposio ACM SIGMOD-SIGACT-SIGART sobre Principios de los sistemas de bases de datos. 2010.
Otras lecturas
- Motwani, Rajeev; Raghavan, Prabhakar (1995). Algoritmos aleatorios . Prensa de la Universidad de Cambridge. pag. 221 . ISBN 978-0-521-47465-8.