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

Limits of Hashing
Автор CP_Sucks, история, 5 лет назад, По-английски

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 ?

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

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

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:)

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

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

    → Ответить