¿Existe una función hash para una colección (es decir, un conjunto múltiple) de enteros que tiene buenas garantías teóricas?

Tengo curiosidad por saber si hay una manera de almacenar un hash de un conjunto múltiple de enteros que tenga las siguientes propiedades, idealmente:

1. Utiliza el espacio O (1)
2. Se puede actualizar para reflejar una inserción o eliminación en tiempo O (1)
3. Dos colecciones idénticas (es decir, colecciones que tienen los mismos elementos con las mismas multiplicidades) siempre deben tener el mismo valor, y dos colecciones distintas deben tener valores diferentes con alta probabilidad (es decir, la función es independiente o independiente por pares)

Un intento inicial de esto sería almacenar el módulo del producto como un primo aleatorio de los valores hash de los elementos individuales. Esto satisface 1 y 2, pero no está claro si, o una variación cercana, satisfaría 3.

Originalmente publiqué esto en StackOverflow .

* Las propiedades 1 y 2 se pueden relajar un poco, por ejemplo, O (log n), o un pequeño polinomio sublineal. El punto es ver si podemos identificar conjuntos múltiples y probar de manera confiable la igualdad sin almacenar los elementos en sí.

Si piensa que los conjuntos viven en el universo , es bastante fácil resolver su problema con el tiempo de actualización de . Todo lo que necesita es una función hash rápida para un vector de números , con "actualizaciones locales" rápidas.$[u]$$O(\lg u)$$u$

Wikipedia / Universal hashing sugiere , donde es un primo suficientemente grande y se extrae uniformemente de . Cuando agrega o elimina el elemento , debe sumar / restar del código hash, lo que toma tiempo usando dividir y conquistar para la exponenciación. Como un polinomio de grado solo puede tener raíces , la probabilidad de colisión para dos conjuntos distintos es . Esto puede hacerse muy pequeño tomando como lo suficientemente grande (por ejemplo,$h(\vec{x}) = \big(\sum_{i=1}^{u} x_i a^i \big) \bmod{p}$$p$$a$$[p]$$i$$a^i$$O(\lg i)$$u$$u$$O(u/p)$$p$$p=u^2$y trabajas en "doble precisión"). Si los conjuntos son mucho más pequeños que , por supuesto, puede comenzar reduciendo el universo a un universo más pequeño.$[u]$

¿Alguien sabe una solución con probabilidad de colisión cuando hashing para rango ? Esto debería ser posible.$O(1/p)$$[p]$

Carter y Wegman cubren esto en las nuevas funciones hash y su uso en autenticación y establecimiento de la igualdad ; Es muy similar a lo que usted describe. Esencialmente, una función hash conmutativa se puede actualizar un elemento a la vez para inserciones y eliminaciones, y coincidencias de alta probabilidad, en O (1).

La calidad de una función hash siempre dependerá de las propiedades de los elementos que tiene que hacer hash. ¿Puedes decir algo sobre esto? Por ejemplo, su sugerencia de producto es probablemente una función hash deficiente si los elementos x_i de su multiset suelen tener muchos factores primos pequeños. Pero puede mejorarlo en este caso simplemente tomando el producto de todo x_i + p mod q para algunos primos p y q.

A = 0x4F1BBCDD
B = 0x314EFB75
A*B = 1 
N = size of set before addition/removal<P>
Add X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U+X)&M)<<16) + ((V^X)&M)
H *= A
H += N+1

Remove X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U-X)&M)<<16) + ((V^X)&M)
H *= A
H += N-1

la suma nos permite tener múltiples ocurrencias del mismo valor que
la xor nos permite tener conjuntos que suman la misma cantidad