DaniWeb Forum Index > Software Development > C++

C++ RSS

String Hash Function

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Sep 2009

Posts: 19

Reputation: killerqb is an unknown quantity at this point

Solved Threads: 0

killerqb

Offline

Newbie Poster

String Hash Function

Oct 21st, 2009

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:

 Help with Code Tags 
 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.

•

Join Date: Jun 2009

Posts: 681

Reputation: Tom Gunn has much to be proud of

Solved Threads: 132

Tom Gunn

Offline

Practically a Master Poster

Oct 21st, 2009

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

 Help with Code Tags 
 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.

-Tommy (For Great Justice!) Gunn

•

Join Date: Sep 2009

Posts: 19

Reputation: killerqb is an unknown quantity at this point

Solved Threads: 0

killerqb

Offline

Newbie Poster

Oct 21st, 2009

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

•

Join Date: Jun 2009

Posts: 681

Reputation: Tom Gunn has much to be proud of

Solved Threads: 132

Tom Gunn

Offline

Practically a Master Poster

Oct 21st, 2009

•

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.

-Tommy (For Great Justice!) Gunn

•

Join Date: Jun 2005

Posts: 2,044

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Oct 21st, 2009

•

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?

All my posts may be redistributed under the GNU Free Documentation License.

•

Join Date: Sep 2009

Posts: 19

Reputation: killerqb is an unknown quantity at this point

Solved Threads: 0

killerqb

Offline

Newbie Poster

Oct 21st, 2009

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

•

Join Date: Sep 2009

Posts: 19

Reputation: killerqb is an unknown quantity at this point

Solved Threads: 0

killerqb

Offline

Newbie Poster

Oct 21st, 2009

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;
}

•

Join Date: Sep 2009

Posts: 19

Reputation: killerqb is an unknown quantity at this point

Solved Threads: 0

killerqb

Offline

Newbie Poster

Oct 21st, 2009

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.

 Help with Code Tags 
 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.

•

Join Date: Jun 2005

Posts: 2,044

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Oct 21st, 2009

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.

All my posts may be redistributed under the GNU Free Documentation License.