I'm working on a hash function that gives a given string an "ID" by mapping that string to a key. The algorithm I need to use is described below:
1 2 3 4 5 6 7 8 9 10 11 12 13
Given the string "NOTE", we assign a value to each letter as such:
N = 14, O =15, T = 20, E = 5
Then we multiply and add:
14 * 32^3 + 15 * 32^2 + 20 * 32^1 + 5 * 32^0
By factoring this expression we get:
((14 * 32 + 15) * 32 + 20) * 32 + 5
But that value might get too large so we use mod division after each set of parentheses as such:
((14 * 32 + 15)%tableSize *32 + 20)%tableSize * 32 +5
How can I create an algorithm to accomplish this? I have tried to do it but mine takes wayyyy too long and is extremely inefficient. My prof said it shouldnt be longer than 7 lines....I'm going to continue thinking about it but I just thought I'd see if anyone could help
The first trick is to notice that you are doing the same thing over and over again, suggesting a loop.
Another trick is that you can find a letter's index in the alphabet by subtracting the first letter. Assuming your input is only the 26 English capital letters:
1 2
int value = c - 'A' + 1;
// we added one because we start counting at one: A=1, B=2, C=3, etc.
The "table size" is 26 - since there are 26 letters in the alphabet.
You need to have a 'sum' kind of variable, and an 'index' variable to count through the input message in your loop.