Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Different Hash Functions (thanks to Prof. Volper)
/*
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment