Need help coming up with hash function algorithm

Question

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:

Given the string NOTE, we assign a value to each letter, for example:
```
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 my implementation is extremely inefficient. My professor said it shouldn't be longer than 7 lines. Can anyone offer suggestions on how to efficiently implement the above algorithm?

My algorithm in case anyone cares is:

int HashDictionary::getKey(string word) const{
    int wordLength = word.length();
    int* values = new int[wordLength];
    for ( int i = 0; i < wordLength; i++ ) {
        values[i] = int(word[i]);
    }

    int productSoFar = 0;
    for(int i = 0; i < wordLength;i++){
        productSoFar *= 32;

        if(i == 0){
            productSoFar = values[i] * 32;
            productSoFar = productSoFar + values[i+1];
            productSoFar %= tableSize;
            i++;
        }
        else{
            productSoFar += values[i];
            productSoFar %= tableSize;
        }

    }
    delete [] values;
    return productSoFar;
}

Why do you have an i++ inside the if() condition? Also, are you using C#? — noMAD
– noMAD, Commented May 1, 2012 at 1:36

Scott Hunter · Accepted Answer · 2012-05-01 01:35:40Z

1

You shouldn't need 2 loops; since the only thing the first does is translate the characters to integers, you can just translate each as you need it, and avoid the values array entirely. That should speed things up AND reduce your line count.

answered May 1, 2012 at 1:35

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

noMAD · Accepted Answer · 2012-05-01 01:41:57Z

0

Try this:

int HashDictionary::getKey(string word) const{
    int wordLength = word.length();
    int* values = new int[wordLength];
    values[0] = int(word[0]);
    values[1] = int(word[1]);

    int productSoFar = 0;
    productSoFar = values[0] * 32;
    productSoFar = productSoFar + values[1];
    productSoFar %= tableSize;

    for(int i = 1; i < wordLength;i++){
        productSoFar *= 32;
        productSoFar += values[i];
        productSoFar %= tableSize;
        values[i] = int(word[i]);
        }
    delete [] values;
    return productSoFar;
}

answered May 1, 2012 at 1:41

noMAD

7,85420 gold badges62 silver badges97 bronze badges

Collectives™ on Stack Overflow

Need help coming up with hash function algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related