ajecc's blog

Question about hashing
By ajecc, history, 7 years ago, In English

Hello! I was working on this problem: 126B - Password. I couldn't come up with a solution so I checked other people's sources. I came across this one that uses hashing: 847891. My question is: how does that solution work, when most values of the arrays p and hash are overflown? I don't see any %MOD operation, which makes this strange to me, as I am not very experimented with hashing.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

When the product overflows, it will be taken modulo 2^64 (for long long). So it computes hashes modulo 2^64

→ Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

Hi, it's just standart trick in hashes, if we don't use MOD operation, it automatically use INT/LONG LONG modulo, dependts from type. Actually, it's easy to check and understand.

Try this: cout << INT_MAX << " " << INT_MAX + 1 << " " << INT_MAX + 2;

Also, you should understand that it isn't the best way to use hashes. This topic will help you to understand why it so.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

As others have already mentioned, it is a well known trick.

Just a note though that you got to be careful that when the value overflows it does not become zero. So, if the hash is a computed value of a polynomial with base b then make sure that gcd(b, 2^64) = gcd(b, 2) = 1, in other words, use either odd numbers or (often even better) prime numbers.

For clarity: in terms of the code you refered to, b is the same as SEED and in the code SEED = 1007 which looks like a prime number, but it actually isn't (1007 = 19*53), and it doesn't have to be for the hash to work.

→ Reply