Existe uma função hash para uma coleção (ou seja, vários conjuntos) de números inteiros que possui boas garantias teóricas?

Estou curioso para saber se existe uma maneira de armazenar um hash de um conjunto múltiplo de números inteiros que possua as seguintes propriedades, idealmente:

1. Utiliza espaço O (1)
2. Pode ser atualizado para refletir uma inserção ou exclusão no tempo O (1)
3. Duas coleções idênticas (ou seja, coleções que possuem os mesmos elementos com as mesmas multiplicidades) devem sempre hash para o mesmo valor e duas coleções distintas devem hash para valores diferentes com alta probabilidade (ou seja, a função é independente ou independente em pares)

Uma tentativa inicial seria armazenar o módulo do produto como um primo aleatório dos hashes dos elementos individuais. Isso satisfaz 1 e 2, mas não está claro se, ou uma variação aproximada, satisfaria 3.

Originalmente, eu postei isso no StackOverflow .

* As propriedades 1 e 2 podem ser relaxadas um pouco para, digamos, O (log n) ou um pequeno polinômio sublinear. O objetivo é ver se podemos identificar vários conjuntos e testar de forma confiável a igualdade sem armazenar os próprios elementos.

Se você pensa em conjuntos como vivendo no universo , é muito fácil resolver seu problema com o tempo de atualização O ( lg u ) . Tudo que você precisa é de uma função rápida de hash para um vetor de números u , com rápidas "atualizações locais".$[u]$$O(\lg u)$$u$

$h(\vec{x}) = \big(\sum_{i=1}^{u} x_i a^i \big) \bmod{p}$uma [ p ] i um i O ( lg i ) u u S ( u / p ) p p = u 2 [ u $p$$a$$[p]$$i$$a^i$$O(\lg i)$$u$$u$$O(u/p)$ . Isso pode ser muito pequeno considerando que seja grande o suficiente (por exemplo, e você trabalha com "precisão dupla"). Se os conjuntos são muito menores que , é claro que você pode começar por fazer o universo se transformar em um universo menor.$p$$p=u^2$$[u]$

Alguém conhece uma solução com probabilidade de colisão ao fazer o hash no intervalo ? Isso deveria ser possível.[ p $O(1/p)$$[p]$

Carter e Wegman abordam isso em Novas funções de hash e seu uso na autenticação e na igualdade de conjuntos ; é muito parecido com o que você descreve. Essencialmente, uma função hash comutativa pode ser atualizada um elemento por vez para inserções e exclusões e correspondências de alta probabilidade, em O (1).

A qualidade de uma função de hash sempre dependerá das propriedades dos elementos que ele tem para o hash. Você pode dizer algo sobre isso? Por exemplo, a sugestão do seu produto provavelmente é uma função de hash ruim se os elementos x_i do seu multiset normalmente tiverem muitos fatores primos pequenos. Mas você pode melhorá-lo neste caso simplesmente usando o produto de todos os x_i + p mod q para alguns primos peq.

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

a soma nos permite ter várias ocorrências do mesmo valor,
o xor nos permite ter conjuntos que somam a mesma quantidade