Introducción al hashing universal en la estructura de datos

Hashing es una gran herramienta práctica, con una teoría interesante y sutil también. Además de su uso como estructura de datos de diccionario, el hashing también aparece en muchas áreas diferentes, incluida la criptografía y la teoría de la complejidad . 

Este artículo analiza una noción importante: Hashing universal (también conocido como familias de funciones hash universales ).

Universal Hashing se refiere a seleccionar una función hash al azar de una familia de funciones hash con una determinada propiedad matemática. Esto asegura un número mínimo de colisiones.

Un algoritmo aleatorio H para construir funciones hash h : U → {1,… ,M} es universal si para todo (x, y) en U tal que x ≠ y , Pr _h∈H [h(x) = h(y )] ≤ 1/M (es decir, la probabilidad de x e y tal que h(x) = h(y) es <= 1/M para todos los valores posibles de x e y ).

Un conjunto H de funciones hash se denomina familia universal de funciones hash si el procedimiento “ elegir h ∈ H al azar ” es universal. (Aquí la clave es identificar el conjunto de funciones con la distribución uniforme sobre el conjunto).

Teorema: Si H es un conjunto de la familia universal de funciones hash, entonces para cualquier conjunto S ⊆ U de tamaño N , tal que x ∈ U y y ∈ S , el número esperado de colisiones entre x y y es como mucho N/M .

Prueba: cada y ∈ S (y ≠ x) tiene como máximo una probabilidad de 1/M de colisionar con x según la definición de «universal». Asi que,

• Sea C _xy = 1 si x e y colisionan y 0 en caso contrario.
• Sea C _x el número total de colisiones para x . Entonces, C _x = ∑ _{y∈S, x≠y} C _{xy .}
• Sabemos que E[C _xy ] = Pr[ x e y colisionan ] ≤ 1/M .
• Entonces, por la linealidad de la expectativa , E[C _x ] = ∑ _y E[C _xy ] < N/M .

Corolario: si H es un conjunto de la familia universal de funciones hash, entonces para cualquier secuencia de L operaciones de inserción, búsqueda o eliminación en la que haya como máximo M elementos en el sistema en cualquier momento, el costo total esperado de las L operaciones para un h ∈ H aleatorio es solo O(L) (viendo el tiempo para calcular h como constante). 

Para cualquier operación dada en la secuencia, su costo esperado es constante según el teorema anterior. Por lo tanto, el costo total esperado de las operaciones L es O(L) por la linealidad de la expectativa .

Construyendo una familia hash universal usando el método matricial:

Digamos que las claves tienen una longitud de u-bits y el tamaño de la tabla M es la potencia de 2 , por lo que un índice tiene una longitud de b-bits con M = 2 ^b .

Lo que haremos es elegir h para que sea una array binaria b-by-u aleatoria y definir h(x) = hx , donde hx se calcula sumando algunas de las columnas de h (haciendo una suma de vectores sobre mod 2) donde el 1 bits en x indican qué columnas agregar. (p. ej., las columnas 1 y 3 de ^h se ^agregan en el siguiente ejemplo). Estas arrays son cortas y gordas. Por ejemplo:

Ahora, tome un par arbitrario de claves ( x, y) tal que x ≠ y . Deben diferir en alguna parte, supongamos que difieren en la i ^-ésima coordenada, y para concretar digamos x _i = 0 y y _i = 1 . Imagine que primero elegimos todas las h excepto la i- ^ésima columna. Sobre las opciones restantes de la i- ^ésima columna, h(x) es fijo. Sin embargo, cada uno de los 2 ^b ajustes diferentes de la i- ^ésima columna da un valor diferente de h(y) (en particular, cada vez que volteamos un bit en esa columna, volteamos el bit correspondiente en h(y) ). Así que hay exactamente una probabilidad de 1/2 ^{b de que} h(x) = h(y) .