Re: hash_map

From:

"tat" <tuantran167@gmail.com>

Newsgroups:

comp.lang.c++.moderated

Date:

3 Oct 2006 14:32:09 -0400

Message-ID:

<1159896461.097750.234240@m7g2000cwm.googlegroups.com>

Hi all,

Thanks very much for all of your comments about hash_map and various
issues around it.
Can someone suggest a good string hash function for a string of length
ranging from 7 to 13? I googled and found a webpage
(GeneralHashFunctions) of Arash Partow (http://www.partow.net) on which
there are a number of hash functions. I copied them below. I am not
sure which one is good for my case.

Thanks,
tat
---------------------------------------------- Hash functions
------------------------------
unsigned int RSHash(string str)
{

    unsigned int b = 378551;
    unsigned int a = 63689;
    unsigned int hash = 0;

    for(unsigned int i = 0; i < str.length(); i++)
    {
       hash = hash*a+str[i];
       a = a*b;
    }

    return (hash & 0x7FFFFFFF);

};
/* End Of RS Hash Function */

unsigned int JSHash(string str)
{

    unsigned int hash = 1315423911;

    for(unsigned int i = 0; i < str.length(); i++)
    {
       hash ^= ((hash << 5) + str[i] + (hash >> 2));
    }

    return (hash & 0x7FFFFFFF);

};
/* End Of JS Hash Function */

unsigned int PJWHash(string str)
{

    unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int)
* 8);
    unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt *
3) / 4);
    unsigned int OneEighth = (unsigned int)(BitsInUnignedInt /
8);
    unsigned int HighBits = (unsigned int)(0xFFFFFFFF) <<
(BitsInUnignedInt - OneEighth);
    unsigned int hash = 0;
    unsigned int test = 0;

    for(unsigned int i = 0; i < str.length(); i++)
    {

       hash = (hash << OneEighth) + str[i];

       if((test = hash & HighBits) != 0)
       {

          hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));

       }

    }

  return (hash & 0x7FFFFFFF);

};
/* End Of P. J. Weinberger Hash Function */

unsigned int ELFHash(string str)
{

    unsigned int hash = 0;
    unsigned int x = 0;

    for(unsigned int i = 0; i < str.length(); i++)
    {
       hash = (hash << 4) + str[i];
       if((x = hash & 0xF0000000L) != 0)
       {
          hash ^= (x >> 24);
          hash &= ~x;
       }
    }

    return (hash & 0x7FFFFFFF);

};
/* End Of ELF Hash Function */

unsigned int BKDRHash(string str)
{

    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;

    for(unsigned int i = 0; i < str.length(); i++)
    {

       hash = (hash*seed)+str[i];

    }

    return (hash & 0x7FFFFFFF);

};
/* End Of BKDR Hash Function */

unsigned int SDBMHash(string str)
{

    unsigned int hash = 0;

    for(unsigned int i = 0; i < str.length(); i++)
    {

       hash = str[i] + (hash << 6) + (hash << 16) - hash;

    }

    return (hash & 0x7FFFFFFF);

};
/* End Of SDBM Hash Function */

unsigned int DJBHash(string str)
{

    unsigned int hash = 5381;

    for(unsigned int i = 0; i < str.length(); i++)
    {

       hash = ((hash << 5) + hash) + str[i];

    }

    return (hash & 0x7FFFFFFF);

};
/* End Of DJB Hash Function */

unsigned int APHash(string str)
{

    unsigned int hash = 0;

    for(unsigned int i = 0; i < str.length(); i++)
    {

       if ((i & 1) == 0)
       {
          hash ^=((hash << 7)^str[i]^(hash >> 3));
       }
       else
       {
          hash ^= (~((hash << 11)^str[i]^(hash >> 5)));
       }

    }

    return (hash & 0x7FFFFFFF);

};
/* End Of AP Hash Function */

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]