Hash string

Applications Programming
1

Hello everyone!

I'm writing a C++ program and I use a hash table which contains strings.
Its the first time I have to deal with strings since the only thing I have done so far is for integers and is the following:

int hashFunction(int key){ 
	return key%sizeOfHashTable;
}

but how can I do the same for strings?
I need the result to give an integer as the hashing is based on integers although the hash table elements are strings.Any ideas?

To be more specific I still want my function to return an integer although it takes a string as an argument(key)

2

It depends on how you want to use the int output of the hash function...is it to be used as an index into the array...in which case you can add up the ascii values of each of the individual characters that make up the string modulo the no of elements of the array in order to get the index into the array.

3

As an aside, that's not a particularly good method for hashing an integer. It means integers n, n+1, n+2, etc will all end up in a row in the table, which will make searching for empty slots slow if there's a collision. More often used is the 'fibbonaci hash', which works by multiplying the key by a 'relatively prime' number before taking the modulous. This spreads out the resulting array indexes across the table.

int hash(int value) { return((value*2654435769)%tablesize);

There are many, many different algorithms for hashing strings, some good, some bad. The idea is to take the characters one at a time and combine them in some way into a single integer. A fairly bad method is to just sum up the values of all the characters and then take the modulous of that. Bad because, "aaA", "aAa", "Aaa" would all have the same hash because they have the same sum.

Better methods mangle the character in various ways depending on its position in the string. This one shifts it one bit for each position, wrapping at 23 bits, to give better odds that "aaA", "aAa", "Aaa" don't hash to the same string. I make no guarantees that it's ideal in any way but is at least better than summing.

int hash(const char *val)
{
        unsigned int n=0, hash=0;
        while(val[n])
        {
                hash ^= ((unsigned int)val[n]) << (n%23)
                n++;
        }

        return(hash%tablesize);
}

There'll always be a chance at hash collisions because there's more than 2^32 different strings in the world. But you do what you can to reduce the odds.