CP_Sucks's blog

Limits of Hashing
By CP_Sucks, history, 4 years 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

Comments Comments (2)
| Write comment?
»
4 years 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:)

→ Reply
  • »
    »
    4 years 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.

    → Reply