Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

CP_Sucks's blog

By CP_Sucks, history, 17 months ago, In English

Is there any limit to the length of the string after which hashing should be avoided. Also can the hashing solutions be easily hacked in contests ?

 
 
 
 
  • Vote: I like it
  • -14
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For p = 31 and m = 1e9 + 9, if string is zzzzzzz the hash value is more than 1e9 + 9 and the collisions start, so how can i use it for strings as large as 1e6 without getting hacked ?

»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

According to the birthday paradox, if m = 1e9 + 9, we can random about 200000 strings and the possibility of collisions is more than 99.9999%!

Simple code can calculate the possibility:

int m = 1e9 + 9;
double x = 1;
for (int i = 0; i < 200000; ++i) {
    x = x * (m - i) / m;
}
x = 1.0 - x;
cout << fixed << setprecision(11) << x << endl;

Also, if you want to make your hashing become hard to hack, there are two possible choice:

  1. use a long long prime as m

  2. use two or more hash functions

Sorry for my poor English, I hope this can help you:)

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Well, that might make it a bit harder to hack, but still hackable. You should also make your base randomized.