Блог пользователя ajecc

Question about hashing
Автор ajecc, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
← Rev. 4   Проголосовать: нравится +16 Проголосовать: не нравится

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.

→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить