Picking the base and mod for string hashing is very important in decreasing the probability of hash collisions. How much are the guidelines affected by the problem itself? So far, I've read that the base should be larger than the alphabet, and the mod should be really large (but not overflow). But is there anything else?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
You sound like you are on the right track. The base and mod must be coprime — usually, you just choose a prime base and prime mod anyway. Furthermore, you usually need hash two or more mods to stay safe. This is because of the birthday paradox. Normally people use base 137 and hash in 1e9+7 and 1e9+9.
Base should also be strictly greater than the number of different values an individual element can be. E.g. 137 is enough for English latters, but not enough for arbitrary
chars.Also, it's good to ensure that all codes of individual elements are between 0 and
base-1so they do not collide modulobasefor some random reason.:)
This topics has been discussed a lot of times.