Odcisk palca dla zestawów dynamicznych

Czy istnieje w-bitowa struktura danych słowo-RAM z czasem O (1) na operację dla następującego problemu ?: Utrzymanie zestawu w-bitowych nieujemnych liczb całkowitych, które obsługują operacje

add (x): dodaj x do zestawu
remove (x): usuń x z zestawu
odcisk palca (): zwraca odcisk palca zestawu. Ten w-bitowy odcisk palca ma właściwość polegającą na tym, że dwa identyczne zestawy mają ten sam odcisk palca, podczas gdy dwa różne zestawy prawdopodobnie mają różne odciski palców

Wszystkie operacje powinny przebiegać w stałym czasie.

Schemat linii papilarnych Rabin-Karp, w którym gdzie p jest losową liczbą w-bitową, prawie działa. Problem dotyczy czasu aktualizacji, ponieważ obliczenie zajmuje więcej niż stały czas. Za pomocą powtarzania kwadratu można to zrobić w czasie O (log w). Najszybszy modułowy algorytm potęgowania, jaki udało mi się znaleźć, wykonuje operacje arytmetyczne (log w) / (loglog w).

fa (S.) = (\sum_{x \in S.} {2)}^{x}) mod p

$f(S) = \left(\sum_{x\in S} 2^x\right) \bmod p$

{2)}^{x} mod p

$2^x \bmod p$

ds.data-structures

— Pat Morin
źródło

Widzę, że podobne pytanie zostało już tutaj opublikowane , ale nie podano rozwiązania w stałym czasie.

— Pat Morin

Ta odpowiedź jest nieco niepewna.

Wybierz funkcję równomiernie losowo z zestawu wszystkich funkcji od słów w-bitowych do słów w-bitowych. Dla każdego zestawu zachowaj odcisk palca w-bit w następujący sposób: $h$

Pusty zestaw ma odcisk palca 0.
dodaj (x) i usuń (x) zaktualizuj odcisk palca do , gdzie to xor. $f$ $f \oplus h(x)$ $\oplus$

Niech będzie dwoma zestawami liczb całkowitych w-bitowych. Jeśli ich odciski palców są takie same, to odcisk palca , symetryczna różnica i , wynosi 0, co dzieje się z prawdopodobieństwem . $S \neq T$ $S \triangle T$ $S$ $T$ $2^{-w}$

— jbapple
źródło

W praktyce można utworzyć instancję z funkcją pseudolosową (PRF) z kryptografii - np. Coś opartego na AES. Powinien być bardzo wydajny, a otrzymasz silne obietnice, że zadziała (chyba że krypto jest zepsute).

h

$h$

— DW