Huellas digitales para conjuntos dinámicos.

¿Existe una estructura de datos de word-RAM de w-bit con tiempo O (1) por operación para el siguiente problema ?: Mantenga un conjunto de enteros no negativos de w-bit que respalde las operaciones

• add (x): agrega x al conjunto
• remove (x): elimina x del conjunto
• huella digital (): devuelve una huella digital del conjunto. Esta huella digital de w-bit tiene la propiedad de que dos conjuntos que son idénticos tienen la misma huella digital, mientras que dos conjuntos que son diferentes probablemente tienen huellas digitales diferentes

Todas las operaciones deben ejecutarse en tiempo constante.

El esquema de huellas digitales Rabin-Karp, donde donde p es un primo aleatorio de w-bit casi funciona. El problema está en el tiempo de actualización, ya que calcular 2 x mod p requiere más que un tiempo constante. Usando la cuadratura repetida, esto se puede hacer en tiempo O (log w). El algoritmo de exponenciación modular más rápido que pude encontrar hace algo como las operaciones aritméticas (log w) / (loglog w).

Esta respuesta es un poco inestable.

Seleccione una función uniformemente al azar del conjunto de todas las funciones, desde palabras de w-bit hasta palabras de w-bit. Para cada conjunto, mantenga una huella digital de w-bit de la siguiente manera:$h$

1. El conjunto vacío tiene la huella digital 0.
2. agregar (x) y eliminar (x) actualizar una huella dactilar a f ⊕ h ( x ) , donde$f$$f \oplus h(x)$$\oplus$

$S \neq T$$S \triangle T$$S$$T$$2^{-w}$