Choosing Base and Mod prime numbers in Rabin Karp rolling hash function

296 Views Asked by At

This has been asked a lot but I have a scenario where what if the vector size is already known and there is no repetition in the characters or integers ?

Suppose:

vector<unsigned int> v = { 1,2,3,4,5,6,7,8,9,10};

We already know that I will have a maximum of 10 integers and no duplicates. I have lots of vectors to compute but lets say this is the worst case where 10 is the maximum size.
The forumla:

hash = (hash * PRIME_BASE+ v[i]) % PRIME_MOD;

Obviously the PRIME_BASE should be = vector size - 1 which is in this case 9 (I know 9 is not a prime base) but it will not create a conflict .

But how to choose the PRIME_MOD to decrease the large numbers generated knowing the maximum size of the vector and that there is no repetition of numbers in it?
I am trying to generate linear congruential hashes.

Thanks

UPDATE
I forgot to mention also that we already know that the highest number in all vectors is also known which is in this sample case is 10.

0

There are 0 best solutions below