Hashing universal

Técnica para seleccionar funciones hash

En matemáticas e informática , el hash universal (en un algoritmo aleatorio o una estructura de datos) se refiere a la selección aleatoria de una función hash de una familia de funciones hash con una determinada propiedad matemática (véase la definición a continuación). Esto garantiza un bajo número de colisiones en expectativa , incluso si los datos son elegidos por un adversario. Se conocen muchas familias universales (para el hash de números enteros, vectores, cadenas), y su evaluación suele ser muy eficiente. El hash universal tiene numerosos usos en informática, por ejemplo en implementaciones de tablas hash , algoritmos aleatorios y criptografía .

Introducción

Supongamos que queremos mapear claves de algún universo en contenedores (etiquetados como ). El algoritmo tendrá que manejar algún conjunto de datos de claves, que no se conoce de antemano. Por lo general, el objetivo del hash es obtener un número bajo de colisiones (claves de ese universo que caen en el mismo contenedor). Una función hash determinista no puede ofrecer ninguna garantía en un entorno adversario si , ya que el adversario puede elegir ser precisamente la preimagen de un contenedor. Esto significa que todas las claves de datos caen en el mismo contenedor, lo que hace que el hash sea inútil. Además, una función hash determinista no permite el rehashing : a veces los datos de entrada resultan ser malos para la función hash (por ejemplo, hay demasiadas colisiones), por lo que uno querría cambiar la función hash. ${\displaystyle U}$ ${\displaystyle m}$ ${\displaystyle [m]=\{0,\dots ,m-1\}}$ ${\displaystyle S\subseteq U}$ ${\displaystyle |S|=n}$ ${\displaystyle S}$ ${\displaystyle |U|>m\cdot n}$ ${\displaystyle S}$

La solución a estos problemas es elegir una función al azar de una familia de funciones hash. Una familia de funciones se denomina familia universal si, . ${\displaystyle H=\{h:U\to [m]\}}$ ${\displaystyle \forall x,y\in U,~x\neq y:~~|\{h\in H:h(x)=h(y)\}|\leq {\frac {|H|}{m}}}$

En otras palabras, dos claves diferentes cualesquiera del universo colisionan con una probabilidad máxima cuando la función hash se extrae de manera uniforme y aleatoria de . Esta es exactamente la probabilidad de colisión que esperaríamos si la función hash asignara códigos hash verdaderamente aleatorios a cada clave. ${\displaystyle 1/m}$ ${\displaystyle h}$ ${\displaystyle H}$

A veces, la definición se relaja mediante un factor constante, y solo se requiere la probabilidad de colisión en lugar de . Este concepto fue introducido por Carter y Wegman ^[1] en 1977 y ha encontrado numerosas aplicaciones en informática (véase, por ejemplo , ^[2] ) . ${\displaystyle O(1/m)}$ ${\displaystyle \leq 1/m}$

Si tenemos un límite superior para la probabilidad de colisión, decimos que tenemos casi universalidad. Por ejemplo, una familia universal tiene casi universalidad. ${\displaystyle \epsilon <1}$ ${\displaystyle \epsilon }$ ${\displaystyle 1/m}$

Muchas familias universales, pero no todas, tienen la siguiente propiedad de diferencia uniforme más fuerte :

${\displaystyle \forall x,y\in U,~x\neq y}$, cuando se extrae aleatoriamente de la familia , la diferencia se distribuye uniformemente en . ${\displaystyle h}$ ${\displaystyle H}$ ${\displaystyle h(x)-h(y)~{\bmod {~}}m}$ ${\displaystyle [m]}$

Tenga en cuenta que la definición de universalidad solo se ocupa de si , lo que cuenta las colisiones. La propiedad de diferencia uniforme es más fuerte. ${\displaystyle h(x)-h(y)=0}$

(De manera similar, una familia universal puede ser XOR universal si , el valor se distribuye uniformemente en donde es la operación exclusiva bit a bit o . Esto solo es posible si es una potencia de dos). ${\displaystyle \forall x,y\in U,~x\neq y}$ ${\displaystyle h(x)\oplus h(y)~{\bmod {~}}m}$ ${\displaystyle [m]}$ ${\displaystyle \oplus }$ ${\displaystyle m}$

Una condición aún más fuerte es la independencia por pares : tenemos esta propiedad cuando tenemos la probabilidad de que el hash de cualquier par de valores hash sea como si fueran perfectamente aleatorios: . La independencia por pares a veces se denomina universalidad fuerte. ${\displaystyle \forall x,y\in U,~x\neq y}$ ${\displaystyle x,y}$ ${\displaystyle z_{1},z_{2}}$ ${\displaystyle P(h(x)=z_{1}\land h(y)=z_{2})=1/m^{2}}$

Otra propiedad es la uniformidad. Decimos que una familia es uniforme si todos los valores hash son igualmente probables: para cualquier valor hash . La universalidad no implica uniformidad. Sin embargo, la universalidad fuerte sí implica uniformidad. ${\displaystyle P(h(x)=z)=1/m}$ ${\displaystyle z}$

Dada una familia con la propiedad de distancia uniforme, se puede producir una familia hash independiente por pares o fuertemente universal agregando una constante aleatoria uniformemente distribuida con valores en a las funciones hash. (De manera similar, si es una potencia de dos, podemos lograr independencia por pares de una familia hash universal XOR haciendo un o exclusivo con una constante aleatoria uniformemente distribuida). Dado que un cambio por una constante a veces es irrelevante en las aplicaciones (por ejemplo, tablas hash), a veces no se hace una distinción cuidadosa entre la propiedad de distancia uniforme y la independencia por pares. ^[3] ${\displaystyle [m]}$ ${\displaystyle m}$

Para algunas aplicaciones (como las tablas hash), es importante que los bits menos significativos de los valores hash también sean universales. Cuando una familia es fuertemente universal, esto está garantizado: si es una familia fuertemente universal con , entonces la familia formada por las funciones para todos también es fuertemente universal para . Desafortunadamente, no sucede lo mismo con las familias (simplemente) universales. Por ejemplo, la familia formada por la función identidad es claramente universal, pero la familia formada por la función no es universal. ${\displaystyle H}$ ${\displaystyle m=2^{L}}$ ${\displaystyle h{\bmod {2^{L'}}}}$ ${\displaystyle h\in H}$ ${\displaystyle L'\leq L}$ ${\displaystyle h(x)=x}$ ${\displaystyle h(x)=x{\bmod {2^{L'}}}}$

UMAC , Poly1305-AES y varios otros algoritmos de código de autenticación de mensajes se basan en hash universal. ^{[4] [5]} En tales aplicaciones, el software elige una nueva función hash para cada mensaje, basándose en un nonce único para ese mensaje.

Varias implementaciones de tablas hash se basan en el hash universal. En tales aplicaciones, normalmente el software elige una nueva función hash solo después de notar que han colisionado "demasiadas" claves; hasta entonces, la misma función hash continúa usándose una y otra vez. (Algunos esquemas de resolución de colisiones, como el hash perfecto dinámico , eligen una nueva función hash cada vez que hay una colisión. Otros esquemas de resolución de colisiones, como el hash cuckoo y el hash de 2 opciones , permiten una serie de colisiones antes de elegir una nueva función hash). En ^[6] se encuentra un estudio de las funciones hash universales y fuertemente universales más rápidas conocidas para números enteros, vectores y cadenas.

Garantías matemáticas

Para cualquier conjunto fijo de claves, el uso de una familia universal garantiza las siguientes propiedades. ${\displaystyle S}$ ${\displaystyle n}$

1. Para cualquier valor fijo en , el número esperado de claves en el contenedor es . Al implementar tablas hash mediante encadenamiento , este número es proporcional al tiempo de ejecución esperado de una operación que involucra la clave (por ejemplo, una consulta, inserción o eliminación). ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle h(x)}$ ${\displaystyle n/m}$ ${\displaystyle x}$
2. El número esperado de pares de claves en con que colisionan ( ) está limitado por encima de , que es de orden . Cuando el número de contenedores, se elige lineal en (es decir, está determinado por una función en ), el número esperado de colisiones es . Cuando se realiza el hash en contenedores, no hay colisiones en absoluto con una probabilidad de al menos la mitad. ${\displaystyle x,y}$ ${\displaystyle S}$ ${\displaystyle x\neq y}$ ${\displaystyle h(x)=h(y)}$ ${\displaystyle n(n-1)/2m}$ ${\displaystyle O(n^{2}/m)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \Omega (n)}$ ${\displaystyle O(n)}$ ${\displaystyle n^{2}}$
3. El número esperado de claves en contenedores con al menos claves en ellos está limitado por encima de . ^[7] Por lo tanto, si la capacidad de cada contenedor está limitada a tres veces el tamaño promedio ( ), el número total de claves en contenedores desbordados es como máximo . Esto solo se cumple con una familia hash cuya probabilidad de colisión está limitada por encima de . Si se utiliza una definición más débil, limitándola por , este resultado ya no es verdadero. ^[7] ${\displaystyle t}$ ${\displaystyle 2n/(t-2(n/m)+1)}$ ${\displaystyle t=3n/m}$ ${\displaystyle O(m)}$ ${\displaystyle 1/m}$ ${\displaystyle O(1/m)}$

Como las garantías anteriores son válidas para cualquier conjunto fijo , también lo son si el adversario elige el conjunto de datos. Sin embargo, el adversario tiene que hacer esta elección antes (o independientemente) de la elección aleatoria de una función hash por parte del algoritmo. Si el adversario puede observar la elección aleatoria del algoritmo, la aleatoriedad no sirve de nada y la situación es la misma que la del hash determinista. ${\displaystyle S}$

La segunda y tercera garantías se utilizan normalmente junto con el refrito . Por ejemplo, se puede preparar un algoritmo aleatorio para manejar cierta cantidad de colisiones. Si observa demasiadas colisiones, elige otro valor aleatorio de la familia y repite. La universalidad garantiza que la cantidad de repeticiones sea una variable aleatoria geométrica . ${\displaystyle O(n)}$ ${\displaystyle h}$

Construcciones

Dado que cualquier dato de computadora puede representarse como una o más palabras de máquina, generalmente se necesitan funciones hash para tres tipos de dominios: palabras de máquina ("enteros"); vectores de palabras de máquina de longitud fija; y vectores de longitud variable ("cadenas").

Hashing de números enteros

Esta sección se refiere al caso de la conversión de números enteros en hashes que caben en palabras de máquina; por lo tanto, operaciones como multiplicación, suma, división, etc. son instrucciones baratas de nivel de máquina. Sea . ${\displaystyle \{0,\dots ,|U|-1\}}$

La propuesta original de Carter y Wegman ^[1] fue elegir un primo y definir ${\displaystyle p\geq |U|}$

${\displaystyle h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}m}$

donde son números enteros elegidos aleatoriamente módulo con . (Esta es una única iteración de un generador congruencial lineal .) ${\displaystyle a,b}$ ${\displaystyle p}$ ${\displaystyle a\neq 0}$

Para ver que es una familia universal, nótese que sólo se cumple cuando ${\displaystyle H=\{h_{a,b}\}}$ ${\displaystyle h(x)=h(y)}$

${\displaystyle ax+b\equiv ay+b+i\cdot m{\pmod {p}}}$

para algún entero entre y . Dado que , si su diferencia es distinta de cero y tiene un módulo inverso . Resolviendo para se obtiene ${\displaystyle i}$ ${\displaystyle 0}$ ${\displaystyle (p-1)/m}$ ${\displaystyle p\geq |U|}$ ${\displaystyle x\neq y}$ ${\displaystyle x-y}$ ${\displaystyle p}$ ${\displaystyle a}$

${\displaystyle a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}}$.

Existen opciones posibles para (ya que se excluye) y, que varían dentro del rango permitido, posibles valores distintos de cero para el lado derecho. Por lo tanto, la probabilidad de colisión es ${\displaystyle p-1}$ ${\displaystyle a}$ ${\displaystyle a=0}$ ${\displaystyle i}$ ${\displaystyle \lfloor (p-1)/m\rfloor }$

${\displaystyle \lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m}$.

Otra forma de ver una familia universal es a través de la noción de distancia estadística . Escribe la diferencia como ${\displaystyle H}$ ${\displaystyle h(x)-h(y)}$

${\displaystyle h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}}$.

Como es distinto de cero y se distribuye uniformemente en , se deduce que módulo también se distribuye uniformemente en . La distribución de es, por tanto, casi uniforme, hasta una diferencia en la probabilidad de entre las muestras. Como resultado, la distancia estadística a una familia uniforme es , que se vuelve insignificante cuando . ${\displaystyle x-y}$ ${\displaystyle a}$ ${\displaystyle \{1,\dots ,p-1\}}$ ${\displaystyle a(x-y)}$ ${\displaystyle p}$ ${\displaystyle \{1,\dots ,p-1\}}$ ${\displaystyle (h(x)-h(y))~{\bmod {~}}m}$ ${\displaystyle \pm 1/p}$ ${\displaystyle O(m/p)}$ ${\displaystyle p\gg m}$

La familia de funciones hash más simples

${\displaystyle h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m}$

es sólo aproximadamente universal: para todos . ^[1] Además, este análisis es casi estricto; Carter y Wegman ^[1] muestran que siempre que . ${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$ ${\displaystyle x\neq y}$ ${\displaystyle \Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m+1)}$ ${\displaystyle (p-1)~{\bmod {~}}m=1}$

Evitar la aritmética modular

El estado del arte para el hash de números enteros es el esquema de multiplicación por desplazamiento descrito por Dietzfelbinger et al. en 1997. ^[8] Al evitar la aritmética modular, este método es mucho más fácil de implementar y también se ejecuta significativamente más rápido en la práctica (generalmente por al menos un factor de cuatro ^[9] ). El esquema supone que el número de bins es una potencia de dos, . Sea el número de bits en una palabra de máquina. Luego, las funciones hash se parametrizan sobre números enteros positivos impares (que caben en una palabra de bits). Para evaluar , se multiplica por módulo y luego se mantienen los bits de orden superior como el código hash. En notación matemática, esto es ${\displaystyle m=2^{M}}$ ${\displaystyle w}$ ${\displaystyle a<2^{w}}$ ${\displaystyle w}$ ${\displaystyle h_{a}(x)}$ ${\displaystyle x}$ ${\displaystyle a}$ ${\displaystyle 2^{w}}$ ${\displaystyle M}$

${\displaystyle h_{a}(x)=(a\cdot x\,\,{\bmod {\,}}2^{w})\,\,\mathrm {div} \,\,2^{w-M}.}$

Este esquema no satisface la propiedad de diferencia uniforme y es sólo -casi-universal ; para cualquier , . ${\displaystyle 2/m}$ ${\displaystyle x\neq y}$ ${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$

Para entender el comportamiento de la función hash, observe que, si y tienen los mismos bits 'M' de orden más alto, entonces tiene todos 1 o todos 0 como sus M bits de orden más alto (dependiendo de si o es mayor). Suponga que el bit menos significativo del conjunto de aparece en la posición . Dado que es un entero impar aleatorio y los enteros impares tienen inversos en el anillo , se deduce que se distribuirá uniformemente entre los enteros de -bit con el bit menos significativo del conjunto en la posición . La probabilidad de que estos bits sean todos 0 o todos 1 es, por lo tanto, como máximo . Por otro lado, si , entonces los M bits de orden superior de contienen tanto 0 como 1, por lo que es seguro que . Finalmente, si entonces el bit de es 1 y si y solo si los bits también son 1, lo que sucede con probabilidad . ${\displaystyle ax{\bmod {2}}^{w}}$ ${\displaystyle ay{\bmod {2}}^{w}}$ ${\displaystyle a(x-y){\bmod {2}}^{w}}$ ${\displaystyle ax{\bmod {2}}^{w}}$ ${\displaystyle ay{\bmod {2}}^{w}}$ ${\displaystyle x-y}$ ${\displaystyle w-c}$ ${\displaystyle a}$ ${\displaystyle Z_{2^{w}}}$ ${\displaystyle a(x-y){\bmod {2}}^{w}}$ ${\displaystyle w}$ ${\displaystyle w-c}$ ${\displaystyle 2/2^{M}=2/m}$ ${\displaystyle c<M}$ ${\displaystyle a(x-y){\bmod {2}}^{w}}$ ${\displaystyle h(x)\neq h(y)}$ ${\displaystyle c=M}$ ${\displaystyle w-M}$ ${\displaystyle a(x-y){\bmod {2}}^{w}}$ ${\displaystyle h_{a}(x)=h_{a}(y)}$ ${\displaystyle w-1,\ldots ,w-M+1}$ ${\displaystyle 1/2^{M-1}=2/m}$

Este análisis es estricto, como se puede demostrar con el ejemplo y . Para obtener una función hash verdaderamente "universal", se puede utilizar el esquema de multiplicación-suma-desplazamiento que selecciona bits de orden superior. ${\displaystyle x=2^{w-M-2}}$ ${\displaystyle y=3x}$

${\displaystyle h_{a,b}(x)=((ax+b){\bmod {2}}^{w+M})\,\mathrm {div} \,2^{w},}$

donde es un entero positivo aleatorio con y es un entero no negativo aleatorio con . Esto requiere realizar operaciones aritméticas en enteros sin signo de -bit. Esta versión de multiplicación por desplazamiento se debe a Dietzfelbinger y luego fue analizada con mayor precisión por Woelfel. ^[10] ${\displaystyle a}$ ${\displaystyle a<2^{2w}}$ ${\displaystyle b}$ ${\displaystyle b<2^{2w}}$ ${\displaystyle 2w}$

Vectores de hash

Esta sección se ocupa de la función hash de un vector de longitud fija de palabras de máquina. Interprete la entrada como un vector de palabras de máquina (números enteros de bits cada uno). Si es una familia universal con la propiedad de diferencia uniforme, la siguiente familia (que data de Carter y Wegman ^[1] ) también tiene la propiedad de diferencia uniforme (y, por lo tanto, es universal): ${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{k-1})}$ ${\displaystyle k}$ ${\displaystyle w}$ ${\displaystyle H}$

${\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m}$, donde cada uno se elige independientemente al azar. ${\displaystyle h_{i}\in H}$

Si es una potencia de dos, se puede reemplazar la suma por o exclusiva. ^[11] ${\displaystyle m}$

En la práctica, si se dispone de aritmética de doble precisión, esto se instancia con la familia de funciones hash de desplazamiento múltiple. ^[12] Inicialice la función hash con un vector de números enteros aleatorios impares de bits cada uno. Entonces, si el número de contenedores es para : ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$ ${\displaystyle 2w}$ ${\displaystyle m=2^{M}}$ ${\displaystyle M\leq w}$

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_{i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

Es posible reducir a la mitad el número de multiplicaciones, lo que se traduce aproximadamente en una aceleración del doble en la práctica. ^[11] Inicialice la función hash con un vector de números enteros aleatorios impares de 1000 bits cada uno. La siguiente familia hash es universal: ^[13] ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$ ${\displaystyle 2w}$

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){\Big )}{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

Si no se dispone de operaciones de doble precisión, se puede interpretar la entrada como un vector de medias palabras ( enteros de 0,016 bits). El algoritmo utilizará entonces multiplicaciones, donde era el número de medias palabras del vector. De este modo, el algoritmo se ejecuta a una "velocidad" de una multiplicación por palabra de entrada. ${\displaystyle w/2}$ ${\displaystyle \lceil k/2\rceil }$ ${\displaystyle k}$

El mismo esquema también se puede utilizar para el hash de números enteros, interpretando sus bits como vectores de bytes. En esta variante, la técnica vectorial se conoce como hash de tabulación y proporciona una alternativa práctica a los esquemas de hash universales basados ​​en la multiplicación. ^[14]

También es posible una fuerte universalidad a alta velocidad. ^[15] Inicialice la función hash con un vector de números enteros aleatorios en bits. Calcule ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k})}$ ${\displaystyle 2w}$

${\displaystyle h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}}$.

El resultado es muy universal en bits. Experimentalmente, se descubrió que funcionaba a 0,2 ciclos de CPU por byte en los procesadores Intel más recientes para . ${\displaystyle w}$ ${\displaystyle w=32}$

Cadenas de hash

Esto se refiere a la función hash de un vector de tamaño variable de palabras de máquina. Si la longitud de la cadena puede limitarse con un número pequeño, es mejor utilizar la solución vectorial de arriba (rellenando conceptualmente el vector con ceros hasta el límite superior). El espacio requerido es la longitud máxima de la cadena, pero el tiempo para evaluar es solo la longitud de . Mientras los ceros estén prohibidos en la cadena, el relleno de ceros se puede ignorar al evaluar la función hash sin afectar la universalidad. ^[11] Nótese que si se permiten ceros en la cadena, entonces podría ser mejor agregar un carácter ficticio distinto de cero (por ejemplo, 1) a todas las cadenas antes del relleno: esto garantizará que la universalidad no se vea afectada. ^[15] ${\displaystyle h(s)}$ ${\displaystyle s}$

Ahora supongamos que queremos calcular el hash de , donde no se conoce a priori un límite adecuado para . Una familia universal propuesta por ^[12] trata la cadena como los coeficientes de un polinomio módulo un primo grande. Si , sea un primo y definamos: ${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{\ell })}$ ${\displaystyle \ell }$ ${\displaystyle x}$ ${\displaystyle x_{i}\in [u]}$ ${\displaystyle p\geq \max\{u,m\}}$

${\displaystyle h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)}$, donde es uniformemente aleatorio y se elige aleatoriamente de un dominio entero de mapeo familiar universal . ${\displaystyle a\in [p]}$ ${\displaystyle h_{\mathrm {int} }}$ ${\displaystyle [p]\mapsto [m]}$

Utilizando propiedades de aritmética modular, lo anterior se puede calcular sin producir números grandes para cadenas grandes de la siguiente manera: ^[16]

uint hash ( String x , int a , int p ) uint h = VALOR_INICIAL para ( uint i = 0 ; i < x . length ; ++ i ) h = (( h * a ) + x [ i ]) mod p devuelve h                        

Este algoritmo hash de Rabin-Karp se basa en un generador congruencial lineal . ^[17] El algoritmo anterior también se conoce como función hash multiplicativa . ^[18] En la práctica, el operador mod y el parámetro p se pueden evitar por completo simplemente permitiendo que el entero se desborde porque es equivalente a mod ( Max-Int-Value + 1) en muchos lenguajes de programación. La siguiente tabla muestra los valores elegidos para inicializar h y a para algunas de las implementaciones populares.

Considere dos cadenas y sea la longitud de la más larga; para el análisis, la cadena más corta se rellena conceptualmente con ceros hasta la longitud . Una colisión antes de aplicar implica que es una raíz del polinomio con coeficientes . Este polinomio tiene como máximo raíces módulo , por lo que la probabilidad de colisión es como máximo . La probabilidad de colisión a través del azar lleva la probabilidad de colisión total a . Por lo tanto, si el primo es suficientemente grande en comparación con la longitud de las cadenas hasheadas, la familia está muy cerca de ser universal (en distancia estadística ). ${\displaystyle {\bar {x}},{\bar {y}}}$ ${\displaystyle \ell }$ ${\displaystyle \ell }$ ${\displaystyle h_{\mathrm {int} }}$ ${\displaystyle a}$ ${\displaystyle {\bar {x}}-{\bar {y}}}$ ${\displaystyle \ell }$ ${\displaystyle p}$ ${\displaystyle \ell /p}$ ${\displaystyle h_{\mathrm {int} }}$ ${\displaystyle {\frac {1}{m}}+{\frac {\ell }{p}}}$ ${\displaystyle p}$

Otras familias universales de funciones hash utilizadas para convertir cadenas de longitud desconocida en valores hash de longitud fija incluyen la huella digital de Rabin y Buzhash .

Evitar la aritmética modular

Para mitigar la penalización computacional de la aritmética modular, en la práctica se utilizan tres trucos: ^[11]

1. Se elige un número primo cercano a una potencia de dos, como un primo de Mersenne . Esto permite implementar el módulo aritmético sin división (utilizando operaciones más rápidas como la suma y los desplazamientos). Por ejemplo, en arquitecturas modernas se puede trabajar con , mientras que los son valores de 32 bits. ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p=2^{61}-1}$ ${\displaystyle x_{i}}$
2. Se puede aplicar el hash vectorial a los bloques. Por ejemplo, se aplica el hash vectorial a cada bloque de 16 palabras de la cadena y se aplica el hash de cadena a los resultados. Dado que el hash de cadena más lento se aplica a un vector sustancialmente más pequeño, esto será esencialmente tan rápido como el hash vectorial. ${\displaystyle \lceil k/16\rceil }$
3. Se elige una potencia de dos como divisor, lo que permite implementar el módulo aritmético sin división (utilizando operaciones más rápidas de enmascaramiento de bits ). La familia de funciones hash NH adopta este enfoque. ${\displaystyle 2^{w}}$

Véase también

• Hashing independiente de K  : familia de funciones hash
• Hashing continuo  : tipo de función hashPages displaying short descriptions of redirect targets
• Hashing de tabulación  : funciones hash calculadas por métodos exclusivos o
• Independencia de min-a-min  : técnica de minería de datosPages displaying short descriptions of redirect targets
• Función hash unidireccional universal  : tipo de función hash universal en criptografía propuesta como alternativa a las funciones hash resistentes a colisionesPages displaying wikidata descriptions as a fallback
• Secuencia de baja discrepancia  : tipo de secuencia matemática
• Hash perfecto  : función hash sin colisionesPages displaying short descriptions of redirect targets

Referencias

1. Carter, Larry; Wegman, Mark N. (1979). "Clases universales de funciones hash". Revista de ciencias de la computación y de sistemas . 18 (2): 143–154. doi : 10.1016/0022-0000(79)90044-8 . Versión de conferencia en STOC'77.
2. Miltersen, Peter Bro. "Universal Hashing" (PDF) . Archivado desde el original (PDF) el 24 de mayo de 2011. Consultado el 24 de junio de 2009 .
3. Motwani, Rajeev; Raghavan, Prabhakar (1995). Algoritmos aleatorios . Cambridge University Press. pág. 221. ISBN 0-521-47465-5.
4. David Wagner, ed. "Avances en criptología - CRYPTO 2008". pág. 145.
5. Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. "La función hash BLAKE". 2014. pág. 10.
6. Thorup, Mikkel (2015). "Hash de alta velocidad para números enteros y cadenas". arXiv : 1504.06804 [cs.DS].
7. Baran, Ilya; Demaine, Erik D.; Pătraşcu, Mihai (2008). "Algoritmos subcuadráticos para 3SUM" (PDF) . Algorítmica . 50 (4): 584–596. doi :10.1007/s00453-007-9036-3. S2CID  9855995.
8. Dietzfelbinger, Martin; Hagerup, Torben; Katajainen, Jyrki; Penttonen, Martti (1997). "Un algoritmo aleatorio confiable para el problema del par más cercano" (posdata) . Journal of Algorithms . 25 (1): 19–51. doi :10.1006/jagm.1997.0873 . Consultado el 10 de febrero de 2011 .
9. Thorup, Mikkel (18 de diciembre de 2009). "Algoritmos de libros de texto en SODA".
10. Woelfel, Philipp (1999). Hashing eficiente, fuertemente universal y óptimamente universal . Fundamentos matemáticos de la informática 1999. LNCS. Vol. 1672. págs. 262–272. doi :10.1007/3-540-48340-3_24.
11. Thorup, Mikkel (2009). Hashing de cadenas para sondeo lineal . Proc. 20.º Simposio ACM-SIAM sobre algoritmos discretos (SODA) . Págs. 655–664. CiteSeerX 10.1.1.215.4253 . doi :10.1137/1.9781611973068.72. ISBN .  978-0-89871-680-1., sección 5.3
12. Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). Las funciones hash polinomiales son fiables (resumen ampliado) . Proc. 19.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) . págs. 235–246.
13. Black, J.; Halevi, S.; Krawczyk, H.; Krovetz, T. (1999). UMAC: autenticación de mensajes rápida y segura (PDF) . Avances en criptología (CRYPTO '99) ., Ecuación 1
14. Pătraşcu, Mihai ; Thorup, Mikkel (2011). El poder del hash de tabulación simple . Actas del 43.° Simposio anual de la ACM sobre teoría de la computación (STOC '11) . págs. 1–10. arXiv : 1011.5200 . doi :10.1145/1993636.1993638. ISBN 9781450306911.
15. Kaser, Owen; Lemire, Daniel (2013). "El hash de cadenas fuertemente universal es rápido". Computer Journal . 57 (11). Oxford University Press: 1624–1638. arXiv : 1202.4961 . doi :10.1093/comjnl/bxt070.
16. "Diapositivas del curso de la Universidad Hebrea" (PDF) .
17. Robert Uzgalis. "Funciones hash de biblioteca". 1996.
18. Kankowsk, Peter. "Funciones hash: una comparación empírica".
19. Yigit, Ozan. "Funciones hash de cadenas".
20. Kernighan; Ritchie (1988). "6" . El lenguaje de programación C (2ª ed.). Prentice Hall. págs.118. ISBN 0-13-110362-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
21. "Cadena (Java Platform SE 6)". docs.oracle.com . Consultado el 10 de junio de 2015 .

Lectura adicional

• Knuth, Donald Ervin (1998). El arte de la programación informática, vol. III: Ordenación y búsqueda (3.ª ed.). Reading, Mass.; Londres: Addison-Wesley. ISBN 0-201-89685-0.

Enlaces externos

• Estructuras de datos abiertas - Sección 5.1.1 - Hashing multiplicativo, Pat Morin