Creating A Better Hash Function

Question

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

class Item {
public:
    Item(const string & v): value(v), next(0) { }
    string value;
    Item * next;
};

int hash_function(const string & s)
{
    unsigned int hashval = 0;
    int i = s.length();
    while (i > 0)
{
        hashval += s[--i];
}       
return hashval%101;
}

main()
{
    string name;
    int index;
    Item * p;

    vector<Item *> bucket(101);

    for (index = 0; index < 101; index++)
        bucket[index] = 0;

    while (cin >> name) {
        p = new Item(name);
        index = hash_function(name);

        // push front
        if (bucket[index] != 0)
            p->next = bucket[index];
        bucket[index] = p;
    }

    for (index = 0; index < 101; index++)
        if (bucket[index] != 0) {
            cout << setw(3) << index << ": ";
            p = bucket[index];
            while (p != 0) {
                cout << p->value << " ";
                p = p->next;
            }
            cout << endl;
        }

    Item * temp;
    for (index = 0; index < 101; index++) {
        p = bucket[index];
        while (p != 0) {
            temp = p;
            p = p->next;
            delete temp;
        }
    }
}

which contains two very simple hash functions. I'm trying to work on the one which is not commented out, as it seems like the better of the two when tested. I want a set of names that is input to be distributed evenly in it's own bucket and so far, that seems to be working, with the exception of names which begin with the same letter. For example, Amy and Alice will appear in the same bucket and so on.

Here is a sample input/output:

Alice
Amy  
Barry
Carrie
David
Garret 
Edward
Henry
Ingrid
Fred
 65: Amy Alice 
 66: Barry 
 67: Carrie 
 68: David 
 69: Edward 
 70: Fred 
 71: Garret 
 72: Henry 
 73: Ingrid

What can I add to my algorithm that would allow Amy and Alice to be placed in their own bucket?

Please, provide a valid code. Your hash_function doesn't return anything and main doesn't have a return type. Switching to a better compiler may help. — Yakov Galka
– Yakov Galka, Commented Mar 20, 2011 at 21:58
calculate the hash function you have in mind for one example name manually and compare that to the data you posted above. — Doc Brown
– Doc Brown, Commented Mar 20, 2011 at 22:08

Gareth McCaughan · Accepted Answer · 2011-03-20 21:58:55Z

8

Your function hash_function isn't actually returning a value. You should pay more attention to your compiler's warnings!

Apparently it happens to have the effect of returning the first character in the string. This is purely arbitrary. On another platform it might always return zero, or cause your computer to explode. (Probably not actually the latter.)

As for making a better hash function: once you fix this bug, you'll no longer find that the hash value depends only on the first character. However, you will find e.g. that "Brian" and "Brain" hash to the same value. That's the next thing you should think about.

answered Mar 20, 2011 at 21:58

Gareth McCaughan

20k1 gold badge43 silver badges64 bronze badges

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

Comments

Sarfaraz Nawaz · Accepted Answer · 2011-03-20 22:14:44Z

1

Instead of blindly adding each letter, give some weight to each, so that cpp, pcp, ppc all could produce different hashvalue.

Here is little improved version:

int hash_function(const string & s)
{
    double hashval = 0;
    int i = s.length();
    double weight = 1.0;
    while (i > 0)
    {
        hashval +=  weight * s[--i];
        weight *= 1.5;
    }       
    return (int) hashval;
}

Assuming the string s is not too long, otherwise there will be overflow!

answered Mar 20, 2011 at 22:14

Sarfaraz Nawaz

363k121 gold badges682 silver badges867 bronze badges

2 Comments

MSalters Over a year ago

Overflow can be fixed fairly easily: int exp; hashval=frexp(hashval, &exp); return int(hashval)+exp; - you scale back hashval and use its magnitude in the hashvalue too.

Luqmaan Over a year ago

Fails to generate a unique hash for 123 and 132, hash becomes 236.

yodie · Accepted Answer · 2011-03-21 00:18:50Z

0

Try weighting the different letters differently. In your current implementation (assuming it worked, as mentioned above), the name ab would hash to the same value as ba. Something like:

for (int i = 0 to str.len())
    hash = hash + hash + str[i]

would return different values for two strings with the same letters, yet is still very simple.

edited Mar 21, 2011 at 0:18

answered Mar 20, 2011 at 22:03

yodie

4315 silver badges14 bronze badges

Collectives™ on Stack Overflow

Creating A Better Hash Function

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related