Ad:

C++ Discussion Thread
Unsolved
Views: 10319

Oct 21st, 2009

String Hash Function

Expand Post »

I am trying to optimize my hash function, for a separate chaining hash table that I have created from scratch. My hash function is as follows:

C++ Syntax (Toggle Plain Text)
     int hash( const string &key, int tableSize)
        {
            int hashVal = 0;
			for(int i = 0; i<key.length();  i++)
			hashVal = 37*hashVal+key[i];
			hashVal %= tableSize;
			if(hashVal<0)
			hashVal += tableSize;
			return hashVal;
        }
     int hash( const string &key, int tableSize)
        {
            int hashVal = 0;
			for(int i = 0; i<key.length();  i++)
			hashVal = 37*hashVal+key[i];
			hashVal %= tableSize;
			if(hashVal<0)
			hashVal += tableSize;
			return hashVal;
        }

I was wondering if one could point me to either a better hash function or how I should go about modifying this function.

Similar Threads

Simple Hash Function for Integer Arrays in C
string array to function in C++
help with a hash function... in C++
hash function in C++
Help regarding PJW hash function in Java

killerqb

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2009

Permalink

Oct 21st, 2009

Re: String Hash Function

SAX was designed for hashing strings and is supposed to be really good for it:

C++ Syntax (Toggle Plain Text)
unsigned hash(string const& key, unsigned tableSize)
{
    unsigned hashVal = 0;
 
    for (int x = 0; x < key.length(); ++x)
    {
        hashVal ^= (hashVal << 5) +
                   (hashVal >> 2) +
                   key[x];
    }
 
    return hashVal % tableSize;
}
unsigned hash(string const& key, unsigned tableSize)
{
    unsigned hashVal = 0;

    for (int x = 0; x < key.length(); ++x)
    {
        hashVal ^= (hashVal << 5) +
                   (hashVal >> 2) +
                   key[x];
    }

    return hashVal % tableSize;
}

Your algorithm is a common variation of a good hash that uses 33 instead of 37. It should work well in the general case.

Tom Gunn

Reputation Points: 1446

Solved Threads: 135

Practically a Master Poster

Offline

681 posts
since Jun 2009

Permalink

Oct 21st, 2009

Re: String Hash Function

Thanks, but when I implemented your hash function it took nearly twice as long. Any other functions I should give a whirl?

killerqb

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2009

Permalink

Oct 21st, 2009

Re: String Hash Function

Quote ...

Thanks, but when I implemented your hash function it took nearly twice as long.

OK, by optimize you mean speed and not collisions. Your algorithm is about as fast as it gets without having excessive collisions or doing micro optimizations. Are you trying to increase the speed because you have proven it to be too slow with a profiler? If not, do not bother because programmers are very bad at guessing where performance bottlenecks are.

Tom Gunn

Reputation Points: 1446

Solved Threads: 135

Practically a Master Poster

Offline

681 posts
since Jun 2009

Permalink

Oct 21st, 2009

Re: String Hash Function

Click to Expand / Collapse Quote originally posted by killerqb ...

Thanks, but when I implemented your hash function it took nearly twice as long. Any other functions I should give a whirl?

Is your call to .length() getting called every time or are you assuming that will get optimized away?

Rashakil Fol

Team Colleague

Reputation Points: 1135

Solved Threads: 173

Super Senior Demiposter

Offline

2,479 posts
since Jun 2005

Permalink

Oct 21st, 2009

Re: String Hash Function

Yes, sorry I meant speed by optimize, I guess I did not clarify. I'm kinda new to hash functions.

killerqb

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2009

Permalink

Oct 21st, 2009

Re: String Hash Function

I was trying to play around with the FNV function but my program keeps seg faulting

static const unsigned InitialFNV = 2166136261;
static const unsigned FNVMultiple = 16777619;

// /* Fowler / Noll / Vo (FNV) Hash */
unsigned HashTable::hashFunc(const string &s)const
{
unsigned hash = InitialFNV;
for(unsigned i = 0; i < s.length(); i++)
{
hash = hash ^ (s[i]); /* xor the low 8 bits */
hash = hash * FNVMultiple; /* multiply by the magic number */
}
return hash;
}

killerqb

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2009

Permalink

Oct 21st, 2009

Re: String Hash Function

This was actually the original function I found online, but I was trying to modify it in order to get it to work with my code. However I am unfamiliar with size_t and the U at the end of the InitialFNV initialization.
So can someone explain the U and size_t please.

C++ Syntax (Toggle Plain Text)
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;
 
/* Fowler / Noll / Vo (FNV) Hash */
size_t myhash(const string &s)
{
    size_t hash = InitialFNV;
    for(size_t i = 0; i < s.length(); i++)
    {
        hash = hash ^ (s[i]);       /* xor  the low 8 bits */
        hash = hash * FNVMultiple;  /* multiply by the magic number */
    }
    return hash;
}
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;

/* Fowler / Noll / Vo (FNV) Hash */
size_t myhash(const string &s)
{
    size_t hash = InitialFNV;
    for(size_t i = 0; i < s.length(); i++)
    {
        hash = hash ^ (s[i]);       /* xor  the low 8 bits */
        hash = hash * FNVMultiple;  /* multiply by the magic number */
    }
    return hash;
}

Last edited by killerqb; Oct 21st, 2009 at 1:43 pm.

killerqb

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

20 posts
since Sep 2009

Permalink

Oct 21st, 2009

Re: String Hash Function

The U means that it's an unsigned integer literal. size_t is an unsigned integer type that's guaranteed to be able to hold the size of an array. But not a std::string. If you're paranoid you should use std::string::size_type. Don't be.

Your program is not segfaulting because of the hash function. The error is elsewhere.

Rashakil Fol

Team Colleague

Reputation Points: 1135

Solved Threads: 173

Super Senior Demiposter

Offline

2,479 posts
since Jun 2005

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Efficient Way to Write a Bunch of Or's?

Next Thread in C++ Forum Timeline: Create Process

DaniWeb Message

Cancel Changes

User Name
Password