Hashing universal

En matemáticas e informática , el hashing universal (en un algoritmo o estructura de datos aleatorios ) se refiere a la selección aleatoria de una función hash de una familia de funciones hash con una propiedad matemática determinada (véase la definición a continuación). Esto garantiza un bajo número de colisiones en promedio , incluso si los datos son elegidos por un adversario. Se conocen muchas familias universales (para el hashing de enteros, vectores y cadenas), y su evaluación suele ser muy eficiente. El hashing 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 $U$ en $m$ contenedores (etiquetados $[m]=\{0,\dots ,m-1\}$ ). El algoritmo tendrá que manejar algún conjunto de datos $S\subsetequ U$ de $|S|=n$ claves, que no se conocen de antemano. Por lo general, el objetivo del hashing es obtener un número bajo de colisiones (claves de $S$ que caen en el mismo contenedor). Una función hash determinista no puede ofrecer ninguna garantía en un entorno adversario si $|U|>m\cdot n$ , puesto que el adversario puede elegir $S$ ser precisamente la preimagen de un contenedor. Esto significa que todas las claves de datos terminan en el mismo contenedor, lo que hace que el hashing sea inútil. Además, una función hash determinista no permite el rehashing : a veces los datos de entrada resultan inadecuados para la función hash (por ejemplo, hay demasiadas colisiones), por lo que se desea cambiar la función hash.

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

En otras palabras, cualesquiera dos claves diferentes del universo chocan con una probabilidad máxima de $1/m$ cuando la función hash $h$ se extrae uniformemente al azar de $H$ Esta es exactamente la probabilidad de colisión que cabría esperar si la función hash asignara códigos hash verdaderamente aleatorios a cada clave.

A veces, la definición se relaja mediante un factor constante, requiriendo únicamente la probabilidad de colisión. $O(1/m)$ en vez de $\leq 1/m$ Este concepto fue introducido por Carter y Wegman ^{[ 1 ]} en 1977 y ha encontrado numerosas aplicaciones en la ciencia de la computación (véase, por ejemplo , ^{[ 2 ]} ) .

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

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

\forall x,y\in U,~x\neq y

, cuando

h

se extrae al azar de la familia

H

, la diferencia

h(x)-h(y)~{\bmod {~}}m

se distribuye uniformemente en

[m]

.

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

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

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

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

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 distribuida uniformemente con valores en $[m]$ a las funciones hash. (De manera similar, si $m$ es una potencia de dos, podemos lograr la independencia por pares de una familia de hash universal XOR haciendo un OR exclusivo con una constante aleatoria uniformemente distribuida. Dado que un desplazamiento 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 ]}

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 $H$ es una familia fuertemente universal con $m=2^{L}$ , entonces la familia hizo de las funciones $h{\bmod {2^{L'}}}$ a pesar de $h\in H$ También es fuertemente universal para $L'\leq L$ Desafortunadamente, lo mismo no ocurre con las familias (meramente) universales. Por ejemplo, la familia formada por la función identidad. $h(x)=x$ es claramente universal, pero la familia hizo de la función $h(x)=x{\bmod {2^{L'}}}$ No es universal.

UMAC y Poly1305-AES , así como otros algoritmos de autenticación de mensajes, se basan en el hash universal. ^{[ 4 ]}^{[ 5 ]} En estas aplicaciones, el software elige una nueva función hash para cada mensaje, basada en un nonce único para ese mensaje.

Varias implementaciones de tablas hash se basan en el hash universal. En estas aplicaciones, el software suele elegir una nueva función hash solo después de detectar que se han producido colisiones de demasiadas claves; hasta entonces, se sigue utilizando la misma función hash repetidamente. (Algunos esquemas de resolución de colisiones, como el hash perfecto dinámico , eligen una nueva función hash cada vez que se produce una colisión. Otros esquemas de resolución de colisiones, como el hash cuco y el hash de dos opciones , permiten un número determinado de colisiones antes de elegir una nueva función hash). En ^[⁶^] se encuentra un estudio de las funciones hash universales y fuertemente universales más rápidas conocidas para enteros, vectores y cadenas.

Garantías matemáticas

Para cualquier conjunto fijo $S$ de $n$ Las llaves, al utilizar una familia universal, garantizan las siguientes propiedades.

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

Dado que las garantías anteriores se mantienen para cualquier conjunto fijo $S$ Estas condiciones se cumplen si el conjunto de datos es elegido por un adversario. Sin embargo, el adversario debe realizar esta elección antes (o independientemente) de la selección aleatoria de la función hash por parte del algoritmo. Si el adversario puede observar la selección aleatoria del algoritmo, la aleatoriedad resulta inútil y la situación es la misma que en el hashing determinista.

La segunda y la tercera garantía se suelen utilizar junto con el rehashing . Por ejemplo, se puede preparar un algoritmo aleatorio para manejar algunos $O(n)$ número de colisiones. Si observa demasiadas colisiones, elige otro número aleatorio. $h$ de la familia y se repite. La universalidad garantiza que el número de repeticiones es una variable aleatoria geométrica .

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 ("enteros"); vectores de longitud fija de palabras de máquina; y vectores de longitud variable ("cadenas").

Hash de enteros

Esta sección se refiere al caso del hash de enteros que caben en palabras de máquina; por lo tanto, operaciones como la multiplicación, la suma, la división, etc., son instrucciones baratas a nivel de máquina. Sea el universo que se va a hashear. $\{0,\dots ,|U|-1\}$ y sea el rango de las funciones hash ${0,\ldots ,n-1}$ .

La propuesta original de Carter y Wegman ^{[ 1 ]} consistía en elegir un número primo. $p\geq |U|$ y definir

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

dónde $a,b$ son números enteros elegidos aleatoriamente módulo $p$ con $a\neq 0$ (Esta es una sola iteración de un generador congruencial lineal ).

Para ver eso $H=\{h_{a,b}\}$ es una familia universal, tenga en cuenta que $h(x)=h(y)$ solo se cumple cuando

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

para algún número entero $i$ entre $0$ y $(p-1)/m$ . Desde $p\geq |U|$ , si $x\neq y$ su diferencia $x-y$ es distinto de cero y tiene un módulo inverso $p$ . Resolviendo para $a$ rendimientos

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

.

Hay $p-1$ posibles opciones para $a$ (desde $a=0$ está excluido) y, variable $i$ dentro del rango permitido, $\lfloor (p-1)/m\rfloor$ posibles valores distintos de cero para el lado derecho. Por lo tanto, la probabilidad de colisión es

\lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m

.

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

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

.

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

La familia de funciones hash más simples

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

es solo aproximadamente universal: $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$ a pesar de $x\neq y$ . ^{[ 1 ]} Además, este análisis es casi exacto; Carter y Wegman ^{[ 1 ]} muestran que $\Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m+1)$ cuando sea $(p-1)~{\bmod {~}}m=1$ .

Evitar la aritmética modular

El estado del arte para el hash de enteros es el esquema de multiplicación-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, $m=2^{M}$ . Dejar $w$ sea el número de bits en una palabra de máquina. Entonces, las funciones hash se parametrizan sobre enteros positivos impares. $a<2^{w}$ (que encaja en una palabra de $w$ bits). Para evaluar $h_{a}(x)$ multiplicar $x$ por $a$ módulo $2^{w}$ y luego mantener el orden alto $M$ bits como el código hash. En notación matemática , esto es

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 solo $2/m$ -casi-universal ; para cualquier $x\neq y$ , $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$ .

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

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

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

dónde $a$ es un número entero positivo aleatorio con $a<2^{2w}$ y $b$ es un número entero no negativo aleatorio con $b<2^{2w}$ Esto requiere realizar operaciones aritméticas en $2w$ Enteros sin signo de -bits. Esta versión de multiplicación-desplazamiento se debe a Dietzfelbinger y fue analizada posteriormente con mayor precisión por Woelfel. ^{[ 10 ]}

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. ${\bar {x}}=(x_{0},\dots ,x_{k-1})$ de $k$ palabras de máquina (enteros de $w$ bits cada uno). Si $H$ 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):

h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m

, donde cada

h_{i}\in H

se elige de forma independiente y aleatoria.

Si $m$ es una potencia de dos, se puede reemplazar la suma por la disyunción exclusiva. ^{[ 11 ]}

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

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 en la práctica se traduce aproximadamente en una aceleración del doble. ^{[ 11 ]} Inicialice la función hash con un vector ${\bar {a}}=(a_{0},\dots ,a_{k-1})$ de números enteros impares aleatorios en $2w$ bits cada uno. La siguiente familia de funciones hash es universal: ^{[ 13 ]}

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 ( $w/2$ enteros de bits). El algoritmo utilizará entonces $\lceil k/2\rceil$ multiplicaciones, donde $k$ era 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.

El mismo esquema también puede utilizarse para el hash de enteros, interpretando sus bits como vectores de bytes. En esta variante, la técnica vectorial se conoce como hash por 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 ${\bar {a}}=(a_{0},\dots ,a_{k})$ de números enteros aleatorios en $2w$ bits. Calcular

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 $w$ bits. Experimentalmente, se descubrió que funciona a 0,2 ciclos de CPU por byte en procesadores Intel recientes para $w=32$ .

Hash 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 se puede limitar con un número pequeño, lo mejor es usar la solución vectorial anterior (que consiste conceptualmente en rellenar 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 $h(s)$ es solo la longitud de $s$ Siempre que los ceros estén prohibidos en la cadena, el relleno con ceros puede ignorarse al evaluar la función hash sin afectar la universalidad. ^{[ 11 ]} Tenga en cuenta 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 ]}

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

h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)

, dónde

a\in [p]

es uniformemente aleatorio y

h_{\mathrm {int} }

se elige aleatoriamente de una familia universal que mapea el dominio entero

[p]\mapsto [m]

.

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

uint hash ( String x , int a , int p ) uint h = VALOR_INICIAL 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 congruencial lineal . ^{[ 17 ]} El algoritmo anterior también se conoce como función hash multiplicativa . ^{[ 18 ]} En la práctica, el operador módulo y el parámetro p se pueden evitar por completo permitiendo que el entero se desborde, ya que es equivalente a mod ( Max-Int-Value + 1) en muchos lenguajes de programación. Sin embargo, al usar el no primo $2^{n}$ El módulo es propenso a colisiones con ciertas entradas , independientemente del valor de a . La siguiente tabla muestra los valores elegidos para inicializar h y a en algunas de las implementaciones más populares.

Consideremos dos cadenas ${\bar {x}},{\bar {y}}$ y dejar $\ell$ 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 $\ell$ . Una colisión antes de aplicar $h_{\mathrm {int} }$ implica que $a$ es una raíz del polinomio con coeficientes ${\bar {x}}-{\bar {y}}$ Este polinomio tiene como máximo $\ell$ raíces módulo $p$ , por lo que la probabilidad de colisión es como máximo $\ell /p$ . La probabilidad de colisión a través del azar $h_{\mathrm {int} }$ lleva la probabilidad total de colisión a ${\frac {1}{m}}+{\frac {\ell }{p}}$ Por lo tanto, si el primo $p$ es suficientemente grande en comparación con la longitud de las cadenas hash, la familia es muy cercana a universal (en distancia estadística ).

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 ]}

Uno elige el primo $p$ estar cerca de una potencia de dos, como un primo de Mersenne . Esto permite la aritmética módulo $p$ debe implementarse sin división (utilizando operaciones más rápidas como la suma y los desplazamientos). Por ejemplo, en arquitecturas modernas se puede trabajar con $p=2^{61}-1$ , mientras $x_{i}$ Los valores son de 32 bits.
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 la $\lceil k/16\rceil$ 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 de vector.
Se elige una potencia de dos como divisor, lo que permite la aritmética módulo $2^{w}$ Se implementará sin división (utilizando operaciones más rápidas de enmascaramiento de bits ). La familia de funciones hash NH adopta este enfoque.

Véase también

Hashing k -independiente : Familia de funciones hash
Hash rotativo : tipo de función hash. Páginas que muestran descripciones breves de los destinos de redirección.
Hashing por tabulación : funciones hash calculadas mediante exclusión o
Independencia min-wise : técnica de minería de datos. Páginas que muestran descripciones breves de los destinos de redireccionamiento.
Función hash unidireccional universal
Secuencia de baja discrepancia : tipo de secuencia matemática.
Hash perfecto : función hash sin colisiones. Páginas que muestran descripciones breves de los destinos de redirección.

Referencias

1 2 3 4 5 Carter, Larry; 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 . Versión de la conferencia en STOC'77.
↑ Miltersen, Peter Bro. "Universal Hashing" (PDF) . Archivado del original (PDF) el 24 de mayo de 2011. Recuperado el 24 de junio de 2009 .
↑ Motwani, Rajeev; Raghavan, Prabhakar (1995). Algoritmos aleatorios . Cambridge University Press. pág. 221. ISBN 0-521-47465-5.
↑ David Wagner, ed. "Avances en criptología - CRYPTO 2008" . pág. 145.
↑ Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. "La función hash BLAKE" . 2014. pág. 10.
↑ Thorup, Mikkel (2015). "High Speed Hashing for Integers and Strings". arXiv : 1504.06804 [ cs.DS ].
1 2 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 .
↑ Dietzfelbinger, Martin; Hagerup, Torben; Katajainen, Jyrki; Penttonen, Martti (1997). "Un algoritmo aleatorio fiable para el problema del par más cercano" (Postscript) . Journal of Algorithms . 25 (1): 19– 51. doi : 10.1006/jagm.1997.0873 . Consultado el 10 de febrero de 2011 .
^ Thorup, Mikkel (18 de diciembre de 2009). "Algoritmos de libros de texto en SODA" .
↑ Woelfel, Philipp (1999). Hashing universal fuerte y óptimo eficiente . Fundamentos matemáticos de la informática 1999. LNCS. Vol. 1672. pp. 262– 272. doi : 10.1007/3-540-48340-3_24 .
^ Thorup , Mikkel (2009 ) . Hashing de cadenas para sondeo lineal . Proc. XX 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
1 2 Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). Las funciones hash polinomiales son fiables (resumen extendido) . Actas del 19.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) . págs. 235–246 .
↑ 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
↑ 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.
1 2 Kaser, Owen; Lemire, Daniel (2013). "El hash de cadena universal fuerte es rápido". Computer Journal . 57 (11). Oxford University Press: 1624– 1638. arXiv : 1202.4961 . doi : 10.1093/comjnl/bxt070 .
↑ "Diapositivas del curso de la Universidad Hebrea" (PDF) .
↑ Robert Uzgalis . "Funciones hash de biblioteca" . 1996.
↑ Kankowsk, Peter. "Funciones hash: una comparación empírica" .
↑ Yigit, Ozan. "Funciones hash de cadena" .
↑ Kernighan; Ritchie (1988). "6" . El lenguaje de programación C (2.ª ed.). Prentice Hall. 118 págs . ISBN 0-13-110362-8.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
↑ "String (Java Platform SE 6)" . docs.oracle.com . Consultado el 10 de junio de 2015 .

Lecturas adicionales

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

[CW77-1] 1 2 3 4 5 Carter, Larry; 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 . Versión de la conferencia en STOC'77.

[Miltersen-2] Miltersen, Peter Bro. "Universal Hashing" (PDF) . Archivado del original (PDF) el 24 de mayo de 2011. Recuperado 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). "High Speed Hashing for Integers and Strings". arXiv : 1504.06804 [ cs.DS ].

[BDP-7] 1 2 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 .

[DHKP97-8] Dietzfelbinger, Martin; Hagerup, Torben; Katajainen, Jyrki; Penttonen, Martti (1997). "Un algoritmo aleatorio fiable para el problema del par más cercano" (Postscript) . 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" .

[w99-10] Woelfel, Philipp (1999). Hashing universal fuerte y óptimo eficiente . Fundamentos matemáticos de la informática 1999. LNCS. Vol. 1672. pp. 262– 272. doi : 10.1007/3-540-48340-3_24 .

[thorup09-11] Thorup , Mikkel (2009 ) . Hashing de cadenas para sondeo lineal . Proc. XX 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

[DGMP-12] 1 2 Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). Las funciones hash polinomiales son fiables (resumen extendido) . Actas del 19.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) . págs. 235–246 .

[black-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.

[kaser2013-15] 1 2 Kaser, Owen; Lemire, Daniel (2013). "El hash de cadena universal fuerte 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 cadena" .

[20] Kernighan; Ritchie (1988). "6" . El lenguaje de programación C (2.ª ed.). Prentice Hall. 118 págs . ISBN 0-13-110362-8.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )

[21] "String (Java Platform SE 6)" . docs.oracle.com . Consultado el 10 de junio de 2015 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

Introducción

Garantías matemáticas

Construcciones

Hash de enteros

Evitar la aritmética modular

Vectores de hash

Hash de cadenas

Evitar la aritmética modular

Véase también

Referencias

Lecturas adicionales

Enlaces externos

Articulos relacionados