Hash universal

Técnica para seleccionar funciones hash

En matemáticas y computación , el hash universal (en un algoritmo o estructura de datos aleatorios ) se refiere a seleccionar una función hash al azar de una familia de funciones hash con una determinada propiedad matemática (consulte la definición a continuación). Esto garantiza un número bajo de colisiones en expectativa , incluso si los datos son elegidos por un adversario. Se conocen muchas familias universales (para 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

Ver también: función hash

Supongamos que queremos mapear claves de algún universo en contenedores (etiquetados ). 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 esa tierra en el mismo contenedor). Una función hash determinista no puede ofrecer ninguna garantía en un entorno adversario si el tamaño de es mayor que , 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 repetir el hash.${\displaystyle U}$${\displaystyle m}$${\displaystyle [m]=\{0,\dots ,m-1\}}$${\displaystyle S\subseteq U}$${\displaystyle |S|=n}$${\displaystyle S}$${\displaystyle U}$${\displaystyle m\cdot n}$${\displaystyle S}$: 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 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:~~\Pr _{h\in H}[h(x)=h(y)]\leq {\frac {1}{m}}}$

En otras palabras, dos claves cualesquiera del universo chocan con la probabilidad como máximo cuando la función hash se extrae al azar . Esta es exactamente la probabilidad de colisión que esperaríamos si la función hash asignara códigos hash verdaderamente aleatorios a cada tecla. A veces, la definición se relaja para permitir la probabilidad de colisión . Este concepto fue introducido por Carter y Wegman ^[1] en 1977, y ha encontrado numerosas aplicaciones en la informática (ver, por ejemplo, ^[2] ). Si tenemos un límite superior de la probabilidad de colisión, decimos que tenemos casi universalidad.${\displaystyle 1/m}$${\displaystyle h}$${\displaystyle H}$${\displaystyle O(1/m)}$${\displaystyle \epsilon <1}$${\displaystyle \epsilon }$

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 al azar 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 refiere a 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 o exclusiva a nivel de bits. 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 la voluntad de hash para cualquier par de valores de hash es como si fueran perfectamente al azar: . 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, una fuerte universalidad 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 por pares independiente o fuertemente universal agregando una constante aleatoria distribuida uniformemente con valores en las funciones hash. (De manera similar, si es una potencia de dos, podemos lograr la independencia por pares de una familia hash universal XOR haciendo una constante aleatoria exclusiva o distribuida uniformemente). Dado que un cambio por una constante a veces es irrelevante en aplicaciones (por ejemplo, tablas hash) , a veces no se hace una distinción cuidadosa entre la propiedad de distancia uniforme e independiente 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 hecha de funciones para todos también es fuertemente universal para . Desafortunadamente, no ocurre lo mismo con las familias (meramente) universales. Por ejemplo, la familia hecha de la función de identidad es claramente universal, pero la familia hecha de la función deja de ser 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 y 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 hash universal. En tales aplicaciones, normalmente el software elige una nueva función hash sólo después de notar que han colisionado "demasiadas" teclas; hasta entonces, la misma función hash se sigue utilizando una y otra vez. (Algunos esquemas de resolución de colisiones, como el hash dinámico perfecto , eligen una nueva función hash cada vez que hay una colisión. Otros esquemas de resolución de colisiones, como el hash de cuco y el hash de 2 opciones , permiten varias colisiones antes de elegir una nueva función de 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. ^[6]

Garantías matemáticas

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

1. Para cualquier fijado en el número esperado de teclas en el cubo es . Cuando se implementan 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 la que chocan ( ) está acotado superiormente por , que es de orden . Cuando el número de bins, se elige lineal en (es decir, está determinado por una función en ), el número esperado de colisiones es . Al hacer 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 bins con al menos claves en ellos está delimitado por encima de . ^[7] Por lo tanto, si la capacidad de cada contenedor se limita a tres veces el tamaño promedio ( ), el número total de llaves en los contenedores desbordados es como máximo . Esto solo se aplica a una familia hash cuya probabilidad de colisión está delimitada por encima de . Si se usa una definición más débil, delimitándola , este resultado ya no es cierto. ^[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 , se mantienen si el conjunto de datos es elegido por un adversario. Sin embargo, el adversario tiene que hacer esta elección antes (o independientemente de) la elección aleatoria del algoritmo de una función hash. Si el adversario puede observar la elección aleatoria del algoritmo, la aleatoriedad no sirve para nada y la situación es la misma que el hash determinista.${\displaystyle S}$

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

Construcciones

Dado que cualquier dato informático 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 ("números enteros"); vectores de longitud fija de palabras de máquina; y vectores de longitud variable ("cadenas").

Hashing enteros

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

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

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

donde se eligen aleatoriamente los números enteros modulo con . (Esta es una sola iteración de un generador congruencial lineal ).${\displaystyle a,b}$${\displaystyle p}$${\displaystyle a\neq 0}$

Para ver que es una familia universal, tenga en cuenta que solo se mantiene 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 número entero entre y . Dado que , si su diferencia es distinta de cero y tiene un módulo inverso . Resolviendo por rendimientos${\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}}}$.

Hay opciones posibles para (ya que está excluido) y, variando en el rango permitido, posibles valores distintos de cero para el lado derecho. Por 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 es 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}}}$.

Dado que es distinto de cero y se distribuye uniformemente en , se deduce que módulo también se distribuye uniformemente en . Por tanto, la distribución de es casi uniforme, hasta una diferencia de 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] lo} demuestran siempre .${\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 de la técnica para el hash de números enteros es el esquema de desplazamiento múltiple 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 asume que el número de contenedores 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 , multiplique por módulo y luego mantenga los bits de orden superior como 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}}$

y se puede implementar en lenguajes de programación similares a C mediante

${\displaystyle h_{a}(x)=}$ (size_t) (a*x) >> (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 comprender el comportamiento de la función hash, observe que, si y tiene los mismos bits 'M' de orden más alto, entonces tiene todos los 1 o todos los 0 como sus bits M de orden más alto (dependiendo de si es mayor o menor). Suponga que el bit de conjunto menos significativo de aparece en la posición . Dado que es un número entero impar aleatorio y los números enteros impares tienen inversos en el anillo , se deduce que se distribuirá uniformemente entre los enteros de -bit con el bit establecido menos significativo en la posición . Por tanto, la probabilidad de que estos bits sean todos ceros o unos es como máximo . Por otro lado, si , entonces M bits de orden superior de ${\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}}$contienen ceros y unos, 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 la probabilidad .${\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 estrecho, como se puede demostrar con el ejemplo y . Para obtener una función hash verdaderamente 'universal', se puede usar el esquema de multiplicar-agregar-turno${\displaystyle x=2^{w-M-2}}$${\displaystyle y=3x}$

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

que se puede implementar en lenguajes de programación similares a C mediante

${\displaystyle h_{a,b}(x)=}$ (size_t) (a*x+b) >> (w-M)

donde es un entero positivo impar aleatorio con y es un entero aleatorio no negativo con . Con estas opciones de y , para todos . ^[10] Esto difiere levemente pero de manera importante del error de traducción en el documento en inglés. ^[11]${\displaystyle a}$${\displaystyle a<2^{w}}$${\displaystyle b}$${\displaystyle b<2^{w-M}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle \Pr\{h_{a,b}(x)=h_{a,b}(y)\}\leq 1/m}$${\displaystyle x\not \equiv y{\pmod {2^{w}}}}$

Vectores de hash

Esta sección se ocupa del 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 se remonta a 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 de forma independiente al azar.${\displaystyle h_{i}\in H}$

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

En la práctica, si se dispone de aritmética de doble precisión, se crea una instancia con la familia de funciones hash de desplazamiento múltiple. ^[13] Inicialice la función hash con un vector de enteros impares aleatorios en 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. ^[12] Inicialice la función hash con un vector de enteros impares aleatorios en bits cada uno. La siguiente familia de hash es universal: ^[14]${\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 las operaciones de doble precisión no están disponibles, se puede interpretar la entrada como un vector de medias palabras ( enteros de -bit). Luego, el algoritmo usará multiplicaciones, donde estaba el número de medias palabras en el vector. Por lo tanto, el algoritmo se ejecuta a una "tasa" 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 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 universal basados ​​en la multiplicación. ^[15]

También es posible una fuerte universalidad a alta velocidad. ^[16] Inicialice la función hash con un vector de enteros aleatorios en bits. Calcular${\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 fuertemente universal en bits. Experimentalmente, se encontró que se ejecuta a 0.2 ciclos de CPU por byte en procesadores Intel recientes para .${\displaystyle w}$${\displaystyle w=32}$

Hashing de cadenas

Esto se refiere al hash de un vector de palabras de máquina de tamaño variable . Si la longitud de la cadena puede estar limitada por un número pequeño, es mejor usar 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 de evaluación es solo la longitud de . Siempre que 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. ^[12] Tenga en cuenta que si se permiten ceros en la cadena, entonces sería mejor agregar un carácter ficticio distinto de cero (por ejemplo, 1) a todas las cadenas antes del relleno: esto asegurará que la universalidad no se vea afectada. ^[dieciséis]${\displaystyle h(s)}$${\displaystyle s}$

Supongamos ahora que queremos hash , donde no se conoce a priori un buen límite . Una familia universal propuesta por ^[13] trata la cadena como los coeficientes de un polinomio módulo un primo grande. Si , sea ​​primo y defina:${\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 las propiedades de la aritmética modular, lo anterior se puede calcular sin producir grandes números para cadenas grandes de la siguiente manera: ^[17]

uint  hash ( String  x ,  int  a ,  int  p ) uint  h  =  INITIAL_VALUE for  ( uint  i = 0  ;  i  <  x . length  ;  ++ i ) h  =  (( h * a )  +  x [ i ])  mod  p return  h

Este hash rodante de Rabin-Karp se basa en un generador de congruencia lineal . ^{[18] El} algoritmo anterior también se conoce como función hash multiplicativa . ^[19] En la práctica, el operador mod y el parámetro p pueden evitarse 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 hya para algunas de las implementaciones populares.

Implementación	VALOR INICIAL	a
Función hash de Bernstein djb2 [20]	5381	33
STLPort 4.6.2	0	5
Función hash de Kernighan y Ritchie [21]	0	31
java.lang.String.hashCode()[22]	0	31

Considere dos cuerdas 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 un módulo de raíces , por lo que la probabilidad de colisión es como máximo . La probabilidad de colisión aleatoria lleva la probabilidad de colisión total a . Por lo tanto, si el número primo es lo suficientemente grande en comparación con la longitud de las cadenas con hash, la familia es muy cercana a 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 que se utilizan 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, se utilizan tres trucos en la práctica: ^[12]

1. Uno elige la prima para estar cerca de una potencia de dos, como una prima de Mersenne . Esto permite implementar el módulo aritmético sin división (utilizando operaciones más rápidas como sumas y cambios). Por ejemplo, en arquitecturas modernas con las que se puede trabajar , mientras que los valores de 's son de 32 bits.${\displaystyle p}$${\displaystyle p}$${\displaystyle p=2^{61}-1}$${\displaystyle x_{i}}$
2. Se puede aplicar hash vectorial a los bloques. Por ejemplo, uno aplica hash vectorial a cada bloque de 16 palabras de la cadena y aplica hash de cadena a los resultados. Dado que el hash de cadena más lento se aplica en un vector sustancialmente más pequeño, esto será esencialmente tan rápido como el hash de vector.${\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}}$

Ver también

• Hash independiente de K
• Hash rodante
• Hash de tabulación
• Independencia mínima
• Función hash unidireccional universal
• Secuencia de baja discrepancia
• Hash perfecto

Referencias

1. Carter, Larry; Wegman, Mark N. (1979). "Clases universales de funciones hash" . Revista de Ciencias de la Computación y Sistemas . 18 (2): 143-154. doi : 10.1016 / 0022-0000 (79) 90044-8 . Versión conferencia en STOC'77.
2. Miltersen, Peter Bro. "Hashing universal" (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 . Prensa de la Universidad de Cambridge. pag. 221. ISBN 0-521-47465-5.
4. David Wagner, ed. "Avances en Criptología - CRYPTO 2008" . pag. 145.
5. Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. "La función hash BLAKE" . 2014. p. 10.
6. Thorup, Mikkel (2015). "Hashing de alta velocidad para 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) . Algoritmica . 50 (4): 584–596. doi : 10.1007 / s00453-007-9036-3 .
8. Dietzfelbinger, Martin; Hagerup, Torben; Katajainen, Jyrki; Penttonen, Martti (1997). "Un algoritmo aleatorio confiable para el problema del par más cercano" (Posdata) . Revista de algoritmos . 25 (1): 19–51. doi : 10.1006 / jagm.1997.0873 . Consultado el 10 de febrero de 2011 .
9. Thorup, Mikkel . "Algoritmos de libros de texto en SODA" .
10. Woelfel, Philipp (2003). Über die Komplexität der Multiplikation in eingeschränkten Branchingprogrammmodellen (PDF) (Ph.D.). Universität Dortmund . Consultado el 18 de septiembre de 2012 .
11. Woelfel, Philipp (1999). Hashing eficiente, fuertemente universal y óptimamente universal . Fundamentos matemáticos de la informática 1999. LNCS. 1672 . págs. 262-272. doi : 10.1007 / 3-540-48340-3_24 .
12. Thorup, Mikkel (2009). Hash de cadena para palpado 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 . , sección 5.3
13. Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). Las funciones hash polinomiales son confiables (resumen extendido) . Proc. XIX Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) . págs. 235–246.
14. Negro, 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
15. Pătraşcu, Mihai ; Thorup, Mikkel (2011). El poder del hash de tabulación simple . Actas del 43º Simposio anual de ACM sobre teoría de la computación (STOC '11) . págs. 1-10. arXiv : 1011.5200 . doi : 10.1145 / 1993636.1993638 .
16. Kaser, Owen; Lemire, Daniel (2013). "El hash de cadena fuertemente universal es rápido". Revista informática . Prensa de la Universidad de Oxford. 57 (11): 1624–1638. arXiv : 1202.4961 . doi : 10.1093 / comjnl / bxt070 .
17. "Diapositivas del curso de la Universidad Hebrea" (PDF) .
18. Robert Uzgalis. "Funciones de biblioteca hash" . 1996.
19. Kankowsk, Peter. "Funciones hash: una comparación empírica" .
20. Yigit, Ozan. "Funciones hash de cadenas" .
21. Kernighan; Ritchie (1988). "6". El lenguaje de programación C (2ª ed.). págs.  118 . ISBN 0-13-110362-8.
22. "Cadena (Java Platform SE 6)" . docs.oracle.com . Consultado el 10 de junio de 2015 .

Otras lecturas

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

enlaces externos

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