Different Hash Functions (thanks to Prof. Volper)

HashFunctions.h

/*
  COMPARISON
  keylen = 512, iterations = 100000
====================================
            Simple... 0.078 s
                RS... 0.422 s
         RS (Fast)... 0.156 s
         Universal... 0.454 s
  Universal (Fast)... 0.156 s
               PJW... 0.328 s
              DJB1... 0.125 s
              DJB2... 0.203 s
             Knuth... 0.219 s
               K&R... 0.140 s
               FNV... 0.141 s
        Super Fast... 0.078 s
           STLPort... 0.078 s

*/

/*
  Interesting sources on hashing:
  http://www.azillionmonkeys.com/qed/hash.html
  http://burtleburtle.net/bob/hash/
  http://www.isthe.com/chongo/tech/comp/fnv/
  http://cmph.sourceforge.net/ // for very large sets
  https://www.gnu.org/software/gperf/gperf.html // for smaller sets
*/

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
unsigned ConstantHash(const char *Key, unsigned TableSize)
{
  return 1;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
unsigned ReflexiveHash(const char *Key, unsigned TableSize)
{
  return StrToInt(Key) % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
unsigned PJWHash(const char *Key, unsigned TableSize)
{
    // Initial value of hash
  unsigned hash = 0;

    // Process each char in the string
  while (*Key)
  {
      // Shift hash left 4
    hash = (hash << 4);

      // Add in current char
    hash = hash + (*Key);

      // Get the four high-order bits
    unsigned bits = hash & 0xF0000000;

      // If any of the four bits are non-zero,
    if (bits)
    {
        // Shift the four bits right 24 positions (...bbbb0000)
        // and XOR them back in to the hash
      hash = hash ^ (bits >> 24);

        // Now, XOR the four bits back in
      hash = hash ^ bits;
    }

      // Next char
    Key++;
  }

    // Modulo so hash is within 0 - TableSize
  return hash % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
unsigned SimpleHash(const char *Key, unsigned TableSize)
{
    // Initial value of hash
  unsigned hash = 0;

    // Process each char in the string
  while (*Key)
  {
      // Add in current char
    hash += *Key;

      // Next char
    Key++;
  }

    // Modulo so hash is within the table
  return hash % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
unsigned RSHash(const char *Key, unsigned TableSize)
{
  unsigned hash = 0;         // Initial value of hash
  unsigned multiplier = 127; // Prevent anomalies

    // Process each char in the string
  while (*Key)
  {
      // Adjust hash total
    hash = hash * multiplier;

      // Add in current char and mod result
    hash = (hash + *Key) % TableSize;

      // Next char
    Key++;
  }

    // Hash is within 0 - TableSize
  return hash;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// Same as above but performing the modulo once at the end
unsigned RSHashMod(const char *Key, unsigned TableSize)
{
  unsigned hash = 0;         // Initial value of hash
  unsigned multiplier = 127; // Prevent anomalies

    // Process each char in the string
  while (*Key)
  {
      // Adjust hash total
    hash = hash * multiplier;

      // Add in current char and mod result
    hash = hash + *Key;

      // Next char
    Key++;
  }

    // Hash is within 0 - TableSize
  return hash % TableSize;;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
unsigned UHash(const char *Key, unsigned TableSize)
{
  unsigned hash = 0;       // Initial value of hash
  unsigned rand1 = 31415; // "Random" 1
  unsigned rand2 = 27183; // "Random" 2

    // Process each char in string
  while (*Key)
  {
      // Multiply hash by random
    hash = hash * rand1;

      // Add in current char, keep within TableSize
    hash = (hash + *Key) % TableSize;

      // Update rand1 for next "random" number
    rand1 = (rand1 * rand2) % (TableSize - 1);

      // Next char
    Key++;
  }

    // Hash value is within 0 - TableSize - 1
  return hash;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// Same as above but performing the modulo once at the end
unsigned UHashMod(const char *Key, unsigned TableSize)
{
  unsigned hash = 0;       // Initial value of hash
  unsigned rand1 = 31415; // "Random" 1
  unsigned rand2 = 27183; // "Random" 2

    // Process each char in string
  while (*Key)
  {
      // Multiply hash by random
    hash = hash * rand1;

      // Add in current char, keep within TableSize
    hash = (hash + *Key);

      // Update rand1 for next "random" number
    rand1 = (rand1 * rand2);

      // Next char
    Key++;
  }

    // Hash value is within 0 - TableSize - 1
  return hash % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//  Daniel J. Bernstein #1
unsigned DJB1Hash(const char *Key, unsigned TableSize)
{
  unsigned hash = 0;
  while (*Key)
  {
    hash *= 33;
    hash += *Key;
    Key++;
  }
  return hash % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//  Daniel J. Bernstein  #2
unsigned DJB2Hash(const char *Key, unsigned TableSize)
{
  unsigned hash = 5381;
  while (*Key)
  {
    hash <<= 5;
    hash += hash;
    hash += *Key;
    Key++;
  }
  return hash % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// Donald E. Knuth
unsigned DEKHash(const char *Key, unsigned TableSize)
{
  unsigned hash = (unsigned)strlen(Key);
  while (*Key)
  {
    hash <<= 5;
    hash ^= (hash >> 27);
    hash ^= *Key;
    Key++;
  }
  return hash % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// K&R Hash page 144 in the white book (second edition)
unsigned KRHash(const char *Key, unsigned TableSize)
{
  unsigned seed = 31;
  unsigned hash = 0;

  while (*Key)
  {
    hash *= seed;
    hash += *Key;
    Key++;
  }
  return hash % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// Fowler, Noll, Vo
// http://isthe.com/chongo/tech/comp/fnv/
unsigned FNVHash(const char *Key, unsigned TableSize)
{
  unsigned FNV_prime32 = 16777619;
  unsigned FNV_offset32 = 2166136261;

  unsigned hash = FNV_offset32;
  while (*Key)
  {
    hash *= FNV_prime32;
    hash ^= *Key;
    Key++;
  }
  return hash % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// SuperFastHash by Paul Hsieh
// http://www.azillionmonkeys.com/qed/hash.html
#include <stdint.h> /* Replace with <pstdint.h> if appropriate */
#undef get16bits
#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
  || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
#define get16bits(d) (*((const uint16_t *) (d)))
#endif

#if !defined (get16bits)
#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                       +(uint32_t)(((const uint8_t *)(d))[0]) )
#endif

uint32_t SFHash (const char * data, unsigned TableSize)
{
  int len = strlen(data);
  uint32_t hash = len;
  uint32_t tmp;
  int rem;

    if (len <= 0 || data == NULL) return 0;

    rem = len & 3;
    len >>= 2;

    /* Main loop */
    for (;len > 0; len--) {
        hash  += get16bits (data);
        tmp    = (get16bits (data+2) << 11) ^ hash;
        hash   = (hash << 16) ^ tmp;
        data  += 2*sizeof (uint16_t);
        hash  += hash >> 11;
    }

    /* Handle end cases */
    switch (rem) {
        case 3: hash += get16bits (data);
                hash ^= hash << 16;
                hash ^= data[sizeof (uint16_t)] << 18;
                hash += hash >> 11;
                break;
        case 2: hash += get16bits (data);
                hash ^= hash << 11;
                hash += hash >> 17;
                break;
        case 1: hash += *data;
                hash ^= hash << 10;
                hash += hash >> 1;
    }

    /* Force "avalanching" of final 127 bits */
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;

    return hash % TableSize;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// STLPort 4.6.2
unsigned STLPortHash(const char *Key, unsigned TableSize)
{
  unsigned hash = 0;
  while (*Key)
  {
    hash = (hash * 5) + *Key;
    Key++;
  }
  return hash % TableSize;
}