Czy istnieje funkcja skrótu dla zbioru liczb całkowitych (tj. Wielu), która ma dobre gwarancje teoretyczne?

Ciekawe, czy istnieje sposób przechowywania skrótu zbioru liczb całkowitych, który ma następujące właściwości, najlepiej:

1. Wykorzystuje spację O (1)
2. Można go zaktualizować, aby odzwierciedlał wstawianie lub usuwanie w czasie O (1)
3. Dwie identyczne kolekcje (tj. Kolekcje, które mają te same elementy o tych samych wielokrotnościach) zawsze powinny mieć skrót do tej samej wartości, a dwie odrębne kolekcje powinny mieć skrót do różnych wartości z dużym prawdopodobieństwem (tj. Funkcja jest niezależna lub parami niezależna)

Jedną z początkowych prób byłoby przechowywanie modulo produktu losowej liczby pierwszych skrótów poszczególnych elementów. Spełnia to 1 i 2, ale nie jest jasne, czy to, czy też ścisła odmiana, spełnia 3.

Pierwotnie opublikowałem to na StackOverflow .

* Właściwości 1 i 2 można nieco rozluźnić, powiedzmy, O (log n) lub mały podliniowy wielomian. Chodzi o to, czy możemy zidentyfikować wiele zestawów i rzetelnie przetestować równość bez przechowywania samych elementów.

Jeśli uważasz, że zestawy żyją we wszechświecie , dość łatwo jest rozwiązać problem z czasem aktualizacji O ( lg u ) . Wszystko czego potrzebujesz to szybka funkcja skrótu dla wektora liczb u , z szybkimi „lokalnymi aktualizacjami”.$[u]$$O(\lg u)$$u$

, gdzie p jest wystarczająco dużą liczbą pierwszą, a a jest równomiernie narysowane z [ p ] . Po dodaniu lub usunięciu elementu I , trzeba dodać / odjąć a ja z kodu skrótu, który zajmuje O ( lg í ) czas korzystania dziel i rządź do potęgowania. Ponieważ wielomian stopnia$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$może mieć tylko pierwiastki , prawdopodobieństwo zderzenia dla dwóch różnych zbiorów wynosi O ( u / p ) . Można to zrobić bardzo małe, przyjmując, że p jest wystarczająco duże (na przykład p = u 2 i pracujesz w „podwójnej precyzji”). Jeśli zestawy są znacznie mniejsze niż [ u ] , możesz oczywiście rozpocząć od skrócenia wszechświata do mniejszego wszechświata.$u$$O(u/p)$$p$$p=u^2$$[u]$

Czy ktoś zna rozwiązanie z prawdopodobieństwem kolizji przy mieszaniu do zakresu [ p ] ? To powinno być możliwe.$O(1/p)$$[p]$

Carter i Wegman opisują to w nowych funkcjach skrótu oraz ich zastosowaniu w uwierzytelnianiu i ustawianiu równości ; jest bardzo podobny do tego, co opisujesz. Zasadniczo komutatywną funkcję skrótu można aktualizować pojedynczo dla wstawiania i usuwania oraz dopasowań o wysokim prawdopodobieństwie w O (1).

Jakość funkcji skrótu zawsze będzie zależeć od właściwości elementów, które musi mieszać. Czy możesz coś o tym powiedzieć? Na przykład sugestia produktu jest prawdopodobnie słabą funkcją skrótu, jeśli elementy x_i multiset zwykle mają wiele małych czynników pierwszych. Ale możesz to poprawić w tym przypadku, po prostu biorąc iloczyn wszystkich x_i + p mod q dla niektórych liczb pierwszych p i 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

suma pozwala nam mieć wiele wystąpień o tej samej wartości
xor pozwala nam mieć zestawy tej sumy na tę samą kwotę