larush's blog

How to hash?
By larush, history, 14 months ago, In English

Hello

So I was solving this problem (here), and a hashing-based solution seemed obvious to me. It is enough to look at the hash of the changed substring and get the final hash of the modified string using the prefix and suffix. I do not know much about hashing, just a little about polynomial (or rolling) hash. But it seems that my hash isn't safe enough. I tried a few things, but with no luck:

Spoiler

I used the standard primes M = 1e9+9 and p = 31 initially, as I learned from cp-algo. I have no clue what I'm doing wrong.

I hope someone could assist me in this and help me understand hashing a little better. Cheers!

off by one
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
14 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can only improve probability of correct answer using hashing.

You can check SlavicG submission. He used $$$3$$$ different combination of $$$3$$$ $$$M$$$ (mod) values and $$$4$$$ different $$$p$$$ values to improve his probability of getting correct output.

You can also checkout his other submission during contest which failed to pass since they used only $$$1$$$ value of $$$M$$$ and $$$p$$$. submission-1 submission-2

UPD: You can checkout this blog for more information on multi-hashing and how to write hard to hack hashing code (and also how to hack poorly written hashes).

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I do not think that the SlavicG submission you linked is safe from hacks. I've hacked many similar rolling hash solutions like that in that past. The reason it is hackable is that

    1. All of the bases used are constant (non-random).
    2. The prime mods used are small. The time complexity for a typical hash hack algorithm is O(sqrt(largest prime)).

    In my opinion, the easiest solution to be safe from hacks when using rolling hashes is to use a single large prime like $$$P=2^{61} - 1$$$, and then use a random base (pick it uniformly at random in [0, P)). But whichever option you choose to go with, do not make the base constant (non-random).

    Just a final note. SlavicG technically does randomize the bases using shuffle(all(plsnohack2), rng);, but there are only 24 different possible outcomes. So his choice of bases is effectively deterministic.

    → Reply
»
14 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

But it seems that my hash isn't safe enough.

Since all of your hashes are integers in range $$$[0, M)$$$, there are $$$M$$$ different possible hashes. Your code will work incorrectly if you encounter a hash collision, i.e. a case where two different strings hash to the same hash value.

In the problem you linked, you're comparing up to $$$2\cdot10^5$$$ hashes with each other. According to the birthday paradox you only need around $$$\sqrt{M}$$$ different hashes before it's expected that some two are the same. Since $$$2\cdot10^5$$$ is much larger than $$$\sqrt{M} \approx 31622$$$, it's very likely that you'll encounter a hash collision.

The easiest way to deal with this is to choose two different pairs of (multiplier, modulus) and calculate the hash with both; now the hash is the pair of these hashes. Now the number of hashes is on the order of $$$M^2$$$ and we'd expect a collision only once we have around $$$M$$$ strings, so two hashes should be good enough. Of course you can use more to be safe but it's probably not required.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Adding to this, in most* problems it usually suffices to have $$$2^{64}$$$ as the second modulus for ease of implementation (something like 231564057).

    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! It took me some time to implement, but I'm pretty sure the hash is much safer. Thanks for your advice.

    accepted submission

    → Reply
»
14 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

using unsigned long long to hash, i will call it overflow hashing.

You can check my code for better understanding: https://mirror.codeforces.com/contest/1840/submission/208865643

→ Reply