Hi all. I have question. When we mod the hash value of substring, we need prime number, right? Are there some optimal prime numbers so that same hash value of different pattern can be minimized?
Thanks
Hi all. I have question. When we mod the hash value of substring, we need prime number, right? Are there some optimal prime numbers so that same hash value of different pattern can be minimized?
Thanks
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
It would be ideal to keep 2 hash functions. 100007 and 100021 are two good prime numbers to be used.
Ohh nice idea. Thanks a lot
I believe you meant 1e9 + 7 not 100007 because it's divisible by 97. Anyways, you shouldn't use well known prime numbers like 1e9 + 7 (it appears so much in contests that's why it's well known) because the problem setter may set test cases that fail this prime number (and I had it happened to me once when I used 1e9 + 7), you should use a RANDOMLY generated prime number.
Sorry, my mistake. What i wanted to say was 100003 instead of 100007. It' not necessary that you should use randomly generated prime numbers. If you use two hash functions it's very hard to find a case that fails.
Please don't confuse others. According to birthday paradox, you need to generate
random strings to get two different strings with equal hashes.
Even worse: to generate lots of strings with equal hashes it's enough to have only one(!) pair of strings with equal hashes. So this problem remains feasible even for double hashes modulo primes of magnitude greater than 10^9.
If the first function generates numbers uniformly in [0,M1) the probaility for a collision is 1/M1. If you add up another function independent form the first one which returns numbers in [0,M2) the probability of a collision drops to 1/M1 * 1/M2. This is way i said that it is hard to find two stings which fail the test. Am I wrong?
I'll just leave it here.
Generally, the larger the prime number is, the lower is the chance to have two different patterns with the same hash value (this by the way is called collision). Here are some primes easy to remember that guarantee low error probability:
Check this site: http://www.numberempire.com/primenumbers.php
They may guarantee low error probability, but are too large for integer arithmetic (even 64-bit), you'd need bigints to get substring hashes.
One can also use pairs of hashes modulo 2 different primes, though. It's even better since the probability of collisions decreases roughly as
, and what we'd get is basically a hash modulo their product, which is around 1018 if we use primes around 109 (109 + 9, 109 + 7 are good examples), and we can use 64-bit integers freely.