Friday, January 15, 2010

Brain Dead Hash Function

I love things that are brain-dead simple.   Here's a very old C function that hashes a string:

int
HashFunction(char *string, int size)
{
   int hashkey = 1;

   while (string[0])
   {
      hashkey  = hashkey<<1^string[0];
      string++;
   }

   return hashkey%size;
}

Another way: although the following routine returns the crc16 for the string that's passed in, it can also be used as a way to hash a string:

/*    crc16 - crc16 routine
 *
 *    R.K. Irvine
 *
 *    This routine returns the crc16 for the string pointed
 *    to by "in".
 *    crc16 is given by:  x^16 + x^15 + x^2 + 1
 */
unsigned short
crc16(register char *in)
{
   register unsigned int n, crc;

   static unsigned short
   crc16l[]
   =
   {
      0x0000,0xc0c1,0xc181,0x0140,
      0xc301,0x03c0,0x0280,0xc241,
      0xc601,0x06c0,0x0780,0xc741,
      0x0500,0xc5c1,0xc481,0x0440,
   };

   static unsigned short
   crc16h[]
   =
   {
      0x0000,0xcc01,0xd801,0x1400,
      0xf001,0x3c00,0x2800,0xe401,
      0xa001,0x6c00,0x7800,0xb401,
      0x5000,0x9c01,0x8801,0x4400,
   };

   crc = 0;
   while(n = (unsigned char)(*in++))
   {    
      n ^= crc;
      crc = crc16l[n&0x0f] ^ crc16h[(n>>4)&0x0f] ^ (crc>>8);
   }

   return crc;
}