Блог пользователя Noob-ita-coder

Limits of Hashing
Автор Noob-ita-coder, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +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:)

→ Ответить