XOR Hashing [TUTORIAL]

Правка en1, от humbertoyusta, 2020-12-24 06:45:32

This is a well known technique, but I couldn't find almost any detailed tutorial, so I'll try to help with this one.

Motivational Problem:

You have an array $$$A$$$ and $$$Q$$$ querys, which are, say if the subarray from $$$l$$$ to $$$r$$$, ($$$A[l]$$$, $$$A[l+1]$$$, $$$...$$$, $$$A[r]$$$) form a permutation.

Some basic observations:

Only the set of elements matter, the order is irrelvant.

You want to know if each element is exactly once.

Solution:

Assign a random number $$$randval[i]$$$ to each number $$$i$$$, now we can say that if the XOR of the subarray is equal to the xor of any permutation of size $$$r - l + 1$$$ (for example $$$1$$$, $$$2$$$, $$$3$$$, ... ,$$$r-l+1$$$).

Some Insights:

With the XOR we have some issues, we are counting if the ocurrences of each elements are even or odd, not the real number of ocurrences, however in this problem if we had repeated elements the XOR-hash will never be the same than the XOR-hash of $$$1$$$, $$$2$$$, $$$3$$$, ... ,$$$r-l+1$$$.

As an alternative to this tecnhique we can use polinomial hash over a binary string that represents the ocurrences of each element modulo $$$2$$$ ($$$x$$$-character of this string represents the number of ocurrences of $$$x$$$ modulo $$$2$$$), but with XOR hash we can do it faster, with less code and case handiling, and with less care about colisions and hacks.

With bitwise-OR we count the number of ocurrences of each element of the set modulo $$$2$$$, if we use $$$k$$$-nary xor we will count the number of ocurrences modulo $$$k$$$.

Collisions:

Now it's time to talk about collisions, as the number are random, the probability of colision in each query if we had only $$$1$$$ bit will be about $$$1/2$$$. And since XOR is independent on each bit, if we use k bits, the probability of colision in each query is $$$2^{-k}$$$. We can use 32-bit random integers or 64-bit random integers depending on the number of querys required. Since the numbers are generated randomly, I think this hashing can't be hacked, but I am not sure, if someone knows more about this, please send some feedback.

More problems using this technique (in no particular order of difficulty):

F. The Number of Subpermutations from Educational Codeforces Round 66 Here editorial doesn't use it, but i have one solution with this technique.

E. The Untended Antiquity from Codeforces Round #439 Div 2

G. Three Ocurrences from Educational Codeforces Round 95

C. Square Subsets from Codeforces Round #448 Div 2 but if we had just 40 numbers up to 10^6.

Feel free to send any feedback.

Теги #hashing, #xor, #tutorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский humbertoyusta 2020-12-24 19:31:06 674 I added a brief solution to the fourth problem which uses this technique
en7 Английский humbertoyusta 2020-12-24 19:20:11 1127 I added a brief solution to the first problem which uses this technique
en6 Английский humbertoyusta 2020-12-24 07:58:51 0 (published)
en5 Английский humbertoyusta 2020-12-24 07:55:43 765 Reverted to en3
en4 Английский humbertoyusta 2020-12-24 07:54:03 765 Tiny change: ' is like\n\nf(l,r)\n\n max ' -> ' is like\nf(l,r)\n max ' (saved to drafts)
en3 Английский humbertoyusta 2020-12-24 07:16:54 0 (published)
en2 Английский humbertoyusta 2020-12-24 07:15:58 228 (saved to drafts)
en1 Английский humbertoyusta 2020-12-24 06:45:32 2734 Initial revision (published)