why we are multiplying every ascii value by prime no. raised from 0 to length of pattern - 1; why, I am not getting it?
Hash function calculation
Hello @Divya_321,
Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends of the efficiency of the hash function used.
Hash function is a formula where you pass key and it generates value.
You can choose any formula or hash function keeping in mind to minimize the complexity.
Here, we have used the rolling hash function which takes O(1) i.e. constant time to compute next hash value in the string to improve the time complexity.
Why do we use a prime number:
Because prime number causes less collisions in comparison to non prime numbers.
Why are multiplying the ASCII value of characters to prime no. raise to power 0 to length of pattern-1?
To create a rolling hash function.
This will ease the task of calculating new hash values as explained in the video in three steps.
- Subtract ASCII value of first char
- Divide with that prime number
- Add (ASCII of new char * prime no. raise to length of pattern-1
So, it’s just a logic built to improve the efficiency of the approach.
Hope, this would help.
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.