Apakah ada fungsi hash untuk koleksi (yaitu, multi-set) bilangan bulat yang memiliki jaminan teoritis yang baik?

Saya ingin tahu apakah ada cara untuk menyimpan hash multi-set bilangan bulat yang memiliki properti berikut, idealnya:

1. Ini menggunakan O (1) ruang
2. Ini dapat diperbarui untuk mencerminkan penyisipan atau penghapusan dalam waktu O (1)
3. Dua koleksi yang identik (yaitu, koleksi yang memiliki elemen yang sama dengan multiplisitas yang sama) harus selalu hash dengan nilai yang sama, dan dua koleksi yang berbeda harus hash ke nilai yang berbeda dengan probabilitas tinggi (yaitu, fungsi independen atau berpasangan independen)

Salah satu upaya awal ini adalah untuk menyimpan modulo produk perdana acak dari hash elemen individu. Ini memuaskan 1 dan 2 tetapi tidak jelas apakah itu, atau variasi dekat, akan memuaskan 3.

Saya awalnya memposting ini di StackOverflow .

* Properti 1 dan 2 bisa sedikit santai untuk, katakanlah, O (log n), atau polinomial sublinear kecil. Intinya adalah untuk melihat apakah kita dapat mengidentifikasi multi-set dan andal menguji kesetaraan tanpa menyimpan elemen itu sendiri.

Jika Anda menganggap set sebagai hidup di alam semesta , cukup mudah untuk menyelesaikan masalah Anda dengan waktu pembaruan O ( lg u ) . Yang Anda butuhkan adalah fungsi hash cepat untuk vektor nomor u , dengan "pembaruan lokal" yang cepat.$[u]$$O(\lg u)$$u$

Wikipedia / Universal hashing menyarankan , di mana p adalah bilangan prima yang cukup besar dan a secara seragam diambil dari [ p ] . Bila Anda menambahkan atau menghapus elemen i , Anda harus menambahkan / mengurangi sebuah i dari kode hash, yang mengambil O ( lg $h(\vec{x}) = \big(\sum_{i=1}^{u} x_i a^i \big) \bmod{p}$$p$$a$$[p]$$i$$a^i$ waktu menggunakan membagi dan menaklukkan untuk exponentiation tersebut. Karena jumlahnya banyak dari tingkat$O(\lg i)$$u$hanya dapat memiliki akar, kemungkinan tabrakan dua set yang berbeda adalah O [ u ] , tentu saja Anda bisa mulai dengan memecah alam semesta ke alam semesta yang lebih kecil.$u$ . Ini dapat dibuat sangat kecil dengan mengambil p menjadi cukup besar (misalnya, p = u 2 dan Anda bekerja dalam "presisi ganda"). Jika set jauh lebih kecil dari$O(u/p)$$p$$p=u^2$$[u]$

Adakah yang tahu solusi dengan probabilitas tabrakan saat hashing ke range [ p $O(1/p)$$[p]$ ? Ini seharusnya mungkin.

Carter dan Wegman membahas hal ini dalam fungsi hash Baru dan penggunaannya dalam otentikasi dan menetapkan kesetaraan ; sangat mirip dengan apa yang Anda gambarkan. Pada dasarnya fungsi hash komutatif dapat diperbarui satu elemen pada satu waktu untuk penyisipan dan penghapusan, dan kecocokan probabilitas tinggi, dalam O (1).

Kualitas fungsi hash akan selalu bergantung pada properti elemen yang harus hash. Bisakah Anda mengatakan sesuatu tentang ini? Misalnya, saran produk Anda mungkin fungsi hash yang buruk jika elemen x_i multiset Anda biasanya memiliki banyak faktor prima kecil. Tetapi Anda dapat memperbaikinya dalam hal ini hanya dengan mengambil produk dari semua x_i + p mod q untuk beberapa bilangan prima p dan 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

jumlah tersebut memungkinkan kita untuk memiliki banyak kejadian dengan nilai yang sama
dengan xor memungkinkan kita untuk memiliki jumlah yang sama dengan jumlah yang sama